¿Por qué es correcta la prueba de la función generadora de la fórmula de Fibonacci?

Question

La prueba es la siguiente:-

Sea $F = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + ...$

Entonces

$$\begin{align} 1 + Fx + Fx^2 &= 1 + (x + x^2 + 2x^3 + 3x^4 + ...) + (x^2 + x^3 + 2x^4 + 3x^5) \\ 1 + Fx + Fx^2 &= 1 + x + (x^2+x^2 + 2x^3+x^3 + 3x^4+2x^4 + ...) \\ 1 + Fx + Fx^2 &= F \\ \frac{1}{1-x-x^2} &= F \end{align} $$

Reordenamos los términos y obtenemos este resultado que puede ser manipulado para encontrar la fórmula del enésimo término de Fibonacci.

Quiero centrarme en el reordenamiento de términos en una serie infinita . Esto no difiere de resultados como $ 1 + 2 + 4 + 8 + ... = -1$ .

La respuesta habitual es que no podemos tratar una suma infinita como esta como números reales y aplicar las reglas normales de suma y resta . Debemos aplicar técnicas sofisticadas como los límites para evaluar estas sumas. Así que $ 1 + r + r^2 + r^3 + ... $ sólo tiene sentido cuando $|r| < 1$ .

Así que volviendo a la prueba de Fibonacci anterior. Estamos aplicando las reglas normales de adición para una suma infinita y también el resultado $\displaystyle F = \frac{1}{1-x-x^2} $ no tiene sentido para ningún valor de $x$ . Pero aún así utilizamos este resultado para completar la prueba. Por qué funciona ?

¿No es lo mismo que utilizar el resultado $ 1 + 2 + 4 + 8 + ... = -1 $ demostrar otros resultados ? Sería absurdo utilizarlo como base para otras pruebas.

Por favor, arroje algo de luz sobre esto. Estoy muy confundido.

Answer 1

Una forma de hacerlo es demostrar primero que la serie converge y luego hacer estos cálculos, como indica Foobaz John. Pero, de hecho, todas estas manipulaciones son perfectamente válidas sin tener en cuenta la convergencia, si se plantean de la forma correcta, es decir, en términos de serie formal de potencias .

A serie formal de potencias no es más que una secuencia infinita arbitraria $(a_0, a_1, a_2, \ldots)$ de (digamos) números reales. Pero "decoramos" esta secuencia utilizando la notación $(a_0, a_1, a_2, \ldots ) = \sum_{k=0}^\infty a_k x^k$ . Nótese que aquí no utilizamos ninguna noción de convergencia. Sólo utilizamos la notación $$\sum_{k=0}^\infty a_k x^k$$ la secuencia $(a_0, a_1, a_2, \ldots)$ . En este contexto, sumas infinitas como $\sum_{k=0}^\infty k! x^k$ que no son convergentes en ninguna parte excepto $x=0$ están perfectamente bien, ya que sólo se refiere a la secuencia de números $(1,1,2,6,24, \ldots)$ .

Esto sería perfectamente inútil a menos que permitiéramos manipularlos de determinadas maneras. Así que hacemos las definiciones

$$\sum_{k=0}^\infty a_k x^k + \sum_{k=0}^\infty b_k x^k := \sum_{k=0}^\infty (a_k + b_k) x^k$$

$$(\sum_{k=0}^\infty a_k x^k ) \cdot ( \sum_{k=0}^\infty b_k x^k) := \sum_{k=0}^\infty \sum_{i=0}^k a_ib_{k-i} x^k. $$

Ahora puedes repasar y demostrar que se aplican todas las reglas habituales del álgebra, de modo que $F(G+H) = FG + FH$ , $(FG)H = F(GH)$ etc. para series de potencias formales $F,G,H$ . Esto significa que el conjunto de las series formales de potencias forma un anillo. A veces se puede dividir: es posible demostrar que $F = \sum_{k=0}^\infty a_k x^k$ tiene un inverso multiplicativo $G$ para que $FG = 1$ sólo si $a_0 \neq 0$ . (Aquí $1 := \sum_{k=0} b_k x^k$ donde $b_0 = 1$ , $b_k = 0$ para $k > 0$ .)

En el anillo de series de potencias formales todos estos cálculos son válidos.

Answer 2

Denote por $F_n$ el $n$ -ésimo número de Fibonacci $$ F_0=0,\qquad F_1=1,\qquad F_{n+2}=F_{n+1}+F_n $$ y considerar la serie $$ F=\sum_{n\ge0}F_nx^n $$ en el anillo de series de potencias formales con coeficientes en $\mathbb{R}$ . Este anillo tiene la propiedad de que cualquier serie $$ \sum_{n\ge0}a_nx^n $$ con $a_0\ne0$ es invertible. Su cálculo tiene lugar en esta estructura algebraica, donde la convergencia no es motivo de preocupación.

Podemos operar formalmente y escribir \begin{align} 1+xF+x^2F &=1+\sum_{n\ge0}F_nx^{n+1}+\sum_{n\ge0}F_nx^{n+2} \\[6px] &=1+\sum_{n\ge1}F_{n-1}x^n+\sum_{n\ge2}F_{n-2}x^n \\[6px] &=1+x+\sum_{n\ge2}(F_{n-1}+F_{n-2})x^n \\[6px] &=1+x+\sum_{n\ge2}F_nx^n \\[6px] &=F \end{align} así que $$ 1=(1-x-x^2)F $$ La serie de potencias formal $1-x-x^2$ (con términos de coeficiente cero para $x^n$ con $n\ge3$ ) es invertible, por lo que $$ F=(1-x-x^2)^{-1} $$ El resto es manipulación de elementos en el anillo de series de potencias, utilizando el hecho de que $$ (1-\alpha x)^{-1}=\sum_{n\ge0}\alpha^nx^n $$

Sin límite ni convergencia, sólo álgebra.

Answer 3

Se puede demostrar un límite como $F_n<2^n$ utilizando la inducción para que la serie de potencias sea convexa al menos para $|x|<1/2$ y las manipulaciones son válidas. De forma más general, para una recurrencia lineal con coeficientes constantes, el radio de convergencia de la serie de potencias resultante será el mínimo de los recíprocos de las raíces de la ecuación característica y, por tanto, la serie de potencias tendrá un radio de convergencia distinto de cero.