Prueba combinatoria de una identidad de Fibonacci: $n F_1 + (n-1)F_2 + \cdots + F_n = F_{n+4} - n - 3.$

Question

¿Alguien conoce una prueba combinatoria de la siguiente identidad, donde $F_n$ es el $n$-ésimo número Fibonacci?

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

No está donde pensé que sería más probable que apareciera: en el libro _Proofs That Really Count_ de Benjamin y Quinn. De hecho, este puede ser un problema difícil, ya que dicen que la identidad similar

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

necesita una prueba combinatoria.

Para referencia, aquí (del texto de Benjamin y Quinn) hay varias interpretaciones combinatorias de los números Fibonacci.

Answer 1

Recuerda que $F_{n+1}$ es la cantidad de formas de cubrir un tablero de longitud $n$ con fichas de longitud $1$ y $2$. Entonces, $F_{n+4}$ es la cantidad de formas de cubrir un tablero de longitud $n+3$ con fichas de longitud $1$ y $2$. Nótese que $n+3$ de estas colocaciones utilizan a lo sumo una ficha de longitud $2$, por lo que $F_{n+4} - (n+3)$ de estas colocaciones utilizan al menos dos fichas de longitud $2.

Dada una colocación así, observa dónde se utiliza la antepenúltima ficha de longitud $2. La parte después de esta ficha es una colocación de una sección de longitud $k+1$ donde exactamente una ficha de longitud $2$ es utilizada (lo cual se puede hacer de $k$ formas), y la parte antes de esta ficha es una colocación de la porción restante de longitud $n-k$ (lo cual se puede hacer de $F_{n-k+1}$ formas). Suma sobre $k$.

(La lección principal aquí es que la convolución es mucho más fácil de manejar que el producto de Hadamard. Además, dado que la biyección que describí anteriormente conserva la cantidad de fichas de cada tipo, la identidad se puede mejorar a una identidad de los números de $q$-Fibonacci.)