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??

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
