# 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$.

-
I don't understand. So, if I take n=6, I have {1,2,3,4,5,6} so you are saying the sets I have are {1,2,3,4,5} and {1,2,3,4,6} and {1,2,3,5,6} but these sets still include 3 consecutive integers. I'm confused. – Dave Nov 28 '11 at 5:23
I said every such subset satisfies (exactly) one of the three conditions. I didn't say every set satisfying one of the three conditions is such a subset. – Gerry Myerson Nov 28 '11 at 6:19

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\}$.

-

For n=0, You have null set as subset. So that count as 1

For n=1, You have {1} and a null subset. So that count as 2

For n=2, You have null + 2C1 +2C2 subsets. So that is 4

For n=3, You have null + 3C1 +3C2 subsets. We can't include 3C3 as consecutive numbers are not allowed. So that is 7

Note: 7=4+2+1

For n=4, You have null + 4C1 +4C2 + 4C3 -2 why -2? as {1,2,3} and {2,3,4} are not allowed. So 13

13=7+4+2

Hence Recurrence F(n)= F(n-1)+ F(n-2)+ F(n-3)

-