Results 1 to 3 of 3

Math Help - proof by complete induction

  1. #1
    Newbie
    Joined
    Sep 2007
    Posts
    3

    proof by complete induction

    fibonacci sequence {fn}= 1,1,2,3,5,8,13,... you know this. defined recursively by f1=1 f2=1 fn+2 = fn+1 + fn for n=1,2,3,... use complete induction to prove that fn < 2^n for all positive integers n. I'm just a little confused with the complete induction part the book and teacher didn't explain it too well.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,212
    Thanks
    419
    Awards
    1
    Quote Originally Posted by Puubes View Post
    fibonacci sequence {fn}= 1,1,2,3,5,8,13,... you know this. defined recursively by f1=1 f2=1 fn+2 = fn+1 + fn for n=1,2,3,... use complete induction to prove that fn < 2^n for all positive integers n. I'm just a little confused with the complete induction part the book and teacher didn't explain it too well.
    We have that
    f_1 < 2^1
    and
    f_2 < 2^2

    Now assume that there is a number k such that f_m < 2^m for all m \leq k.

    We wish to show that
    f_{k + 1} < 2^{k + 1}

    Well,
    f_{k + 1} = f_k + f_{k - 1}

    and we know, by assumption, that
    f_{k - 1} < 2^{k - 1}
    and
    f_k < 2^k

    Thus
    f_{k + 1} = f_k + f_{k - 1} < 2^k + 2^{k - 1}

    But
    2^k + 2^{k -1} < 2^{k + 1} <-- I leave this for you to prove.

    Thus
    f_{k + 1} = f_k + f_{k - 1} < 2^k + 2^{k - 1} < 2^{k + 1}

    implies
    f_{k + 1} < 2^{k + 1}
    as desired.

    Thus the theorem is true for n = 1, 2, ...

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2007
    Posts
    3
    thanks dan that seems simple enough.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proving Complete Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: June 10th 2011, 02:13 PM
  2. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  3. Complete Induction proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 22nd 2009, 07:41 AM
  4. What's wrong with this proof (complete induction)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 4th 2009, 11:32 PM
  5. complete induction problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 20th 2008, 12:48 PM

Search Tags


/mathhelpforum @mathhelpforum