How many subsets does the set S = {1,2,...,n} have that contain no two consecutive integers? Assuming that the number of subsets is f(n), you need to find a recurrence relation and its initial conditions.
Can anybody explain me how to solve this question? I've tried to solve it but I couldn't come up with a recurrence relation..
$f(n)=f(n-1)+f(n-2)$. The first term gives you all subsets that do not contain $n$ and the second gives you all subsets that contain $n$.
Note that $f(0)=1$ (the empty set) and $f(1)=2$ (the empty set and the whole set).