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

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.
