¿Es la convergencia superlinear, lineal y cuadrática?

Question

La secuencia de Fibonacci es generado por las fórmulas \begin{cases} r_0=1 & r_1=1\\ r_{n+1}=r_n+r_{n-1} \end{casos} La la secuencia, por tanto, comienza $1, 1, 2, 3, 5, 8, 13, 21, 34, \dots$. Demostrar que la secuencia de $[2r_n/r_{n-1}]$ converge a $1+\sqrt{5}$. Es la convergencia lineal, signos diacríticos, cuadrática?

Prueba: Supongamos que tenemos la siguiente relación de recurrencia $$r_{n+1}=r_n+r_{n-1},$$ where $r_0=1$ and $r_1=1$. We want to show that the sequence $[2r_n/r_{n-1}]$ converges to $1+\sqrt{5}$. i.e. We want to show that $$\lim_{n\to \infty} \dfrac{2r_n}{r_{n-1}}=1+\sqrt{5}.$$ Antes, se demuestra que este límite es cierto, tenemos que encontrar la solución a esta recurrencia relación con las condiciones iniciales.

El correspondiente polinomio característico de la relación de recurrencia es $$p(\lambda)=\lambda^2-\lambda-1=0.$$ Hence the roots of the characteristic polynomial are $\lambda=\dfrac{1\pm\sqrt{5}}{2}$. Hence the general solution for the relation is $$r_n=A\left(\dfrac{1+\sqrt{5}}{2}\right)^n+B\left(\dfrac{1-\sqrt{5}}{2}\right)^n.$$

A continuación, queremos encontrar los valores de $A$ $B$ con las condiciones iniciales. Con los valores iniciales $r_0=1$$r_1=1$, se obtiene el siguiente sistema de ecuaciones: \begin{cases} 1=r_0=A+B \\ 1=r_1=A\left(\dfrac{1+\sqrt{5}}{2}\right)+B\left(\dfrac{1-\sqrt{5}}{2}\right) \end{casos}

Multiplicar la primera ecuación por $\dfrac{1+\sqrt{5}}{2}$. \begin{cases} \dfrac{1+\sqrt{5}}{2}=r_0=A\left(\dfrac{1+\sqrt{5}}{2}\right)+B\left(\dfrac{1+\sqrt{5}}{2}\right) \\ 1=r_1=A\left(\dfrac{1+\sqrt{5}}{2}\right)+B\left(\dfrac{1-\sqrt{5}}{2}\right) \end{casos}

A continuación, reste la ecuación (1) de la ecuación (2), que los resultados con $$\dfrac{\sqrt{5}=1}{2}=B\sqrt{5} \iff B=\dfrac{\sqrt{5}-1}{2\sqrt{5}}.$$ Además $$A=1-\dfrac{\sqrt{5}-1}{2\sqrt{5}}=1-\dfrac{\sqrt{5}}{2\sqrt{5}}+\dfrac{1}{2\sqrt{5}}=1-\dfrac{1}{2}+\dfrac{1}{2\sqrt{5}}=\dfrac{1}{2}+\dfrac{1}{2\sqrt{5}}=\dfrac{\sqrt{5}+1}{2\sqrt{5}}.$$ Por lo tanto, la solución general de la relación es \begin{equation*} \begin{aligned} r_n & =\left(\dfrac{\sqrt{5}+1}{2\sqrt{5}}\right)\left(\dfrac{1+\sqrt{5}}{2}\right)^n+\left(\dfrac{\sqrt{5}-1}{2\sqrt{5}}\right)\left(\dfrac{1-\sqrt{5}}{2}\right)^n \\ & =\dfrac{1}{\sqrt{5}}\left[\dfrac{(1+\sqrt{5})^{n+1}-(1-\sqrt{5})^{n+1}}{2^{n+1}}\right]. \end{aligned} \end{ecuación*}

Ahora podemos demostrar que la secuencia de $[2r_n/r_{n-1}]$ converge a $1+\sqrt{5}$. \begin{equation*} \begin{aligned} \lim_{n\to \infty} \dfrac{2r_n}{r_{n-1}} & = \lim_{n\to \infty} \dfrac{\dfrac{2}{\sqrt{5}}\left[\dfrac{(1+\sqrt{5})^{n+1}-(1-\sqrt{5})^{n+1}}{2^{n+1}}\right]}{\dfrac{1}{\sqrt{5}}\left[\dfrac{(1+\sqrt{5})^{n}-(1-\sqrt{5})^{n}}{2^{n}}\right]} \\ & = \lim_{n\to \infty} \dfrac{(1+\sqrt{5})^{n+1}-(1-\sqrt{5})^{n+1}}{(1+\sqrt{5})^{n}-(1-\sqrt{5})^{n}} \\ & = \lim_{n\to \infty} \dfrac{\dfrac{(1+\sqrt{5})^{n+1}-(1-\sqrt{5})^{n+1}}{(1+\sqrt{5})^n}}{\dfrac{(1+\sqrt{5})^{n}-(1-\sqrt{5})^{n}}{(1+\sqrt{5})^n}} \\ & = \lim_{n\to \infty} \dfrac{(1+\sqrt{5})-(1-\sqrt{5})\cdot \left(\dfrac{1-\sqrt{5}}{1+\sqrt{5}}\right)^{n}}{1-\left(\dfrac{1-\sqrt{5}}{1+\sqrt{5}}\right)^{n}} \\ & = \dfrac{(1+\sqrt{5})-(1-\sqrt{5})\cdot 0}{1-0} \\ & = 1+\sqrt{5}. \end{aligned} \end{ecuación*}

Nota: Desde $0<\dfrac{1-\sqrt{5}}{1+\sqrt{5}}<1$, $$\lim_{n\to\infty} \left(\dfrac{1-\sqrt{5}}{1+\sqrt{5}}\right)^{n}=0.$$

Para finalizar la pregunta que me deben decir si la convergencia es lineal, signos diacríticos, o cuadrática. Sé que

• Si el límite es igual a 0, entonces la convergencia es signos diacríticos.
• Si el límite es igual a 1, entonces la convergencia es lineal.
• Si el límite es igual a 2, entonces la convergencia es cuadrática.

Sin embargo, mi límite es igual a $1+\sqrt{5}$. Me estoy perdiendo algo?

Answer 1

Tratando de igualar su notación: Vamos a $r_n$ representan el $n$'ésimo número de Fibonacci, vamos a $q_n=\frac{2r_n}{r_{n-1}}$, y deje $L=1+\sqrt{5}$

En la primera parte del problema, usted debe han mostrado $\lim\limits_{n\to\infty}q_n=L$

Ahora investigar qué ocurre con el límite de:

$$(\dagger):~~~~~~~~~\lim\limits_{n\to\infty}\frac{|q_{n+1}-L|}{|q_{n}-L|}$$

$q_{n+1}$ tiende a estar más cerca de a $L$ $q_{n}$ lo que implica que $|q_{n+1}-L|<|q_{n}-L|$ lo que implica que el límite de $(\dagger)$ por encima de la voluntad, si es que existe en algún lugar en el rango de $[0,1]$. Si el límite es $1$ nos dicen que $q_n$ converge a $L$ "sublinearly", si el límite es de entre $0$ $1$ nos dicen que $q_n$ converge a $L$ "linealmente", y si el límite es $0$ nos dicen que $q_n$ converge a $L$ "superlinearly." En el caso de que se sublinear o signos diacríticos, podemos clasificar más de lo rápido o lento que es elevar el denominador a diferentes potencias y la investigación de los límites.

Ahora... una vez más, nos ha encomendado la tarea de investigar el límite de $(\dagger)$. Recordar que $q_n=\frac{2r_n}{r_{n-1}}$ y $r_n=\frac{\varphi^n-\psi^n}{\sqrt{5}}$ donde$\varphi=\frac{1+\sqrt{5}}{2}$$\psi=\frac{1-\sqrt{5}}{2}$. Observe que $\frac{L}{2}=\varphi$ y $\varphi\cdot \psi=-1$.

Tenemos entonces $q_n=2\cdot \frac{\varphi^n-\psi^n}{\varphi^{n-1}-\psi^{n-1}}$. Ahora tenemos $q_{n+1}-L=2\cdot \frac{\varphi^{n+1}-\psi^{n+1}-\varphi(\varphi^n-\psi^n)}{\varphi^n-\psi^n}$

$=2\cdot \frac{\varphi^{n+1}-\psi^{n+1}-\varphi^{n+1}-\psi^{n-1}}{\varphi^n-\psi^n}=2\cdot \frac{-\psi^{n+1}-\psi^{n-1}}{\varphi^n-\psi^n}$

De igual manera debemos calcular el $q_{n}-L$ $2\cdot \frac{-\psi^n-\psi^{n-2}}{\varphi^{n-1}-\psi^{n-1}}$

Como una comprobación de validez de aquí, aviso que $\lim\limits_{n\to\infty}|q_n-L|=0$ como el numerador tiende a cero, mientras que el denominador crece grande. Esto confirma, o más bien rederives, lo que debería haber aprendido en la primera parte de la pregunta.

Así que esto nos lleva a nuestro límite de $(\dagger)$ ser:

$\lim\limits_{n\to\infty}\frac{|q_{n+1}-L|}{|q_n-L|}=\lim\limits_{n\to\infty}\frac{|2\cdot \frac{-\psi^{n+1}-\psi^{n-1}}{\varphi^n-\psi^n}|}{|2\cdot \frac{-\psi^n-\psi^{n-2}}{\varphi^{n-1}-\psi^{n-1}}|}=$

Que después de un poco más de álgebra y un poco de handwaving resultados en

$\frac{\frac{|\psi^2+\psi|}{|\psi+1|}}{\varphi}=\frac{|\psi|}{\varphi}=\frac{\sqrt{5}-1}{1+\sqrt{5}}\approx 0.382$

El handwaving entra en juego cuando se intenta mover las diferentes partes de la fracción para obtener como grupos juntos. El grupo de la forma $\frac{\varphi^n-\psi^n}{\varphi^{n-1}-\psi^{n-1}}$ nosotros aviso que como $\lim\limits_{n\to\infty}\psi^n=0$ los únicos términos que realmente sobreviven son las $\varphi'$s. Esto puede ser más formal, pero esto es suficiente por ahora.

I. e. el doble de la proporción de consecutivos de fibonacci términos converge a $L$ lineal.