Prueba de que la proporción de dos números de Fibonacci consecutivos converge a la proporción de oro por inducción

Question

$$\varphi = \frac{1 + \sqrt{5}}{2}$$

Queremos demostrar que la relación de dos números de Fibonacci consecutivos enfoques $\varphi$ por inducción y también la utilización de Newton-Raphson método para aproximar $\sqrt{5}$ como un número racional con relativamente primer numeradores y denominadores.

Primero vamos a definir la Secuencia de Fibonacci y, a continuación, escriba lo que queremos demostrar el uso de la notación simbólica.

$$\phi_1,\phi_2 = 1$$ $$\phi_{n+2} = \phi_{n+1} + \phi_{n}$$ $$1 \le n$$

$$n \to \infty \Rightarrow \frac{\phi_{n+1}}{\phi_{n}} \to \varphi$$

En primer lugar tenemos aproximaciones racionales de los irracionales número $\sqrt{5}$, por lo que podemos conectarlo a enteros:

$$x_{n} = \frac{a_{n}}{b_{n}}$$

$$x_{1} = \frac{2}{1} = \frac{a_1}{b_1}$$

Donde el límite de $n$ va al infinito es $\sqrt{5}$. De acuerdo con el método de Newton-Raphson método podemos escribir que,

$$x_{n+1} = x_n - \frac{F(x_n)}{F'(x_n)} = \frac{x_n^2 + 5}{2x_n}$$

La sustitución de la $\frac{a_n}{b_n}$ e $\frac{a_{n+1}}{b_{n+1}}$ , respectivamente, a los lugares de $x_n$ e $x_{n+1}$ nos aparecerá el siguiente número racional con el entero numerador y el denominador,

$$\frac{a_{n+1}}{b_{n+1}} = \frac{a_n^2 + 5b_n^2}{2a_nb_n}$$

Así que

$$a_{n+1} = a_n^2 + 5b_n^2$$ $$b_{n+1} = 2a_nb_n$$

Vamos a definir

$$\varphi_n = \frac{1 + \frac{a_n}{b_n}}{2} = \frac{a_n + b_n}{2b_n}$$

$$n \to \infty \Rightarrow \varphi_{n} \to \varphi$$

Para $n = 1$ (el primer caso):

$$\varphi_1 = \frac{1 + \frac{2}{1}}{2} = \frac{3}{2}$$

El numerador y el denominador son dos números de Fibonacci consecutivos, respectivamente, el $\phi_4$ e $\phi_3$. Ahora aquí va nuestra hipótesis de inducción para $1 \le n$:

si el numerador y el denominador de $\varphi_n$ son dos números de Fibonacci consecutivos, respectivamente, $\phi_{3\cdot2^{n - 1} + 1}$ e $\phi_{3\cdot2^{n - 1}}$ (como $\phi_{4}$ e $\phi_{3}$ son), entonces el numerador y el denominador de $\varphi_{n+1}$ será de nuevo dos números de Fibonacci consecutivos, respectivamente, $\phi_{3\cdot2^{n} + 1}$ e $\phi_{3\cdot2^{n}}$.

$$\varphi_1 = \frac{3}{2} = \frac{\phi_4}{\phi_3} = \frac{\phi_{3\cdot2^{0} + 1}}{\phi_{3\cdot2^{0}}}$$ $$\varphi_2 = \frac{13}{8} = \frac{\phi_7}{\phi_6} = \frac{\phi_{3\cdot2^{1} + 1}}{\phi_{3\cdot2^{1}}}$$ $$\varphi_3 = \frac{233}{144} = \frac{\phi_{13}}{\phi_{12}} = \frac{\phi_{3\cdot2^{2} + 1}}{\phi_{3\cdot2^{2}}}$$ $$...$$ Si podemos demostrar que, vamos a ser demostrado que el cociente de dos números de Fibonacci consecutivos enfoques $\varphi$, por supuesto, si yo no tengo ningún error aquí.

Aquí está nuestra suposición:

$$\varphi_n = \frac{a_n + b_n}{2b_n} = \frac{\phi_{3\cdot2^{n - 1} + 1}}{\phi_{3\cdot2^{n - 1}}}$$

Y aquí es lo que queremos demostrar (i reescrito y manipular la declaración utilizando las definiciones anteriores de $a_{n+1}$ e $b_{n+1}$):

$$\varphi_{n+1} = \frac{(a_n + b_n)^2 + (2b_n)^2 }{(2b_n)^2} = \frac{\phi_{3\cdot2^{n} + 1}}{\phi_{3\cdot2^{n}}}$$

$$\varphi_{n+1} = \varphi_{n}^2 + 1 = \frac{\phi_{3\cdot2^{n} + 1}}{\phi_{3\cdot2^{n}}}$$

Esto se hace realmente complicado para mí después de este punto. Alguien podría por favor darme consejos o señalar mis errores si los hay?

Answer 1

Esta es sólo una sugerencia:

De $F_{n+1}=F_n+F_{n-1}$, definir la relación como

$r_{n+1}=\frac{F_{n+1}}{F_n}=1+\frac{F_{n-1}}{F_n}=1+\frac{1}{r_n}$

Hay un par de cosa que hacer ahora, por ejemplo, para mostrar que $r_n$ converge. Una vez que está hecho, el límite debe satisfacer $$x=1+\frac{1}{x}$$ el que tiene la media de oro como solución.

Observe también que $$\begin{bmatrix} F_{n+1}\\ F_n \end{bmatrix} =\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_n\\ F_{n-1} \end{bmatrix}$$ Y repitiendo n veces que se $$\begin{bmatrix} F_{n+1}\\ F_n \end{bmatrix} =\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} F_1\\ F_0 \end{bmatrix}$$

El uso de la diagonal de la descomposición de la matriz de involucrar a obtener de nuevo en algo relacionado a la media de oro.

Answer 2

Con $\phi_n:=\dfrac{F_{n+1}}{F_n}$,

$$F_{n+2}=F_{n+1}+F_n\iff \phi_{n+1}=1+\frac1{\phi_{n}}.$$

Entonces, si la secuencia de $\phi_n$ converge, se converge a una raíz de

$$p=1+\frac1p.$$

Como todos los términos son positivos, la convergencia se debe a la positiva de la raíz.

---

Como se puede observar, la $\phi_n$ se alternan en torno a $\phi$ y acercando más y más. Podemos demostrar que

$$|\phi_{n+1}-\phi|<|\phi_n-\phi|.$$

De hecho

$$|\phi_{n+1}-\phi|=\left|1+\frac1{\phi_{n}}-\phi\right|=\left|\frac1{\phi_{n}}-\frac1\phi\right|=\frac{|\phi_n-\phi|}{\phi_{n}\phi}<|\phi_n-\phi|.$$

Como $\phi_n>1$, entonces la distancia a $\phi$ es de al menos dividido por $\phi$ (de hecho casi $\phi^2$) en cada iteración, y lineal, la convergencia está garantizada.