Results 1 to 3 of 3

Thread: 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
    11,152
    Thanks
    731
    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
    $\displaystyle f_1 < 2^1$
    and
    $\displaystyle f_2 < 2^2$

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

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

    Well,
    $\displaystyle f_{k + 1} = f_k + f_{k - 1}$

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

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

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

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

    implies
    $\displaystyle 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: Jun 10th 2011, 01:13 PM
  2. Replies: 10
    Last Post: Jun 29th 2010, 12:10 PM
  3. Complete Induction proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 22nd 2009, 06:41 AM
  4. What's wrong with this proof (complete induction)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Apr 4th 2009, 10:32 PM
  5. complete induction problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Oct 20th 2008, 11:48 AM

Search Tags


/mathhelpforum @mathhelpforum