Let $f(n)$ be the number of subsets of $[n]$ that do not contain two consecutive integers. For example, for $n = 4$ we have the subsets $\emptyset$, $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{1, 3\}$, $\{1, 4\}$, $\{2, 4\}$, so $f(4) = 8$.
The solution: $f(n) = f(n − 1) + f(n − 2)$ for $n \geq 2$.
My question is: How do I approach this kind of problems to reach the recurrence solution?
In order to see that $f(n)=f(n-1)+f(n-2)$, notice that a subset $A$ of $[n]$ satisfying the condition either contains $n$ or doesn't.
If $n\in A$, then $A$ surely doesn't contain $n-1$, and hence $A-\{n\}$ is a subset of $[n-2]$ satisfying the condition. Thus, there are $f(n-2)$ such sets $A$.
Otherwise, if $n\not\in A$, then $A-\{n\}$ is a subset of $[n-1]$ satisfying the condition. There are thus $f(n-1)$ such sets $A$.
In total, we obtain $f(n)=f(n-2)+f(n-1)$, as desired. Since $f(0)=1$ and $f(1)=2$, we see that $f(n)=F_{n+2}$, the $(n+2)$nd Fibonacci number.
Notice that for this kind of problem, it is essential to try and reduce the problem to one of the previous cases, for instance by removing elements.
