# Number of subsets of $\{1,2, \ldots, n\}$ containing no three consecutive integers: recurrence equation?

I'm thinking about the problem below. I know that I have to find a polynomial formula for that first, and then from that polynomial formula I can find the recurrence relation. I actually attempted finding a polynomial formula, but I think I'm leaving some options while thinking about three consecutive integers. Anyway, without further ado, here is the problem and your suggestions are appreciated:

Let $f_n$ be the number of subsets of $\{1,2,3,\ldots, n\}$ that contain no three consecutive integers. Find a recurrence for $f_n$.

-
What is the polynomial formula? If you are guessing that $f_n$ is a polynomial in $n$, then that's not the case. In fact, the answer to this is given by the Fibonacci numbers, which grow exponentially fast (i.e., faster than any polynomial). –  Srivatsan Nov 28 '11 at 4:42
@Srivatsan, it's the subsets with no two consecutive integers that give you the Fibonaccis. –  Gerry Myerson Nov 28 '11 at 4:58
@Gerry, Indeed, thanks for the correction. [Grr, I should really pay more attention :).] Anyway, $f_n$ is then even larger than Fibonacci, and hence grows larger than every polynomial. –  Srivatsan Nov 28 '11 at 5:00
@Srivatsan, yes. I'm really not sure what Dave means by "polynomial formula." –  Gerry Myerson Nov 28 '11 at 5:05

Hint: every such subset leaves out $n$, or includes $n$ but leaves out $n-1$, or includes $n$ and $n-1$ but leaves out $n-2$.
My Hint: $f_n$ can be any set from $f_i$ such that $i<n-1$ plus the element $\{n\}$. it can also be any set from $f_i$ such that $i<n-2$ plus the elements $\{n-1,n\}$.