Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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$.

share|cite|improve this answer
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\}$.

share|cite|improve this answer

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


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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.