All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
No neighbors allowed (Posted on 2015-05-22) Difficulty: 3 of 5
How many subsets of {1,2,...,n} contain no consecutive integers?

See The Solution Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Hints/Tips re: solution............spoiler Comment 2 of 2 |
(In reply to solution by Charlie)

Your result is correct,  and it can be easily explained:

the number a(n) must cover all the qualifying subsets of n-1 integers i.e,  a(n-1) plus all the qualifying subsets of n-2 elements, where to each of them integer n was added (the integer n-1 is absent!).

a(n)= a(n-1) + a(n-2)

a(1)=2=f(3)   so  a(n)=f(n+2)







  Posted by Ady TZIDON on 2015-05-22 17:28:26
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information