Is the Golden Ratio the Limit of Consecutive Fibonacci Numbers?

[steven187]

Warning:Danger Zone II

hello all

Check this out I have been working on this over the last few days, its pretty intense, I don't think I am getting anywhere, anyway peoples good luck

prove
$$\lim_{n\longrightarrow\infty}\frac{F_n}{F_{n-1}}=\frac{1+\sqrt{5}}{2}$$
where
$$F_n=F_{n-1}+F_{n-2} \ \forall n>2$$
A Fibonacci sequence

 

[matt grime]

Let G_n be F_n/F_{n-1} find an equation the G_n satisfy (this is easy and is obtainable from the step you've written. (hit the limit is the golden ratio, the root of x^2-x-1))

1. assume G_n converges, to G, find G from the equaiton you just made (hint take limits in both sides)

2. now show that G_n is indeed convergent (several ways of showing this kind of thing, say if x_n is an increasing (resp. decreasing) sequnec bounded above (resp. below) it converges. you may find the arithmetic-geometric mean (or some other inequality) helpful.)

please acn i ask others to refrain from posting *solutions*, though if my hints are off please correct them. i haven't checked them, but this *must* be how one solves it since it is the only method available to us. it's probably the worng time of year to be homework but it does feel like we solving all of steven's examples for him. by now the answers hould be startng to come moer easily to you, steven. this sounds harsher than i mean to be typing it, sorry if it osunds that way. you may way have been working on this for ages.

when you've seen the idea once, though, it becomes clear what to do in all cases like this.

 

[Zurtex]

This is a fairly standard problem, I must have come across it at least a few times in my courses. There are atleast a couple of ways of doing this (I seem to remember a much more 'exoitic' way of doing it), but matt grime's is the most obvious way of thinking about it.

Although, something worth noting is that you have not defined F₀ and F₁.

 

[saltydog]

May I offer another route of inquiry:

The Fibonacci relation above is in the form of a "second-order difference equation". Difference equations can be solved very much like linear differential equations: You determine the auxiliary equation, solve for the roots, form the complimentary function from the roots and then determine the constants c1 and c2 using the the initial conditions (f(0) and f(1)) to obtain the specific solution. Once the specific solution is obtained this way, the limit of the above ratio can be determined.

Edit: I made a mistake. I haven't figured out how to determine the limit from the equation derived from the difference equation. I'll work on it some more.

Edit2: You know what, this is Calculus/Analysis and I think my route is more, well difference equations and not Analysis. So nevermind. Also, I was able to prove the limit via this route.

 

[qbert]

Let's say you could come up with a formula
$$f_n = c_1 r_1^n + c_2 r_2^n$$
and you could prove that $r1 > r2 >0$.

Then you could write
$$\frac{f_{n+1}}{f_n} = \frac{ c_1 r_1^{n+1} + c_2 r_2^{n+1} }{<br /> c_1 r_1^n + c_2 r_2^n} \\<br /> = \frac {r_1 + \frac{c_2 r_2}{c_1} \left( \frac{r_2}{r_1} \right)^n}<br /> {1 + \frac{c_2}{c_1} \left( \frac{r_2}{r_1} \right)^n }$$

Then in the n -> infinity limit, $(r2/r1)^n \rightarrow 0$.

Then you could say:
$$\lim_{n \rightarrow \infty} \frac{f_{n+1}}{f_n} = r_1$$

--

 

[matt grime]

yeah, or you could just use the axiom of convergence and that the square of a real number is positive which is all I did. still two methods are better than one i suppose, but the "general" method is what they're after since it reinforces the basics of analysis, speaking as a teacher of analysis. it's also entirely possible that my general method doesn't work, you know.

 

[saltydog]

Let's say you could come up with a formula
$$f_n = c_1 r_1^n + c_2 r_2^n$$
and you could prove that $r1 > r2 >0$.

Then you could write
$$\frac{f_{n+1}}{f_n} = \frac{ c_1 r_1^{n+1} + c_2 r_2^{n+1} }{<br /> c_1 r_1^n + c_2 r_2^n} \\<br /> = \frac {r_1 + \frac{c_2 r_2}{c_1} \left( \frac{r_2}{r_1} \right)^n}<br /> {1 + \frac{c_2}{c_1} \left( \frac{r_2}{r_1} \right)^n }$$

Then in the n -> infinity limit, $(r2/r1)^n \rightarrow 0$.

Then you could say:
$$\lim_{n \rightarrow \infty} \frac{f_{n+1}}{f_n} = r_1$$

--

Very nice Qbert. That is in fact the route taken via difference equations as your first is a solution to the equation:

$$y_{n+2}+a_1y_{n+1}+a_0y_n=0$$

Although I approached the limit in a more messy direction but obtained the same result.

 

[matt grime]

looking at the first few terms of the ratios F_n/F_{n-1} then the sequence alternates between greater than the limit and less than the limit (1,2,1.5,1.66...,1.6,...) so for my allegedly better general method you're actually goingt o have some worl to do if it even is possible that way. (i think i can by soem tricks show that the sequence is cauchy, if taht'd be of interest)

 

[Zurtex]

The last time I proved this, I did it by showing that the partial fraction expansion of $(1 + \sqrt{5})/2$ was equal to F_n/F_n-1 and the rest of the proof was trivial.

 

[saltydog]

I'd like to explain, for those reading this and perhaps not familiar with solving difference equations, how to solve the Fibonacci equation using them. You'll notice the close resemblance to the method used in solving a linear second-order ODE:

Rewriting the Fibonacci equation as:

$$F_n-F_{n-1}-F_{n-2}=0;\quad F_0=1,\quad F_1=1$$

we attempt a trial solution of the form:

$$F_n=r^n;\quad r\ne 0$$

Substituting this into the Fibonacci equation we obtain:

$$r^n-r^{n-1}-r^{n-2}=0$$

or:

$$r^{n-2}(r^2-r-1)=0$$

Thus:

$$r^2-r-1=0$$

with:

$$r_1=\frac{1+\sqrt{5}}{2}=\phi;\quad r_2=\frac{1-\sqrt{5}}{2}=1-\phi$$

Since the roots are real and distinct, the general solution to this difference equation is given by:

$$F_n=c_1\phi^n+c_2(1-\phi)^n$$

Using the initial conditions we obtain:

$$1=c_1+c_2$$

$$1=c_1\phi+c_2(1-\phi)$$

Solving for $c_1$ and $c_2$ and noting that $2\phi-1=\sqrt{5}$, we obtain as the particular solution:

$$F_n=\left(\frac{\phi}{\sqrt{5}}\right)\phi^n+\left(\frac{\phi-1}{\sqrt{5}}\right)(1-\phi)^n$$

 

[steven187]

hello all

well that was a nice approach, after playing around with it I ended up doing it like this
let
$$\lim_{n\longrightarrow\infty}\frac{F_n}{F_{n-1}}=L$$

then from this
$$F_n=F_{n-1}+F_{n-2}$$

we get
$$\frac{F_n}{F_{n-1}}= 1 +\frac{F_{n-2}}{F_{n-1}}$$

$$\frac{F_n}{F_{n-1}}= 1 +\frac{1}{\frac{F_{n-1}}{F_{n-2}}}$$

while considering that the limit is unique and taking the limit of both sides we get
$$\lim_{n\longrightarrow\infty} \frac{F_n}{F_{n-1}}=\lim_{n\longrightarrow\infty}1 +\frac{1}{\frac{F_{n-1}}{F_{n-2}}}$$

$$L=1 +\frac{1}{L}$$

$$L^2-L-1=0$$

$$L=\frac{1+\sqrt{5}}{2};\frac{1-\sqrt{5}}{2}$$

since
$$\frac{F_n}{F_{n-1}}>1 \\ \forall n\epsilon N$$

then
$$L=\frac{1+\sqrt{5}}{2}$$

I am currently working on a method that involves linear algebra its pretty intense but hopefully I should get to my destination, once I do il post it up as usual .

 

[saltydog]

hello all

well that was a nice approach, after playing around with it I ended up doing it like this
let
$$\lim_{n\longrightarrow\infty}\frac{F_n}{F_{n-1}}=L$$

then from this
$$F_n=F_{n-1}+F_{n-2}$$

we get
$$\frac{F_n}{F_{n-1}}= 1 +\frac{F_{n-2}}{F_{n-1}}$$

$$\frac{F_n}{F_{n-1}}= 1 +\frac{1}{\frac{F_{n-1}}{F_{n-2}}}$$

while considering that the limit is unique and taking the limit of both sides we get
$$\lim_{n\longrightarrow\infty} \frac{F_n}{F_{n-1}}=\lim_{n\longrightarrow\infty}1 +\frac{1}{\frac{F_{n-1}}{F_{n-2}}}$$

$$L=1 +\frac{1}{L}$$

$$L^2-L-1=0$$

$$L=\frac{1+\sqrt{5}}{2};\frac{1-\sqrt{5}}{2}$$

since
$$\frac{F_n}{F_{n-1}}>1 \\ \forall n\epsilon N$$

then
$$L=\frac{1+\sqrt{5}}{2}$$

I am currently working on a method that involves linear algebra its pretty intense but hopefully I should get to my destination, once I do il post it up as usual .

Hello Steven.

That's a nice way you did that and I can't see anything wrong but I'm not the Analysis expert (well ok, far from it but I digress). Can you post the outlines of the linear algebra approach?

Thanks,
Salty

 

[Muzza]

The problem with steven's approach is that it doesn't show that the sequence actually converges...

 

[saltydog]

The problem with steven's approach is that it doesn't show that the sequence actually converges...

Ahhhhhh . . . good for you Muzza. I see that now. Thanks.

 

[Zurtex]

Like I say if you've done anything on continued fraction expansion then just expand [itex](1 + \sqrt{5})/2[/tex] and look at p_n and q_n. If not then, erm, try something else <img src="https://cdn.jsdelivr.net/joypixels/assets/8.0/png/unicode/64/1f644.png" class="smilie smilie--emoji" loading="lazy" width="64" height="64" alt=":rolleyes:" title="Roll Eyes :rolleyes:" data-smilie="11"data-shortname=":rolleyes:" />[/itex]

 

[steven187]

hello all

this is my basically my linear algebra approach enjoy, I don't know if anybody knew this but there is a general formulae in matrix form

$$A^n=\left(\begin{array}{cc}F_{n+1}&F_n\\F_n&F_{n-1}\end{array}\right)$$
where
$$A=\left(\begin{array}{cc}1&1\\1&0\end{array}\right)$$
by solving the characteristics equation
$$|A-\lambda I|=0$$
we get
$$(1-\lambda)(-\lambda)-1=0$$
$$\lambda^2-\lambda-1=0$$
as a result the eigenvalues are
$$\lambda=\phi;(1-\phi)$$
then by multiplying by $$\lambda^n$$
we get
$$\lambda^{n+2}-\lambda^{n+1}-\lambda^{n}=0$$
and so
$$n\mapsto \phi^n$$
also
$$n\mapsto (1-\phi)^n$$
just to note the eigenvectors are linear independent of each other and so the eigenvectors can be put into a linear combination, as a result we can have
$$n\mapsto a\phi^n+b(1-\phi)^n$$
to accommodate for all linear combinations and by adjusting the coefficients for the initial values we get
$$F_n=\frac{\phi^n+(1-\phi)^n}{\sqrt{5}}$$
now we let
$$a=\phi$$
and
$$b=1-\phi$$
$$a-b=\sqrt{5}$$
then
$$F_n=\frac{a^n-b^n}{a-b}$$
then we have
$$\frac{F_{n+1}}{F_n}=\frac{a^{n+1}-b^{n+1}}{a^n-b^n}$$
we then take the limit of both sides and we get
$$\lim_{n\rightarrow\infty}\frac{F_{n+1}}{F_n}=\lim_{n\rightarrow\infty}\frac{a^{n+1}-b^{n+1}}{a^n-b^n}$$
since
$$|b|<1$$
and
$$\lim_{n\rightarrow\infty}b^n=0$$
then
$$\lim_{n\rightarrow\infty}\frac{F_{n+1}}{F_n}=\lim_{n\rightarrow\infty}\frac{a^{n+1}}{a^n}=a=\phi$$
oh yes about the existence of the limit that aint too hard all i did was show that
$$1\le\frac{F_{n+1}}{F_n}\le 2$$
by using the fact
$$a_{n+1}=1+\frac{1}{a_n}$$
then i let
$$a_n=\frac{F_{n+1}}{F_n}$$
and showed that the subsequence (by mathematical Induction)
$$a_{2n+1}$$ is increasing and
$$a_{2n}$$ is decreasing
and so since all terms are positive then both subsequences converge to the same limit

steven

 

[Muzza]

...I don't know if anybody knew this...

The same method for working out the closed form of the Fibonacci sequence is detailed in "Basic Linear Algebra" by TS Blyth. ;)

...and so since all terms are positive then both subsequences converge to the same limit

Are you sure that this is sound reasoning? Seems like this sequence would be a counterexample:

a_(2n) = 1/n + 1
a_(2n + 1) = 2 - 1/n

 

[matt grime]

that first one is a nice method, will have to remember it.

the second one does indeed have problems as muzza mentions but they can be gotten round. i'd be itnerested to see the proofs that the even and odd parts are increasing and devreasing resp.

you cannot conclude that the converge to the same thing, though if one forms a recurrence that the even and odd terms satisfy like you did for the sequence in general then you can take limits in that relation and find the limits and show they are the same.

 

[steven187]

hello all

well i wanted to show that
$$a_{2n+2}-a_{2n}\le 0$$
$$a_{2n+2}-a_{2n}=\frac{a_{2n}-a_{2n-2}}{(1+a_{2n})(1+a_{2n-2})}$$
by considering that
$$1\le a_{n} \le 2$$
then
$$(1+a_{2n})(1+a_{2n-2})\ge 0$$
infact it should be
$$4\le (1+a_{2n})(1+a_{2n-2})\le 9$$
and so
$$a_{2n+2}-a_{2n}$$
has the same sign as
$$a_{2n}-a_{2n-2}$$
now by considering that
$$a_2=2$$ and $$a_4<a_2$$
then
$$a_{2n+2}-a_{2n}< a_{2n}-a_{2n-2}\le a_4-a_2\le 0$$
and this is true for all n by induction and hence
$$a_{2n}$$ a decreasing sequence
similarly for $$a_{2n+1}$$
and as for :

"..and so since all terms are positive then both subsequences converge to the same limit "

so we have 2 subsequences one that is decreasing and bounded by 1 so it must have a limit let us denote it by r also we have a increasing sequence which is bounded above by 2 so it must have a limit let us denote it by t

now since the terms of the sequence satisfy the equation
$$a_{n+2}=1+\frac{a_n}{1+a_n}$$
then the limit must also satisfy this equation
$$r^2-r-1=0$$
$$t^2-t-1=0$$
and since
$$a_n> 0 \ \forall n\epsilon N$$
then
$$r,t>0$$
and hence the limit is unique
$$r=t=\frac{1+\sqrt{5}}{2}$$

steven

 

[matt grime]

well done, that answer is perfect in all senses.