Suma de los números de Fibonacci.

Question

Dejemos que $f_n$ sea la secuencia de números de Fibonacci. Tenemos que demostrar que

$$\sum_{n\ge0} f_n x^n = \dfrac{1}{1-x-x^2}$$

Recuerdo una solución cuando estamos utilizando las funciones de generación como:

$f(x) = F_0 + F_1x + F_2 x^2 + F_3x^3$ A continuación, multiplique por $x$ y $x^2$ ambos lados y obtener $(1-x-x^2)f(x) = F_0 + (F_1-F_0)x=x$ y el resultado es el siguiente.

Sin embargo, no entiendo muy bien cómo funciona esto. También me gustaría llegar a expresiones similares para $\sum_{n\ge0} f_{2n} x^n$ y $\sum_{n\ge0} f_{2n+1} x^n$ .

Answer 1

He aquí una mirada no tan rigurosa a la cuestión.

Los números de Fibonacci se definen por la relación

$$f_{n+2}=f_{n+1}+f_{n}$$

Multiplicando por $x^{n+2}$ en ambos lados, obtenemos

$$f_{n+2}x^{n+2}=x\times f_{n+1}x^{n+1}+x^2\times f_{n}x^{n}$$

Sumando como $n$ va de cero a infinito, tenemos

$$\sum ^\infty _{n=0} f_{n+2}x^{n+2}=x\times \sum ^\infty _{n=0} f_{n+1}x^{n+1}+x^2\times \sum ^\infty _{n=0} f_{n}x^{n}$$

Podemos reescribirlo como

$$\left(\sum ^\infty _{n=0} f_{n}x^{n}-f_{1}x-f_{0}\right)=x\times \left(\sum ^\infty _{n=0} f_{n}x^{n}-f_{0}\right)+x^2\times \sum ^\infty _{n=0} f_{n}x^{n}$$

Reordenando la ecuación, tenemos

$$\sum ^\infty _{n=0} f_{n}x^{n}(1-x-x^2)=x(f_0+f_1)+f_0$$

De lo que se deduce el resultado.

Answer 2

\begin{align} g(x) & = \dfrac1{1-x-x^2} = \sum_{k=0}^{\infty} (x+x^2)^k = \sum_{k=0}^{\infty} x^k(1+x)^k = \sum_{k=0}^{\infty}x^k \sum_{l=0}^k \dbinom{k}l x^l\\ & = \sum_{k=0}^{\infty} \sum_{l=0}^k \dbinom{k}l x^{k+l} = \sum_{m=0}^{\infty}x^m \left(\sum_{l=0}^m \dbinom{m-l}l\right) = \sum_{m=0}^{\infty} g_{m+1} x^m \end{align} Ahora utiliza el hecho de que $$\dbinom{n}r + \dbinom{n}{r+1} = \dbinom{n+1}{r+1}$$ para concluir que $$g_{m+1} = g_m + g_{m-1}$$ con $g_1 = 1$ , $g_0 = 0$ .

Answer 3

$$\begin{array}{r|cccccccc}\color{Red}{1}f(x) & \color{Red}{F_0} & + & \color{Red}{F_1}x & + & \color{Red}{F_2}x^2 & + & \color{Red}{F_3}x^3 & \cdots \\ \hline \color{Green}{x}f(x) & & & \color{Green}{F_0}x & + & \color{Green}{F_1}x^2 & + & \color{Green}{F_2}x^3 & \cdots \\ \hline \color{Blue}{x^2}f(x) & & & & & \color{Blue}{F_0}x^2 & + & \color{Blue}{F_1}x^3 & \cdots \\ \hline (\color{Red}{1}-\color{Green}{x}-\color{Blue}{x^2})f(x) & \color{Red}{F_0} & + & (\color{Red}{F_1}-\color{Green}{F_0})x & + & (\color{Red}{F_2}-\color{Green}{F_1}-\color{Blue}{F_0})x^2 & + & (\color{Red}{F_3}-\color{Green}{F_2}-\color{Blue}{F_1})x^3 & \cdots \\\end{array}$$

Esto es $F_0+(F_1-F_0)x+0+0+\cdots=x$ ya que $F_{n+2}-F_{n+1}-F_n=0$ para todos $n\ge0$ . Una vez que se llega a la ecuación funcional $(1-x-x^2)F(x)=x$ , se divide para la forma cerrada de $F(x)$ .

Para las funciones generadoras de $F_{2n}$ y $F_{2n+1}$ , tal vez podría utilizar identidades como

$$F_{2n}=\sum_{k=1}^nF_{2k-1} \qquad F_{2n+1}=1+\sum_{k=1}^nF_{2k}.$$

Sin embargo, en mi opinión, para los tres GFs sería más fácil utilizar simplemente la fórmula de Binet

$$F_n=\frac{\varphi^n-\bar{\varphi}^n}{\varphi~-~\bar{\varphi}\,},\qquad \varphi,\bar{\varphi}=\frac{1\pm\sqrt{5}}{2}.$$

Una forma de demostrar la fórmula de Binet es con álgebra lineal, pero otra forma es demostrarla usando la misma función generadora que acabamos de ver (y usando la descomposición de fracciones parciales), y en este último caso no es aplicable al GF original pero después puede seguir usándose para los otros dos.