Alternative "Fibonacci" sequences and ratio convergence

Question

So the well known Fibonacci sequence is $$ F=\{1,1,2,3,5,8,13,21,\ldots\} $$ where $f_1=f_2=1$ and $f_k=f_{k-1}+f_{k-2}$ for $k>2$. The ratio of $f_k:f_{k-1}$ approaches the Golden Ratio the further you go: $$\lim_{k \rightarrow \infty} \frac{f_k}{f_{k-1}} =\phi \approx 1.618$$

Let's define a class of similar sequences $F_n$ where each $f_k$ is the sum of the previous $n$ numbers, $f_k=f_{k-1} + f_{k-2} + \dots + f_{k-n}$ so that the traditional Fibonacci sequence would be $F_2$ but we can talk about alternatives such as $$F_3 = \{1,1,1,3,5,9,17,\dots \}$$ where we initialized the values $f_1$ through $f_3$ to be $1$ and we can show that in this case $$ \lim_{k \rightarrow \infty} \frac{f_k}{f_{k-1}} \approx 1.839286755 $$ The following table gives some convergences for various values of $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{matrix} $$ Just by inspection, it seems that the convergence values are converging toward $2$ as $n \rightarrow \infty$.

So my primary question is: What is the proof that the convergence converges to 2 (assuming it does).

Answer 1

From the standard theory of linear recurrence,s $F_n$ is the positive real root of the equation $z^n = z^{n-1} + z^{n-2} + \cdots + z + 1$. Multiplying both sides by $1-z$ and rearranging, you get that $F_n$ is the positive real root of $f_n(z) = z^{n+1} - 2z^n + 1 = 0$ that is not $z = 1$. (By Descartes' rule of signs (https://en.wikipedia.org/wiki/Descartes%27_rule_of_signs), there are either 0 or 2 positive real roots of this polynomial; we know there is at least 1 , so there must be 2.)

Now, we have $$ f_n(2)= 2^{n+1} - 2 \cdot 2^{n} + 1 = 1 $$ and $$f_n(2 - 1/2^{n-1}) = (2 - 1/2^{n-1})^{n+1} - 2 \cdot (2-1/2^{n-1})^n + 1. $$ We aim to show that $f_n(2-1/2^{n-1}) < 0$; then $f_n$ must have a root between $2 - 1/2^{n-1}$ and $2$.

Factoring out powers of 2, we get $$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.$$ Factoring out $2^{n+1} (1-1/2^n)^n$ from the first two terms gives $$f_n(2 - 1/2^{n-1}) = 2^{n+1} (1-1/2^n)^n (-1/2^n) + 1$$ or, finally, $$f_n(2 - 1/2^{n-1}) = 1-2(1-1/2^n)^n. $$ So the result that $f_n$ has a root in the interval $[2-1/2^{n-1}, 2]$, for $n$ sufficiently large, follows from the fact that $(1-1/2^n)^n > 1/2$ for $n$ sufficiently large. Since $\lim_{n \to \infty} (1-1/2^n)^n = 1$ (use for example L'Hopital's rule) this follows.

Thus $F_n \in [2 - 1/2^{n-1}, 2]$ and the desired result follows, for example, from the squeeze theorem.