Demostrar esta fórmula para la Secuencia de Fibonacci

Question

Esta fórmula proporciona la $n$th término en la Secuencia de Fibonacci, y se define mediante la repetición de la fórmula: $u_n = u_{n − 1} + u_{n − 2}$ $n > 1$ donde$u_0 = 0$$u_1 = 1$.

Mostrar que

$$u_n = \frac{(1 + \sqrt{5})^n - (1 - \sqrt{5})^n}{2^n \sqrt{5}}.$$

Por favor me ayudan con su prueba. Gracias.

Answer 1

SUGERENCIA $\rm\quad\ u_n =\: x^n\ \iff\ 0\ =\ x^{n+2}\:-\:x^{n+1}\:-\:x^n\ =\ (x^2-x-1)\ x^n\ =:\ f(x)\ x^n\:.\:$

Por lo tanto, podemos deducir que los $\rm\ \phi^{\ n}\:$ $\rm\ \bar\phi^{\ n}\:$ son soluciones, donde $\rm\:\phi,\ \bar\phi\:$ son las raíces de $\rm\:f(x)\:.$

Por lo tanto, por la linealidad $\rm\ g_n =\: c\ \phi^{\:n} +d\ \bar\phi^{\:n}\ $ también es una solución, para cualquier constantes $\rm\: c,\:d\:.$

Por inducción, las soluciones están unívocamente determinados por sus condiciones iniciales $\rm\:u_0,\:u_1,\:$ por lo tanto

$\begin{array}{rl} \qquad\qquad\rm g_n =\: f_n\!\! &\iff\quad\begin{array}{}\rm 0\: =\: f_0 =\: g_0 =\: c+d \\ \rm 1\: =\: f_1 =\: g_1 =\: c\ \phi + d\ \bar\phi\end{de la matriz} \\ &\ffi\quad\rm d = {-}c,\quad c\: =\: \dfrac{1}{\phi-\bar\phi} \\ &\ffi\quad\rm g_n =\: \dfrac{\phi^{\:n}-\bar\phi^{\:n}}{\phi\ -\ \bar\phi\ \ \ } \end{array}$

Este es un ejemplo prototípico de la potencia de los teoremas de singularidad para probar las igualdades. Aquí la unicidad teorema es que, por lineal de ecuaciones de diferencia (es decir, las recurrencias). Mientras que aquí la unicidad teorema tiene un trivial de una línea de prueba por inducción, en otros contextos, tales teoremas de singularidad puede ser mucho menos menos trivial (por ejemplo, para ecuaciones diferenciales). Como tales, pueden proporcionar una gran potencia para la demostración de la igualdad. Por ejemplo, algunos de mis anteriores posts.

Answer 2

Vamos catálogo de algunas de esas sugerencias en los comentarios. En primer lugar, permítanme reescribir la fórmula de Binet en una forma más conveniente:

$$F_n=\frac1{\sqrt{5}}(\phi^n-(-\phi)^{-n})$$

donde $\phi=\frac12(1+\sqrt5)$ es la proporción áurea.

1) Verificar la fórmula de Binet satisface la relación de recursividad. En primer lugar, podemos comprobar que la fórmula de Binet da la respuesta correcta para $n=0,1$. Lo único que se necesita ahora es sustituir la fórmula en la diferencia de la ecuación de $u_{n+1}-u_n-u_{n-1}=0$. Usted, a continuación, obtener

$$(-\phi)^{-n+1}+(-\phi)^{-n}-(-\phi)^{-n-1}+\phi^{n+1}-\phi^n-\phi^{n-1}=0$$

Podemos hacer algo de factoring:

$$-(-\phi)^{-n-1}(\phi^2-\phi-1)+\phi^{n-1}(\phi^2-\phi-1)=0$$

y ya sabemos que $\phi^2-\phi-1=0$, la fórmula de Binet es verificada.

2) la Solución de la ecuación característica. Uno puede asociar con el lineal a diferencia de la ecuación de $u_{n+1}-au_n-bu_{n-1}=0$ la ecuación característica $x^2-ax-b=0$. Si las dos raíces de la ecuación característica son $x_1$$x_2$, las soluciones de la diferencia de la ecuación toma la forma $u_n=px_1^n+qx_2^n$.

Para el Fibonacci de recurrencia, $a=b=1$, y las raíces de $x^2-x-1=0$$\phi$$1-\phi=-\phi^{-1}$. Por lo tanto, $F_n$ es expresable como la

$$F_n=p\phi^n+q(-\phi)^{-n}$$

Podemos resolver para $p$ $q$ utilizando las condiciones iniciales $F_0=0,F_1=1$. Esto le da a las dos ecuaciones

$$\begin{align*}p+q&=0\\p\phi+q(1-\phi)&=1\end{align*}$$

con las soluciones de $p=-q=\frac1{\sqrt{5}}$. La sustitución de que en el anteproyecto de expresión para $F_n$ los rendimientos de la fórmula de Binet.

Answer 3

El uso de funciones de generación a la Wilf del "generatingfunctionology". Definir el ordinario de la generación de la función: $$ F(z) = \sum_{n \ge 0} F_n z^n $$ El Fibonacci de recurrencia es: $$ F_{n + 2} = F_{n + 1} + F_n \qquad F_0 = 0, F_1 = 1 $$ La aplicación de las propiedades de la ordinaria de la generación de la función: $$ \frac{F(z) - F_0 - F_1 z}{z^2} = \frac{F(z) - F_0}{z} + F(z) $$ La solución a esta ecuación como fracciones parciales es: $$ F(z) = \frac{z}{1 - z - z^2} = \frac{1}{\sqrt{5}}\cdot \left( \frac{1}{1 - \phi z} - \frac{1}{1 - \bar{\phi} z} \right) $$ Aquí $\phi = \frac{1}{2} (1 + \sqrt{5})$ $\bar{\phi} = \frac{1}{2}(1 - \sqrt{5})$ son las raíces de $r^2 - r - 1$. Esto es sólo dos series geométricas: $$ F_n = \frac{1}{\sqrt{5}}(\phi^n - \bar{\phi}^n) $$

Answer 4

Como alternativa, puede utilizar la recursividad lineal diferencia de la fórmula. Esto funciona para cualquier recursividad lineal (es decir, una recursividad en la forma $a_n=qa_{n-1}+ra_{n-2}$.

Paso 1 para la forma cerrada de la linealidad de la recursividad: Encontrar las raíces de la ecuación de $x^2=qx+r$. Para Fibonnaci, esta fórmula es $x^2=x+1$. Las raíces se $\frac{1\pm\sqrt5}2$.

Paso 2: La forma cerrada es en la forma $a(n)=g\cdot\text{root}_1^n+h\cdot\text{root}_2^n$. Por Fibonacci, esta rendimientos $a_n=g(\frac{1+\sqrt5}2)^n+h(\frac{1-\sqrt5}2)^n$.

Paso 3: Resolver para$g$$h$. Todo lo que tienes que saber hacer es conectar dos valores conocidos de la secuencia en esta ecuación. Por fibonacci, consigue $g=h=1/\sqrt5$. Listo!