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
    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).2011-11-28
  • 1
    @Srivatsan, it's the subsets with no *two* consecutive integers that give you the Fibonaccis.2011-11-28
  • 0
    @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.2011-11-28
  • 0
    @Srivatsan, yes. I'm really not sure what Dave means by "polynomial formula."2011-11-28

3 Answers 3