Recursividad Fibonacci con coeficientes binomiales

Question

Mientras que la experimentación con los números de Fibonacci y el triángulo de Pascal, he encontrado este: tome cualquier fila del triángulo de Pascal (es decir, $n = 7$): $$1, 7, 21, 35, 35, 21, 7, 1$$ y escribir debajo de los números de Fibonacci, con $F_0=0$, pasando bajo el segundo número (por supuesto, asumimos $F_{-1} = F_1 - F_0 = 1$). Luego, escribe una tercera fila de $\pm1$'s: $$\begin{array}{ccc}1&7&21&35&35&21&7&1\\1&0&1&1&2&3&5&8\\1&-1&1&-1&1&-1&1&-1\\\end{array}$$ Multiplicar abajo de las columnas: $$\begin{array}{ccc}1&0&21&-35&70&-63&35&-8\\\end{array}$$ y ahora agregar la fila para conseguir $21$, que es el ($n+1$)ésimo número de Fibonacci! Esto parece funcionar para todos los $n$.

Para probar esto sería para demostrar los siguientes Fibonacci recursividad con los coeficientes binomiales: $$F_{n+1} = \sum_{k=0}^n {\left(\left(-1\right)^k {n\choose k} F_{k-1}\right)}$$ No estoy seguro de cómo continuar a partir de aquí, cualquier insinuación? Gracias!

Answer 1

Recuerda que el $Fn = \frac{1}{\sqrt5}\left(\varphi^n - (-\varphi)^{-n}\right)$ y $\varphi - 1 = \frac{1}{\varphi}$. Ahora podemos sustituya en su suma: $\sum{k = 0} ^ n \left ((-1) ^ k \binom{n}{k}F{k - 1} \right) \ = \frac{1}{\sqrt5}\sum{k = 0} ^ \left n ((-1) ^ k \binom{n}{k} (\varphi^{k - 1} - (- \varphi)^{1 - k)} \right) \ = \frac{1}{\sqrt5}\left (\frac {1} {\varphi}(1-\ varphi) ^ n + \varphi\left (1 + \frac{1}{\varphi}\right)^n\right)\ = \frac{1}{\sqrt5}\left(-(-\varphi)^{-n - 1} + \varphi^{n + 1} \right) \ = F_ {n + 1}. $$

Answer 2

Un enfoque de los sistemas dinámicos: Deje $\sigma$ denotar el "derecho-shift" en el espacio de secuencias de $(x_n)_{n\in {\Bbb Z}}$, es decir: $$ (\sigma x)_n = x_{n+1}, \ \ {n\in {\Bbb Z}} $$ A continuación, la secuencia de Fibonacci, $(F_n)_{n\in {\Bbb Z}}$, se verifica: $$ \sigma^2 F = \sigma F + F = (\sigma +1) F $$ o, de manera equivalente, $$ \sigma^{-1}F = \sigma F - F = (\sigma -1) F $$ La primera de identidad implica: $$ \sigma^{2n} F = (\sigma +1)^n F = \sum_{k=0}^n \binom{n}{k}\sigma^k F $$ y la segunda: $$ \sigma^{-n} F = (\sigma -1)^n F = \sum_{k=0}^n (-1)^{n-k}\binom{n}{k}\sigma^k F = (-1)^{n+1} \sum_{k=0}^{n-1} (-1)^{k-1}\binom{n}{k}\sigma^k F $$ La evaluación de estos últimos en el índice de $-1$, es decir: $$ F_{-n-1}=(\sigma^{-n} F)_{-1} = (-1)^{n+1} \sum_{k=0}^n (-1)^{k-1}\binom{n}{k}\sigma^k F_{k-1} $$ vemos que su identidad, que realmente corresponde a la evaluación de $(-1)^{n+1} F_{-n-1}$ e no $F_{n+1}$. Se acaba de pasar a ser idénticas, debido a la simetría en las condiciones iniciales que definen $(F_n)_{n\in {\Bbb Z}}$ [La secuencia de $F_n - (-1)^n F_n, \ {n\in {\Bbb Z}}$ es idéntica a cero]