Results 1 to 6 of 6
Like Tree2Thanks
  • 1 Post By Prove It
  • 1 Post By hollywood

Math Help - Proof: limit of ratios of fibonacci numbers is convergent

  1. #1
    Junior Member beebe's Avatar
    Joined
    Aug 2011
    Posts
    54

    Proof: limit of ratios of fibonacci numbers is convergent

    So I was given a proof: Let F_n be the n-th term of the Fibonacci sequence. Show that \lim_{n\to\infty}\frac{F_n}{f_{n-1}}=\frac{1+\sqrt{5}}{2}

    I figured out how to do the proof starting with the assumption that the limit exists for \lim_{n\to\infty}\frac{F_n}{f_{n-1}}. My problem is that I can't figure out how to show that the limit is convergent. My instructor suggested using something like the squeeze theorem, but I can't figure out how to use the squeeze theorem on a sequence defined recursively.

    I'm convinced that the ration decreases to the limit for odd values of n, and increases to the limit for even values of n, but don't know how to prove this, especially without assuming that the limit exists beforehand.

    I would appreciate avenues to pursue, but I am trying not to find an already complete proof, so don't give me the answer.

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Mar 2012
    From
    USA
    Posts
    28
    Thanks
    2

    Re: Proof: limit of ratios of fibonacci numbers is convergent

    I'm not sure if this will help or not, but a proof for the "ratio" test of series seems to be similar to what you're doing. Maybe worth a shot. Basically using the logic that having the n+1 term divided by the nth term is the same as having the nth term divided by the n-1 term. Here is a link to the proof for the ratio test, although I haven't yet checked it out myself. Again, I'm still in highschool, so I'm not quite sure if this will help or not.
    Last edited by Xeritas; March 21st 2012 at 12:48 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,569
    Thanks
    1427

    Re: Proof: limit of ratios of fibonacci numbers is convergent

    Start by showing that \displaystyle x := 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \dots}}}} } = \frac{1 + \sqrt{5}}{2}. To do this, notice that since the fraction is continuing ad infinitum, everything after the first vinculum is exactly what we are trying to find. Therefore, we have

    \displaystyle \begin{align*} x &= 1 + \frac{1}{x} \\ x^2 &= x + 1 \\ x^2 - x - 1 &= 0 \\ x^2 - x + \left(-\frac{1}{2}\right)^2 - \left(-\frac{1}{2}\right)^2 - 1 &= 0 \\ \left(x - \frac{1}{2}\right)^2 - \frac{1}{4} - 1 &= 0 \\ \left(x - \frac{1}{2}\right)^2 - \frac{5}{4} &= 0 \\ \left(x - \frac{1}{2}\right)^2 &= \frac{5}{4} \\ x - \frac{1}{2} &= \pm \frac{\sqrt{5}}{2} \\ x &= \frac{1}{2} \pm \frac{\sqrt{5}}{2}  \end{align*}

    And since it's clear that we are looking for a positive solution, that means \displaystyle x = 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \dots}}}} } = \frac{1 + \sqrt{5}}{2}.


    Now, notice what happens when we examine this continued fraction in more detail...

    \displaystyle \begin{align*} 1 = \frac{1}{1} &= \frac{F_0}{F_1} \\ 1 + \frac{1}{1} = \frac{2}{1} &= \frac{F_1}{F_2} \\ 1 + \frac{1}{1 + \frac{1}{1}} = \frac{3}{2} &= \frac{F_3}{F_2} \\ 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1}}} = \frac{5}{3} &= \frac{F_4}{F_3} \\ \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1}}}} = \frac{8}{5} &= \frac{F_5}{F_4} \\ &\vdots \\ 1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \frac{1}{1 + \dots}}}} } &= \frac{F_n}{F_{n-1}}  \end{align*}

    I think that you can see that the ratio of consecutive Fibonnaci numbers is upon \displaystyle \begin{align*} \frac{1 + \sqrt{5}}{2} \end{align*}
    Thanks from beebe
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member beebe's Avatar
    Joined
    Aug 2011
    Posts
    54

    Re: Proof: limit of ratios of fibonacci numbers is convergent

    Thank you! It hadn't occured to me to use continuing fractions.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,739
    Thanks
    645

    Re: Proof: limit of ratios of fibonacci numbers is convergent

    Hello, beebe!

    Are we allowed the closed form? . F_n \:=\:\frac{\left(1 + \sqrt{5}\:\!\right)^n - \left(1-\sqrt{5}\:\!\right)^n}{2^n\sqrt{5}}


    \text{Let }F_n\text{ be the }n^{th}\text{ term of the Fibonacci sequence.}
    \text{Show that: }\lim_{n\to\infty}\frac{F_n}{F_{n-1}}\;=\;\frac{1+\sqrt{5}}{2}

    \frac{F_n}{F_{n-1}} \;=\;\frac{1+\sqrt{5})^n - (1-\sqrt{5})^n}{2^n\sqrt{5}} \cdot\frac{2^{n-1}\sqrt{5}}{(1+\sqrt{5})^{n-1} - (1-\sqrt{5})^{n-1}}

    . . . . =\;\frac{1}{2}\cdot\frac{(1+\sqrt{5})^n - (1-\sqrt{5})^n}{(1+\sqrt{5})^{n-1} - (1-\sqrt{5})^{n-1}}


    Divide numerator and denominator by (1+\sqrt{5})^{n-1}

    . . \frac{1}{2}\cdot  \frac{\;\dfrac{(1+\sqrt{5})^n}{(1+\sqrt{5})^{n-1}} -\dfrac{1-\sqrt{5})^n}{(1+\sqrt{5})^{n-1}}\;} { \dfrac{(1+\sqrt{5})^{n-1}}{(1+\sqrt{5})^{n-1}} - \dfrac{(1-\sqrt{5})^{n-1}}{(1+\sqrt{5})^{n-1}}} \;=\; \frac{1}{2}\cdot\frac{(1 + \sqrt{5}) - (1-\sqrt{5})\left(\dfrac{1-\sqrt{5}}{1+\sqrt{5}}\right)^{n-1}} {1 - \left(\dfrac{1-\sqrt{5}}{1+\sqrt{5}}\right)^{n-1}}}


    \lim_{n\to\infty}\frac{F_n}{F_{n-1}} \;=\;\lim_{n\to\infty} \frac{1}{2}\cdot\frac{(1 + \sqrt{5}) - (1-\sqrt{5})\left(\dfrac{1-\sqrt{5}}{1+\sqrt{5}}\right)^{n-1}} {1 - \left(\dfrac{1-\sqrt{5}}{1+\sqrt{5}}\right)^{n-1}}}


    Note that: . \lim_{n\to\infty}\left(\frac{1-\sqrt{5}}{1+\sqrt{5}}\right)^n \:=\:0


    Therefore: . \lim_{n\to\infty}\frac{F_n}{F_{n-1}} \;=\;\frac{1}{2}\cdot \frac{(1 + \sqrt{5}) - 0}{1 - 0} \;=\;\frac{1 + \sqrt{5}}{2}

    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Mar 2010
    Posts
    980
    Thanks
    236

    Re: Proof: limit of ratios of fibonacci numbers is convergent

    Here's another idea.

    First, prove inductively that F_{n+1}F_{n-1}=F_n^2+(-1)^n. It's a pretty straightforward proof: remember that F_n=F_{n+1}-F_{n-1}.

    Then divide by F_nF_{n-1} to get \frac{F_{n+1}}{F_n}=\frac{F_n}{F_{n-1}}+\frac{(-1)^n}{F_nF_{n-1}}.

    Now use the alternating series test.
    Thanks from beebe
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci Numbers Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 13th 2011, 09:32 PM
  2. Proof about Fibonacci and Lucas numbers (GCD)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 21st 2010, 09:26 AM
  3. Induction Proof- Fibonacci Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 18th 2010, 06:28 AM
  4. Proving Lucas Numbers and Fibonacci Numbers
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 18th 2008, 11:33 PM
  5. Fibonacci Numbers - proof.
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 25th 2007, 09:08 AM

Search Tags


/mathhelpforum @mathhelpforum