Ley de adición de Fibonacci $F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$

Question

Pregunta: Que $F_n$ la secuencia de números de Fibonacci, dada por $F_0 = 0, F_1 = 1$ y $F_n = F_{n-1} + F_{n-2}$ para $n \geq 2$ . Mostrar para $n, m \in \mathbb{N}$ : $$F_{n+m} = F_{n-1}F_m + F_n F_{m+1}$$

Mi intento (muy limitado) hasta ahora: después de crear una pequeña lista de los valores $F_0=0, F_1=1, F_2=1, F_3=2, F_4=3, F_5=5, F_6=8, F_7=13, F_8=21, F_9=34, F_{10}=55$ veo que sí parece funcionar por ejemplo $F_{6+3}=F_5 F_3 +F_6 F_4 = 10 +24 = 34 = F_9$ . Sin embargo, no sé por dónde empezar a demostrar que esto debe mantenerse en términos generales. ¿Debería buscar el uso de límites? ¿O quizás la inducción? ¿Cuál es la mejor manera de resolver esto?

Answer 1

Con los números de Fibonacci normalmente hay múltiples formas de demostrar las identidades.

Una forma (que es una de mis favoritas) de demostrar tu identidad es la siguiente:

Considere el siguiente problema:

Una persona sube $\displaystyle n$ pasos, dando un paso o dos pasos a la vez.

El número total de formas en que la persona puede subir todos los $\displaystyle n$ pasos es $\displaystyle F_{n+1}$ (¿Por qué?)

Ahora considere escalar $\displaystyle m+n-1$ escalones y se divide en los casos en que la persona cae en el escalón $\displaystyle n$ y los casos en los que la persona cae en el escalón $\displaystyle n-1$ y da dos pasos en ese punto (y por lo tanto no aterriza en el paso $\displaystyle n$ en esos casos). Estos dos casos cubren todas las posibilidades, y así tenemos:

$$\displaystyle F_{m+n} = F_{n+1}F_{m} + F_{n}F_{m-1}$$

Answer 2

Si me presionan, yo mismo me quedaría con la fórmula de Binet, pero aquí hay otra enfoque. Por una fácil inducción, si $$A=\pmatrix{0&1\\\\ 1&1}$$ entonces $$A^n=\pmatrix{F_{n-1}&F_n\\\\ F_n&F_{n+1}}.$$ Comparando la entrada superior derecha de la ecuación $A^m A^n=A^{m+n}$ da $$F_{m-1}F_n+F_m F_{n+1}=F_{m+n}.$$

Answer 3

Sugerencia $\ $ Si ponemos la recurrencia de Fibonacci en forma de matriz, el resultado es obvio, a saber

$$ M^n\ :=\ \left[\begin{array}{rr} \!\!1 & 1 \\\ \!\!1 & 0 \end{array}\right]^{\large n} =\, \left[\begin{array}{cc} F_{n+1} &\!\! F_n \\\ F_n &\!\! F_{n-1} \end{array}\right] $$

Ahora comparando las entradas de $\ M^{n+m} = M^n \ M^m\,$ inmediatamente se obtiene la ley de adición de Fibonacci.

Nota: $\ M$ es el operador de desplazamiento, es decir $\,(F_{n1},F_n)M^t = (F_n,F_{n+1}).\,$ La misma idea funciona para cualquier recurrencia lineal.

Answer 4

Ya hay varias respuestas buenas, pero pensé en añadir la siguiente derivación porque es uno de los pocos usos que conozco para la propiedad de la suma de los permanentes; a saber,

Si $A$ , $B$ y $C$ son matrices con entradas idénticas, excepto que una fila (columna) de $C$ , dicen los $k^{th}$ es la suma de los $k^{th}$ filas (columnas) de $A$ y $B$ entonces $\text{ per } A + \text{ per } B = \text{per } C$ .

Comience con las matrices $\begin{bmatrix} F_n & F_{n-1} \\ F_0 & F_1 \end{bmatrix}$ y $\begin{bmatrix} F_n & F_{n-1} \\ F_1 & F_2 \end{bmatrix}$ . Desde $F_0 = 0$ y $F_1 = F_2 = 1$ tienen permanentes $F_n$ y $F_n + F_{n-1} = F_{n+1}$ respectivamente. Aplicando la recurrencia de Fibonacci y la propiedad de la suma permanente, tenemos $\text{ per } \begin{bmatrix} F_n & F_{n-1} \\ F_2 & F_3 \end{bmatrix} = F_{n+2}$ . Continuando con la construcción de nuevas matrices cuyas segundas filas son las sumas de las segundas filas de las dos matrices anteriores, este proceso continúa hasta que tenemos $F_n F_{m+1} + F_{n-1}F_m = \text{ per} \begin{bmatrix} F_n & F_{n-1} \\ F_m & F_{m+1} \end{bmatrix} = F_{n+m}.$

Para más información sobre este enfoque (pero con determinantes), véase este artículo que escribí hace unos años: " Identidades de Fibonacci mediante la propiedad de la suma de determinantes ," La Revista de Matemáticas de la Universidad , 37 (4): 286-289, 2006.

Answer 5

Intenta probar esta afirmación: Afirmación: Si $f(n) = f(n-1)+f(n-2)$ entonces $f(n) = F_n f_1 + F_{n-1} f_0$ .

Ahora "arreglar" $m$ y pensar en $F_{n+m}$ como una recurrencia lineal en $n$ con condiciones iniciales $F_{m+1}$ y $F_m$ .

Luego vendrá su reclamación.

Por cierto, hay una prueba de reclamación corta y limpia, pero debes saber que utiliza el hecho $F_{-1} = 1$ (Algo que puedes comprobar fácilmente si no lo sabías ya).