Coeficiente Binomial y números de fibonacci

Question

He encontrado el siguiente problema en putnam y más allá: demostrar que $$F_{2n} = \sum_{k=1}^{n} F_{k}{{n}\choose {k}}$$

La respuesta en la parte de atrás del libro utiliza la forma cerrada de $F_n$, pero a mí me parece su debe ser una solución utilizando sólo las propiedades de la binomial cooeficient. He intentado utilizar $${{n} \choose {k}} = {{n-1} \choose {k}}+ {{n-1}\choose {k-1}}$$

pero esto parece ser un callejón sin salida, y no tengo otras ideas.

Cualquier ayuda es muy apreciada.

Answer 1

Antes de que podamos demostrar que mediante la aplicación de Pascal de la identidad y de la de Fibonacci recurrencia, se debe generalizar la identidad de a $$F_{2n+m} = \sum_{k=0}^n F_{k+m} \binom{n}{k}.$$

Ahora podemos proceder por inducción en $n$. Al $n=0$, la identidad sólo dice $F_m = F_m$, y que será nuestra base de caso. Para $n>0$, tenemos: \begin{align} \sum_{k=0}^n F_{k+m} \binom{n}{k} &= \sum_{k=0}^n F_{k+m} \binom{n-1}{k-1} + \sum_{k=0}^n F_{k+m} \binom{n-1}{k} \\ &= \sum_{k=0}^{n-1} F_{k+m+1} \binom{n-1}{k} + \sum_{k=0}^{n-1} F_{k+m} \binom{n-1}{k} \\ &= F_{2(n-1)+m+1} + F_{2(n-1)+m} \\ &= F_{2n+m}. \end{align}