Tuesday, 13 February 2018

Alternative "Fibonacci" sequences and ratio convergence



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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...