sdentatoiz

2022-09-11

Combinatorial proof of a Fibonacci identity: $n{F}_{1}+\left(n-1\right){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?

Peugeota2p

Expert

Recall that ${F}_{n+1}$ is the number of ways to tile a board of length 𝑛 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}-\left(n+3\right)$ 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$.

Do you have a similar question?