1
$\begingroup$

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

  • 0
    @Srivatsan, yes. I'm really not sure what Dave means by "polynomial formula."2011-11-28

3 Answers 3

7

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

  • 2
    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.2011-11-28
0

My Hint: $f_n$ can be any set from $f_i$ such that $i plus the element $\{n\}$. it can also be any set from $f_i$ such that $i plus the elements $\{n-1,n\}$.

0

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)