Results 1 to 3 of 3

Math Help - Fibonacci Sequence Proof

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    19

    Fibonacci Sequence Proof

    Fibonacci Sequence - Induction.
    Prove F(n) ≤ (7/4)^n for all n, 0≤n

    F(n) = F(n-1) + F(n-2)

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

    Let n = k+1

    F(k+1) ≤ (7/4)^(k+1)

    LHS: F(k+1) = F(k)+ F(k-1) ≤ F(k-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)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Aug 2009
    Posts
    9
    Quote Originally Posted by glover_m View Post
    Fibonacci Sequence - Induction.
    Prove F(n) ≤ (7/4)^n for all n, 0≤n

    F(n) = F(n-1) + F(n-2)

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

    Let n = k+1

    F(k+1) ≤ (7/4)^(k+1)

    LHS: F(k+1) = F(k)+ F(k-1) ≤ F(k-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)
    LHS:
    F(k+1) = F(k)+ F(k-1)
    ≤ (7/4)^(k-1) + (7/4)^k
    =(7/4)^(k-1) ( 1+7/4)...................1+7/4=2.75 < (7/4)^2
    ≤ (7/4)^(k-1)(7/4)^2
    =(7/4)^(k+1)

    i don't know why it is ≤ instead of <
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2009
    Posts
    19
    thanks, was copying over from html so had to edit some things and must have forgot to change that too.

    thanks a lot btw
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Fibonacci sequence divisibility proof
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: June 20th 2011, 04:46 AM
  2. Fibonacci sequence proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: April 5th 2011, 02:29 AM
  3. Fibonacci Sequence - Induction Proof
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 19th 2011, 03:41 PM
  4. Fibonacci sequence proof
    Posted in the Algebra Forum
    Replies: 3
    Last Post: May 20th 2010, 07:28 AM
  5. Fibonacci sequence proof
    Posted in the Algebra Forum
    Replies: 3
    Last Post: April 30th 2007, 09:12 AM

Search Tags


/mathhelpforum @mathhelpforum