Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
1  
@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

2 Answers 2

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|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
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. –  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|improve this answer

Your Answer

 
discard

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.