11
$\begingroup$

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).

$\endgroup$
  • 1
    $\begingroup$ Changing the initial conditions will not affect the limit. Use $a_0=a_1=\dots=a_{k-3}=0$ and $a_{k-2}=a_{k-1}=1$, and see if the result is more obvious. $\endgroup$ – Bonnaduck Apr 13 '16 at 19:02
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.