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
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.
No comments:
Post a Comment