9
$\begingroup$

For general Fibonacci sequence with $F_1=F_2=1$,

It is known that limit of $\frac {F_{n+1}} {F_n} $ exists.

I am wondering what this limit implies and why it is important to compare these two sequences.

Thanks

$\endgroup$
  • 5
    $\begingroup$ I tis not in the nature of limits to imply, and there are no two sequences being compared (unless you mean the Fibonacci sequence and the same sequence shifted one place). $\endgroup$ – Marc van Leeuwen Nov 24 '17 at 12:39
24
$\begingroup$

One reason to be interested in $\frac{F_{n+1}}{F_n}$ and its limit, is that it is a rational number which gives a good approximation to the golden ratio $\phi$ (which is irrational). In fact, in a way, this is the best rational approximation to $\phi$. Understanding why leads to the fascinating topic of continued fractions. The continued fraction expansion of $\phi$ is

$$ \phi = 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1+\ldots}}}. $$

If you truncate this fraction after $n-1$ divisions you get the $n$-th convergent. The first convergent of $\phi$ is $1$, the second one is $1 + \frac{1}{1} = 2$, the third is $1 + \frac{1}{1 + \frac{1}{1}} = \frac{3}{2}$, the fourth is $1 + \frac{1}{1 + \frac{1}{1+\frac{1}{1}}} = \frac{5}{3}$.

Hopefully you see the pattern: using induction you can show that the $n$-th convergent is $\frac{F_{n+1}}{F_n}$. The neat thing is that a basic theorem about continued fractions shows that if $\frac{p}{q}$ is the $n$-th convergent of the continued fraction of a number $x$, then any other rational number $\frac{r}{s}$ with $s \le q$ is a worse approximation to $x$. I.e. for all $r$ and all $s \le q$, we have

$$ \left|x - \frac{p}{q}\right| \le \left|x - \frac{r}{s}\right|. $$

So, not only $\frac{F_{n+1}}{F_n}$ is a rational sequence that converges to $\phi$, but in fact it converges as fast as possible, in a certain precise sense.

Additionally, as noted in a comment, because all terms in the continued fraction expansion of $\phi$ are $1$, $\phi$ is the hardest irrational to approximate. This is the essence of Hurwitz's inequality.

$\endgroup$
  • 1
    $\begingroup$ Interesting to me, is that the ratio of successive terms is alternately more and less than $\phi$ rather than approaching $\phi$ from one direction or the other. In a series which has alternating sign on each term (such as the Maclaurin series for cosine) it would be expected. $\endgroup$ – Weather Vane Nov 24 '17 at 7:39
  • 9
    $\begingroup$ You should also mention that because of all those 1s in the continued fraction that in a sense $\phi$ is the most irrational number because its continued fraction has the slowest possible convergence. $\endgroup$ – PM 2Ring Nov 24 '17 at 12:13
  • 2
    $\begingroup$ @PM2Ring This is a good point: $\frac{F_{n+1}}{F_n}$ is the best rational approximation to the hardest irrational to approximate. $\endgroup$ – Sasho Nikolov Nov 24 '17 at 19:16
13
$\begingroup$

The existence of the limit reflects the fact that the Fibonacci sequence is essentially a geometric sequence (it is actually a linear combination of two geometric sequences but one of them dominates the other). See Wikipedia.

$\endgroup$
  • $\begingroup$ Yep, so in fact, we could use this knowledge to say that the Fibonacci numbers are growing in $\Theta(\phi^n)$. That way, if there is an algorithm where a Fibonacci like pattern shows up, we know that it is an exponential algorithm. Or if there is a combinatorial problem whose answer involves Fibonacci numbers, we could give some assymptotics for it. $\endgroup$ – Agnishom Chattopadhyay Nov 24 '17 at 16:11
4
$\begingroup$

The recurrence $F_{i+2}=F_i+F_{i+1}$ gives rise to a simple recurrence relation for the ratio of successive terms $\frac{F_{i+1}}{F_i}\in\Bbb R\cup\{\infty\}$, namely $\frac{F_{i+2}}{F_{i+1}}=\frac{F_i}{F_{i+1}}+\frac{F_{i+1}}{F_{i+1}}=(\frac{F_{i+1}}{F_i})^{-1}+1$, which is of order$~1$. The dynamics of the map $x\mapsto x^{-1}+1$ on $\Bbb R\cup\{\infty\}$ is quite simple: the map has two fixed points $\frac{1+\sqrt5}2$ and $\frac{1-\sqrt5}2$, of which the first is attractive, ad the second is repulsive. For any sequence satisfying the recursion and with initial ratio not exactly equal to the second fixed point, the ratio of successive terms will converge to the the first fixed point as $n\to\infty\,$; this is in particular the case for the Fibonacci sequence.

$\endgroup$
1
$\begingroup$

Let $f_n$ be the original Fibonacci sequence ($f_0=0,f_1=1$). Then any sequence $F$ defined as $$F_1=a\\F_2=b\\F_{n+2}=F_{n+1}+F_n$$ can be written as $$F_n=\frac{(3a-b)f_n-(a-b)L_n}2$$ where $L_n$ is $n$-th Lucas number. Now, knowing that Fibonacci sequence is recurrence equation, it can be solved like this: $$x^2=x+1\implies x_{1,2}=\frac{1\pm\sqrt5}2$$ Now, we can use these solutions to construct the solution for our recurrent equation (se "how to solve recurrent equation" article on Wikipedia): $$f_n=\frac{x_1^n-x_2^n}{x_1-x_2}$$ Knowing it, you will see that $F$ is always an exponential sequence and therefore limit of it's two consecutive elements always exists.

$\endgroup$
  • $\begingroup$ You final formula is wrong: the denominator should be $x_1-x_2=\sqrt5$, not $x_1+x_2=1$. But in any case this has nothing to do with what comes before, the "therefore" is completely incomprehensible. $\endgroup$ – Marc van Leeuwen Nov 24 '17 at 16:50
  • $\begingroup$ @MarcvanLeeuwen. Thank you very much for pointing that out. Plus sign instead of minus sign was just a typo. I also updated the above sentence and explained that it is a part from the algorithm for solving recurrent equations. Hope it is better now. If you have any other suggestions, just let me know and I'll update the post accordingly. Thanks! $\endgroup$ – user499203 Nov 24 '17 at 17:34
  • $\begingroup$ @MarcvanLeeuwen. BTW, I would suggest you to reconsider your vote, as the question is now updated and the typo is fixed. $\endgroup$ – user499203 Nov 24 '17 at 18:20
  • $\begingroup$ @ThePirateBay voting is anonymous, you cannot associate votes with comments unless the commenter explicity says so. $\endgroup$ – Weather Vane Nov 24 '17 at 19:49
  • $\begingroup$ @ThePirateBay Since you insist, I shall reconsider the rewritten answer. It has three parts. First a general solution $F_n$ of the recurrence is written as a linear combination of two particular solutions $f_n$ and $L_n$ (not surprising for a linear relation of order$~2$). Then a fresh quadratic equation in a fresh quantity $x$ is solved, correctly. Finally the general form of $f_n$ is expressed in terms of the solutions to that equation, but with no explanation of a relation to the equation, and referring to Wikipedia for an explanation. The parts are not logically related at all. $\endgroup$ – Marc van Leeuwen Nov 25 '17 at 7:38
0
$\begingroup$

Denote the limit with $L$. Then: $$\lim_{n\to\infty} \frac{F_{n+1}}{F_n}=L \Rightarrow \lim_{n\to\infty} \frac{1}{\frac{F_{n+2}-F_{n+1}}{F_{n+1}}}=L \Rightarrow \frac{1}{L-1}=L \Rightarrow L=\frac{1+\sqrt{5}}{2}=\phi.$$

$\endgroup$
  • 3
    $\begingroup$ Hmmm, and this addresses the question because? $\endgroup$ – Did Nov 24 '17 at 14:33
  • $\begingroup$ @Did, my point is to show the limit approaches not a random number, but the golden ratio, i.e. their relation. Like the relation of Fibonacci numbers with binomial coefficients. $\endgroup$ – farruhota Nov 25 '17 at 3:43
  • $\begingroup$ ...Which is known to the OP, it seems, and not related to what they are actually asking. $\endgroup$ – Did Nov 25 '17 at 8:26

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.