Comprender una prueba relacionada con los números de Fibonacci.

(Esta es ahora una respuesta larga, pero puede detenerse después de cualquier sección. Cada sección simplemente adopta un enfoque diferente o señala similitudes con otros tipos de problemas).

La primera vez que ve esto, dado el orden en que normalmente se enseñan las cosas, parece arbitrario. Es más claro cuando ves cómo se desarrolla la recurrencia, ya sea en álgebra lineal o en funciones generadoras.

Por supuesto, puede probar directamente que la fórmula es verdadera. Si$g_n$ es la fórmula, solo necesitas mostrar $g_0=0,g_1=1,$ y $g_{n+1}=g_n+g_{n-1}.$

Pero esa no es una razón satisfactoria de por qué adopta esta forma.

Si definimos una función generadora:

Luego, usando fracciones parciales, del cálculo, obtienes, si $r_1,r_2$ son las raíces de $y^2-y-1=0,$ entonces para algunos $a_1,a_2$:

Como es habitual con las fracciones parciales, si el polinomio en el denominador tiene raíces repetidas, entonces su término general es, si el grado de una raíz $r_i$ en el polinomio es $d_i,$

El enfoque del álgebra lineal es tener en cuenta:

Así que si $A=\begin{pmatrix}1&1\\1&0\end{pmatrix}$ tienes:

La matriz $A$ tiene polinomio característico $x^2-x-1,$ que tiene dos raíces distintas, por lo que hay una matriz $S$ de modo que:

Entonces podemos expresar las entradas de $A^n$ cada uno como $a_{ij}r_1^{n}+b_{ij}r_2^n,$ y así de manera similar para $f_n.$

Al igual que con las fracciones parciales, la forma de la matriz que se obtiene cuando el polinomio tiene raíces repetidas se vuelve más complicada. No se puede obtener una matriz diagonal, en general, solo una matriz en forma normal de Jordan.

Una tercera forma de pensarlo es en términos del espacio vectorial de todas las secuencias. $\mathbf a=(a_i)_{i=0}^\infty$ y el operador lineal:

Entonces nuestra recurrencia significa que si $\mathbf f=(f_i)$ entonces $(D^2-D-I)\mathbf f=0,$ aquí $I$ es el operador de identidad $I\mathbf a=\mathbf a.$

Reescribiendo eso como:

Entonces deja

Entonces desde $(D-r_1I)\mathbf e =0$, tu consigues eso $e_i=r_1^ie_0.$

Similar, $d_i=f_{i+1}-r_1f_i$ da $d_i=r_2^id_0,$ entonces

Entonces

Entonces usa eso

Y

Y por lo tanto, dejar $c_1=e_0,c_2=d_0,$ usted obtiene:

Dado $r_i=\frac{1\pm\sqrt 5}{2},$ $2r_i-1=\pm\sqrt 5$ y $d_0=e_0=1,$ usted obtiene:

En el caso más general, si $p(x)$ es un polinomio sin raíz repetida, entonces $\gcd(p(x),p’(x))=1.$ (En el caso de Fibonacci, $p(x)=x^2-x-1$ y $p’(x)=2x-1.$) Entonces:

Entonces sí $p(D)\mathbf a=0,$ usted obtiene $p_j(D)\mathbf a$ es una serie geométrica con razón común $r_j,$ y

Pero el requisito de GCD significa que tenemos una solución para:

(En Fibonacci, $u(x)=(2x-1)/5, v(x)=4/5,$ por (2).)

Entonces esto significa:

Y esto te dará:

Esta técnica funciona hasta (3) con raíces repetidas, excepto que obtienes $p’(x)=\sum_j d_ip_i(x).$ Pero en (3), lo mejor que puede obtener es:

Ese último enfoque está relacionado con la ecuación diferencial lineal, donde a menudo se le enseña primero, "Oye, probemos ciertas soluciones de la forma $e^{rx},$”Sin mucha motivación.

En el espacio vectorial de funciones infinitamente diferenciables, obtenemos un operador lineal $D$ definido como

Entonces las ecuaciones diferenciales lineales se pueden escribir como $p(D)f=0$ para algún polinomio $p.$

Como antes, si $p(x)$ no tiene raíces repetidas, obtienes: $g_i=p_i(D)f$ es una raíz de $(D-r_i)g_i=0$ o $g_i’(x)=r_ig_i(x),$ que tiene un conjunto de soluciones conocido $g_i(x)=C_ie^{r_ix}.$

Entonces

Básicamente, estamos encontrando soluciones para $p(D)f=0$ en términos de vectores propios conocidos $v_i$ del operador lineal $D$ para valores propios $r_i,$ y siempre se complica cuando hay raíces repetidas.

Incluso el enfoque del álgebra lineal funciona de esta manera.

$A$ satisface $p(A)=0,$ así que dado cualquier vector $\mathbf v$ obtenemos $\mathbf v_i=p_i(A)\mathbf v$ es un vector propio de $A$ para valor propio $r_i.$

Entonces

Y:

En el caso de Fibonacci, $\mathbf v=(1,0)^t$ y $\mathbf v_i=(1-r_{3-i},1)^t=(r_i,1)$ y $u(r_i)=(2r_i-1)/5=\pm\frac{1}{\sqrt5}.$.

Si alguna vez ha estudiado ecuaciones diferenciales, probablemente se haya encontrado con algo similar, donde se sugiere una solución de cierta forma y luego se descubre que funciona. Esto no es una coincidencia, ya que las teorías de ecuaciones diferenciales y de recurrencias tienen algunos puntos en común. En ambos entornos, es común que los estudiantes se sientan insatisfechos cuando se encuentran por primera vez con este tipo de argumentación.

Algunas cosas que pueden ayudar psicológicamente:

1. Tuvo que esperar mucho tiempo antes de que el primer ser humano tropezara con la solución que los autores de libros de texto presentan ahora con tanta naturalidad. No sé cómo se encontró por primera vez esta solución en particular; quizás alguien llegó al problema con alguna experiencia relevante, quizás por haber estudiado ecuaciones diferenciales; tal vez hubo mucho ensayo y error involucrado; quizás tuvieron suerte.
2. hay problemas muy similares para los que este método de solución no funciona, al menos no sin modificaciones. Considerar$f_n=2f_{n-1}-f_{n-2}$. El método falla aquí porque la ecuación secular tiene una raíz doble. Estoy seguro de que Brualdi analiza la modificación necesaria para manejar este caso, aunque no tengo el libro a mano para comprobarlo. (Implica postular$nq^n$como una segunda solución.) El punto es que no es el caso que la suposición sea tan obvia que simplemente tiene que funcionar. No tiene por qué funcionar, pero vale la pena intentarlo y resulta que tiene éxito.

Ahora, algunas posibles motivaciones para hacer tal suposición.

1. Esta es una recurrencia de dos términos. Quizás uno debería intentar resolver las recurrencias de un término antes de abordar esto. Qué tal si $$f_n=3f_{n-1}?$$ Esta ecuación solo dice que cada término es $3$ veces tan grande como el término anterior, por lo que aparece una solución exponencial: $f(n)=C\cdot3^n$. Volviendo al caso de dos términos, uno podría preguntarse qué pasaría si intentara esto nuevamente, pero no está claro qué base de la exponencial probar, por lo que lo convertimos en un parámetro. Después de un paso o dos de álgebra, te das cuenta de que el$n$-la dependencia se cancela, lo que tiene que ser algo bueno. Así que seguimos adelante para ver qué tan lejos podemos llegar ...
2. Ya hemos mencionado las ecuaciones diferenciales. Si tienes la ecuación diferencial$f'(x)=kf(x)$ puede que sepas que $q^x$ resuelve esto, donde $q=e^k$. Puede o no haber visto la generalización: $$a_nf^{(n)}(x)+a_{n-1}f^{(n-1)}(x)+\ldots+a_1f'(x)+a_0f(x)=0$$ se puede resolver planteando $f(x)=Ce^{kx}$ y luego resolviendo una ecuación polinomial para encontrar valores de $k$ que dan soluciones.
3. Si el truco utilizado para manejar el caso de doble raíz mencionado anteriormente parece desmotivado cuando llega a él, puede investigar cómo se maneja el problema análogo en el caso de ecuaciones diferenciales. Las cuestiones que rodean la regla de l'Hôpital son relevantes aquí. El punto aquí es que el método de solución está relacionado con muchas otras matemáticas.

Creo que al considerar $f_n=q^n$ obtenemos $f_n-f_{n-1}-f_{n-2}=0 \Rightarrow q^n-q^{n-1}-q^{n-2}=0 \Rightarrow q^n(q^2-q-1)=0$. Por lo tanto, resolviendo la cuadrática podemos tener una idea acerca de$f_n$.

$\begin{bmatrix} f_n\\ f_{n-1} \end{bmatrix}=\begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}\begin{bmatrix} f_{n-1}\\ f_{n-2} \end{bmatrix}=\begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}^{n-1}\begin{bmatrix} f_1\\ f_0 \end{bmatrix}$ Entonces puede calcular los valores propios.

Uno puede encontrar una prueba de ello aquí en mi artículo.
https://www.ssmrmh.ro/2021/04/12/metallic-numbers/
Sin embargo, como resumen, tenga en cuenta que si

Pensé en este enfoque antes y llegué a la conclusión de que:

Vayamos tu pregunta, dijimos $f_n=q^n$ porque sabemos que $f_n$significa, es decir, representa un número. Además, podemos ver que se puede obtener cualquier número jugando términos como$a \times q^n$. Gracias a esta propiedad, podemos satisfacer ecuaciones dadas tales que$f_n=f_{n-1} +f_{n-2} +f_{n-3}$ etc.

Más claramente, digamos que $q=2$ y también queremos obtener alguna recursión como $f_n=f_{n-1} +f_{n-2} +f_{n-3}$ , es decir , $2^n=2^{n-1} + 2^{n-2} +2^{n-3}$. Podemos satificarlo por algún número racional.$a,b,c,d$ tal que $a2^n=b2^{n-1} + c2^{n-2} +d2^{n-3}$. También estamos encontrando estos números racionales por condiciones iniciales.

Como comprenderá, gracias a exponenciales como $q^n$ , podemos satisfacer nuestras ecuaciones de relación recursiva. Por eso, las seleccionamos para usar.

NOTA = Por lo que he entendido, se pregunta por qué elegimos $f_n=q^n$en el comienzo. En realidad, se puede concluir fácilmente a partir de la explicación anterior. Porque, es obvio que$f_n$ es un número racional y podemos indicarlos por exponencial como $57 = 57^1$ o $1/16 = (1/2)^4$

El enfoque estándar para trabajar con secuencias recursivas lineales como la secuencia de Fibonacci es el siguiente: Consideremos un mapeo $\mathbb{Z}^{+} \mapsto \mathbb{R}$ donde decir $R$ es un anillo arbitrario, suponga que la secuencia correspondiente al mapa se representa como $\{u_j\}_{\ge 1}^{\infty}$,

Supongamos que la relación recursiva es de forma $u_{n+k}=\sum_{j=1}^{k}a_{(n+k-j)}\,u_{j}$ ,donde $a_j \in \mathbb{R}$

Entonces a la secuencia podemos asociar un polinomio $p(\xi ) \in \mathbb{R}[\xi]$ tener la representación

Si $\{\phi_j:1\le j \le k\}$ es el conjunto cero de $p(\xi)$ con $\phi_j$es distinto, entonces el término general de $\{u_j\}_{\ge 1}^{\infty}$ tiene forma

NOTA: Para una descripción lesiure pero rigurosa de la teoría de las secuencias recursivas lineales, sugiero revisar el texto soviético clásico RECURSION SEQUENCES, por el profesor Aleksei Ivanovich Markushevich