Does anyone know a combinatorial proof of the following identity, where $F_n$ is the $n$th Fibonacci number?

$$n F_1 + (n-1)F_2 + \cdots + F_n = F_{n+4} - n - 3$$

It's not in the place I thought it most likely to appear: Benjamin and Quinn's Proofs That Really Count. In fact, this may be a hard problem, as they say the similar identity

$$ F_1 + 2F_2 + \cdots + nF_n = (n+1)F_{n+2} - F_{n+4} +2$$

is "in need of a combinatorial proof."

For reference, here (from Benjamin and Quinn's text) are several combinatorial interpretations of the Fibonacci numbers.

  • $\begingroup$ I know that You are looking for combinatorical proof, but it is easy to show that this is true using induction. $\endgroup$ – Tomek Tarczynski Dec 24 '10 at 22:26
  • $\begingroup$ @Tomek: Yes, and I have another (non-inductive) proof that is also not combinatorial. Right now I really am only interested in a combinatorial one - for aesthetic reasons. :) $\endgroup$ – Mike Spivey Dec 24 '10 at 22:34

Recall that $F_{n+1}$ is the number of ways to tile a board of length $n$ with tiles of length $1$ and $2$. So $F_{n+4}$ is the number of ways to tile a board of length $n+3$ with tiles of length $1$ and $2$. Note that $n+3$ such tilings use at most one tile of length $2$, so $F_{n+4} - (n+3)$ such tilings use at least two tiles of length $2$.

Given such a tiling, look at where the second-to-last tile of length $2$ is used. The part after this tile is a tiling of some section of length $k+1$ where exactly one tile of length $2$ is used (which can be done in $k$ ways), and the part before this tile is a tiling of the remaining portion of length $n-k$ (which can be done in $F_{n-k+1}$ ways). Sum over $k$.

(The bigger lesson to take away here is that convolution is much easier to deal with than Hadamard product. Also, since the bijection I described above preserves the number of tiles of each type, the identity can be upgraded to an identity of $q$-Fibonacci numbers.)

  • 3
    $\begingroup$ The other lesson to take away is that you can sometimes convert generating function identities directly into combinatorial proofs (which I imagine was your second proof); I think Zeilberger and others have written papers about the possibility of doing this automatically. $\endgroup$ – Qiaochu Yuan Dec 25 '10 at 6:25
  • $\begingroup$ Beautiful! And I second your comment about convolution generally being easier to deal with. $\endgroup$ – Mike Spivey Dec 25 '10 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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