Alternativa "Fibonacci" secuencias y la relación de convergencia

Question

Así que la conocida secuencia de Fibonacci es $$ F=\{1,1,2,3,5,8,13,21,\ldots\} $$ donde$f_1=f_2=1$$f_k=f_{k-1}+f_{k-2}$$k>2$. La relación de $f_k:f_{k-1}$ enfoques de la Proporción áurea, más ir: $$\lim_{k \rightarrow \infty} \frac{f_k}{f_{k-1}} =\phi \approx 1.618$$

Vamos a definir una clase de secuencias similares a $F_n$ donde cada una de las $f_k$ es la suma de los anteriores $n$ números, $f_k=f_{k-1} + f_{k-2} + \dots + f_{k-n}$, de modo que la tradicional secuencia de Fibonacci sería $F_2$ pero podemos hablar de alternativas, tales como $$F_3 = \{1,1,1,3,5,9,17,\dots \}$$ donde inicializamos los valores de $f_1$ a través de $f_3$ $1$ y podemos mostrar que en este caso $$ \lim_{k \rightarrow \infty} \frac{f_k}{f_{k-1}} \approx 1.839286755 $$ La tabla siguiente da algunas convergencias para los distintos valores de $n$: $$ \begin{matrix} F_n & \text{Converges to} \\ \hline F_2 & \phi \\ F_3 & 1.839286755 \\ F_4 & 1.927561975 \\ F_5 & 1.965948237 \\ F_{6} & 1.983582843 \\ F_{10} & 1.999018626 \end{de la matriz} $$ Simplemente por inspección, parece que la convergencia de los valores están convergiendo hacia la $2$$n \rightarrow \infty$.

Así que mi pregunta principal es: ¿Cuál es la prueba de que la convergencia converge a 2 (suponiendo que sea).

Answer 1

De la teoría estándar de recurrencia lineal,s $F_n$ es el positivo de la raíz real de la ecuación de $z^n = z^{n-1} + z^{n-2} + \cdots + z + 1$. Multiplicando ambos lados por $1-z$ y reordenando, se obtiene que el $F_n$ es la verdadera raíz de la $f_n(z) = z^{n+1} - 2z^n + 1 = 0$ que no es $z = 1$. (Por Descartes' regla de los signos (https://en.wikipedia.org/wiki/Descartes%27_rule_of_signs), hay 0 o 2 reales positivos raíces de este polinomio; sabemos que hay al menos 1 , por lo que debe ser de 2.)

Ahora, tenemos $$ f_n(2)= 2^{n+1} - 2 \cdot 2^{n} + 1 = 1 $$ y $$f_n(2 - 1/2^{n-1}) = (2 - 1/2^{n-1})^{n+1} - 2 \cdot (2-1/2^{n-1})^n + 1. $$ Nuestro objetivo es demostrar que $f_n(2-1/2^{n-1}) < 0$; a continuación, $f_n$ debe tener una raíz entre $2 - 1/2^{n-1}$$2$.

Factorizando potencias de 2, obtenemos $$f_n(2 - 1/2^{n-1}) = 2^{n+1} (1-1/2^n)^{n+1} - 2^{n+1} (1-1/2^n)^n + 1.$$ Factorizando $2^{n+1} (1-1/2^n)^n$ a partir de los dos primeros términos de la da $$f_n(2 - 1/2^{n-1}) = 2^{n+1} (1-1/2^n)^n (-1/2^n) + 1$$ o, finalmente, $$f_n(2 - 1/2^{n-1}) = 1-2(1-1/2^n)^n. $$ Así, el resultado que $f_n$ tiene una raíz en el intervalo de $[2-1/2^{n-1}, 2]$ $n$ suficientemente grande, se sigue del hecho de que $(1-1/2^n)^n > 1/2$ $n$ lo suficientemente grande. Desde $\lim_{n \to \infty} (1-1/2^n)^n = 1$ (por ejemplo, utilizar la regla de L'Hospital) esta de la siguiente manera.

Por lo tanto $F_n \in [2 - 1/2^{n-1}, 2]$ y el resultado deseado de la siguiente manera, por ejemplo, del teorema del sándwich.