Combinatorial proof of a Fibonacci identity: $n F_1 + (n-1)F_2 + \cdots + F_n = F_{n+4} - n - 3.$

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.

Solution 1:

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