Results 1 to 3 of 3

Math Help - Fibonacci, proof with induction

  1. #1
    Newbie
    Joined
    Aug 2008
    Posts
    2

    Fibonacci, proof with induction

    Hello, I think I am getting stuck; I would really appreciate any help or advice!

    Prove by induction that {Fib}_n \geq 2^{n/2} for n \geq 6

    To start , prove the base case of n = 6:

    {Fib}_6 = 8, 2^{6/2} = 8 so {Fib}_6 \geq 2^{6/2}

    Now assume {Fib}_n \geq 2^{n/2} is true.

    We can multiply both sides by 2^{1/2} to get the n+1 term on the right side.

    2^{1/2}{Fib}_n \geq 2^{(n+1)/2}

    This is where I think I'm not sure about what to do. What I had been thinking is: now try to show that {Fib}_{n+1} \geq 2^{1/2}{Fib}_n

    so that we can conclude with {Fib}_n \geq 2^{n/2} \Longrightarrow {Fib}_{n+1} \geq 2^{(n+1)/2}.

    I had been trying: It's true that {Fib}_{6+1} \geq 2^{1/2}{Fib}_6. If we add {Fib}_n to both sides, we can get the n+2 term on the left. But then I wasn't sure if there is another step..? Or if I'm on the right track at all?

    THANKS! for any help!!
    Last edited by dill_day; August 26th 2008 at 08:10 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by dill_day View Post
    Prove by induction that {Fib}_n \geq 2^{n/2} for n \geq 6

    To start , prove the base case of n = 6
    the base case for this problem is actually n = 6 and n = 7, not just n = 6. (you'll see why later!) now suppose that n > 7 and that the claim is true

    for all 6 \leq k < n. then F_n^2 = (F_{n-1} + F_{n-2})^2 \geq (2^{\frac{n-1}{2}} + 2^{\frac{n-2}{2}})^2=2^n \left(\frac{1}{\sqrt{2}} + \frac{1}{2} \right)^2 > 2^n. therefore: F_n > 2^{\frac{n}{2}}, and the induction is complete!


    Remark: as you may have noticed, for n > 6, the inequality is strict, i.e. F_n > 2^{\frac{n}{2}}. it's a good exercise to try to find a non-inductive solution as well!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2008
    Posts
    2
    Thank you for the response! I am not sure I follow along...

    I think I understand why 6 and 7 are both part of the basis: F_n = F_{n-1} + F_{n-2}, so we first prove for n = 6 and 7, and then assume that the claim F_{k-1} + F_{k-2} \geq 2^{k/2} for some arbitrary k where k > 7 - because k > 7 \Longrightarrow k-2 \geq 6.

    Now we want to use the assumption that F_{k-1} + F_{k-2} \geq 2^{k/2} to prove that, if this assumption is true, F_{k} + F_{k-1} \geq 2^{(k+1)/2} must also be true.

    I'm having trouble figuring out where to start working towards this though... or, how squaring F_n leads to F_{n+1}...

    Thanks again for your help, and to anyone who can help me out!!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci Sequence - Induction Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 19th 2011, 03:41 PM
  2. [SOLVED] Fibonacci sequence induction proof
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 1st 2010, 10:22 AM
  3. Induction Proof- Fibonacci Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: February 18th 2010, 06:28 AM
  4. Fibonacci number Induction Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 17th 2009, 03:09 PM
  5. Fibonacci Sequence: Induction Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: August 14th 2009, 07:38 AM

Search Tags


/mathhelpforum @mathhelpforum