So the well known Fibonacci sequence is
F={1,1,2,3,5,8,13,21,…}
where f1=f2=1 and fk=fk−1+fk−2 for k>2. The ratio of fk:fk−1 approaches the Golden Ratio the further you go:
lim
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