Fibonacci Number Proof

  1. 1. The problem statement, all variables and given/known data
    The Fibonacci numbers are defined recusively by:
    F(0) = 0, F(1) = 1, for n > 1, F(n) = F(n − 1) + F(n − 2).
    Use strong induction to show that F(n) < 2^n for all n.


    2. Relevant equations
    n/a

    3. The attempt at a solution
    I use my base case as F(2) = F(1) + F(0) = 1 which is less than 2^n = 2^2 = 4. After that I am not sure where to go with strong induction...
     
  2. jcsd
  3. micromass

    micromass 18,543
    Staff Emeritus
    Science Advisor

    The induction hypthesis gives us

    [tex]F(n)=F(n-1)+F(n-2)\leq 2^{n-1}+2^{n-2}[/tex]

    Can you now prove that this is smaller then [tex]2^n[/tex]?
     
  4. well 2^n-1 + 2^n-2 is equal to 2^n (2^-1 + 2^-2) = 3/4(2^n) but I don't see the logic behind equating the problem to less than or equal to 2^n-1 + 2^n-2
     
  5. micromass

    micromass 18,543
    Staff Emeritus
    Science Advisor

    If you want to apply induction? Then what is the induction hypothesis?
     
  6. Let k>2, for all integers i, with 2<=i<k, F(i)<2^i would be my induction hypothesis I think?
     
  7. micromass

    micromass 18,543
    Staff Emeritus
    Science Advisor

    Yes, that is correct. So in particular, we have

    [tex]F(n-1)\leq 2^{n-1}~\text{and}~F(n-2)\leq 2^{n-2}[/tex]

    So

    [tex]F(n-1)+F(n-2)\leq 2^{n-1}+2^{n-2}[/tex]
     
  8. woops, I meant n>2, so just replace all my k's with n's and so if I know that F(i)<2^i, then F(i-1) + F(i-2) < 2^i-1 + 2^i-2 which is F(i) < 3/4 2^i, so therefore F(i) must also be less than 2^i if its less than 0.75 of it, so the statement is true for all F(n)
     
  9. does that look about right?
     
  10. micromass

    micromass 18,543
    Staff Emeritus
    Science Advisor

    Yeah, that looks fine :smile:
     
  11. thank you :), so in general with strong induction, you prove a base, then your induction hypothesis is that it works for all numbers between your base up until some value n, and you have to prove using this, that it also works for the n? thank you for all your help!
     
  12. micromass

    micromass 18,543
    Staff Emeritus
    Science Advisor

    Yep, that is the idea behind strong induction.

    Good luck with your next problems!
     
  13. thank you:)
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?