Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fibonacci Sequence - Induction.

  1. Sep 15, 2009 #1
    Prove Fn ≤ (7/4)n for all n, 0≤n

    Fn = Fn-1 + Fn-2

    Let P(n) be true for some n = k, for 0≤k

    Let n = k+1

    Fk+1 ≤ (7/4)k+1

    LHS: Fk+1 = Fk + Fk-1 ≤ Fk-1 + (7/4)k ≤ (7/4)k-1 + (7/4)k

    This last line is where I'm stuck, I feel like either I messed up early on, or I'm missing a way of simplifying this to look like (7/4)k+1
     
  2. jcsd
  3. Sep 15, 2009 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Well, [itex](7/4)^{k-1}= (4/7)(7/4)^k[/itex] so [itex](7/4)^{k-1}+ (7/4)^k= (4/7+ 1)(7/4)^k[/itex]. And 4/7+ 1= 11/7= (11/7)(4/7)(7/4)= (44/49)(7/4) and 44/49< 1.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook