How many subsets has the set $\{ 1, 2 , \dots, n\}$? How many subsets has the set $\{ 1, 2 , \dots, n\}$ that don't contain two consecutive naturals?
My idea is the following:
$$\displaystyle{2^{\frac{n}{2}}}$$
because $n$ numbers, we can't take two consecutive..
Is this correct??
 A: Here is a substantial hint:
Let $f_n$ be the number you are looking for. Then $f_{n+1}$ adds to $f_n$ the number of subsets containing $n+1$ - these cannot contain $n$, so must be subsets of $\{1,2, \dots , n-1\}$ with $n+1$ added as a member.
You should be able to analyse the problem from there. Don't forget the empty set.
A: Answer:
If n is even, the number of subsets  =  $${n\choose0}+{n\choose1}+{{n-1}\choose2}+\cdots+{{\frac{n}{2}+1}\choose \frac{n}{2}}$$
IF n is odd,   $${n\choose0}+{n\choose1}+{{n-1}\choose2}+\cdots+{{\frac{n+1}{2}}\choose \frac{n+1}{2}}$$
As per Barry's advice, I worked a few scenarios and found this relation after some hard thinking.  Hopefully it is useful.  Good luck
Thanks
Satish
A: Alternatively, it's easy to see that for a subset of size $i$ the number of subsets of $\left[n\right]$ with the required property is $\displaystyle \binom{n-i+1}{i}$ using the following set-up:
Choosing such a subset bijectively corresponds to forming a binary string of length $n$ using $i$ $1$s and $n-i$ $0$s such that no $2$ $1$s are adjacent. Write down $n-i$ $0$s and observe that there are $n-i+1$ positions in which the $i$ $1$s can be inserted. Thus the $1$s can be chosen in $\displaystyle \binom{n-i+1}{i}$ ways. Summing over $i= 1, 2, \ldots, \bigg\lfloor\dfrac{n+1}{2}\bigg \rfloor$ yields the final answer.
As Mark Bennett points out, this is simply $F_{n+2}$ where $F_{n}$ is the $n^{th}$ Fibonacci number.
