Question

How many subsets of {1, 2, · · · , n} have no two successive numbers?

Answer 1

hi

Here is the solution :

The subsets are interpreted as n

-words from the alphabet {0,1}. Let an be the number of words with no consecutive ones. Then, a word can start from 0 and proceed in an−1 ways or start with 10 and proceed in an−2 ways. Therefore, an=an−1+an−2. a1=2,a2=3. So, an=Fn+2.

hope it helps
☺☺☺☺☺☺