Results 1 to 3 of 3
Like Tree1Thanks
  • 1 Post By chiro

Math Help - Proof the following proposition: for all n ≥ 0 , fib(n) ≤ n!

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    SG
    Posts
    2

    Proof the following proposition: for all n ≥ 0 , fib(n) ≤ n!

    Hi All,
    I am a comp science undergrad and just started to learn proof.
    And I have been thinking about this question for a few days.
    How should I present my answer?
    Do I have to use the Binet's formula?
    Or can I do this:


    Base case:
    let n = 0
    fib(0) = 0
    0! = 0
    Thus, fib(n) ≤ n! is true when n = 0.
    Assume n = k, fib(k) = k!, for all values of n≥2,
    Proof: fib(k+1) ≤ (k+1)!


    fib(k+1) = fib(k) + fib(k-1)


    fib(k) + fib(k-1) ≤ (k+1)!


    fib(k) + fib(k-1) ≤ (k+1) * k!


    k! + fib(k-1) ≤ (k+1) * k!


    Since k! + fib(k-1) can never be greater than (k+1) * k!, it is true that fib(k+1) ≤ (k+1)!
    This, for all n ≥ 0 , fib(n) ≤ n! is true.


    Thanks and please advise!


    Regards,
    Raymond
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    4,173
    Thanks
    765

    Re: Proof the following proposition: for all n ≥ 0 , fib(n) ≤ n!

    Hey raylistic87.

    You may want to look at showing its true for n = 2 instead since you are looking at k-1.

    Also for fib(k-1), use the fact that this is less than (k-1)! and group the terms to show that k! + (k-1)! < (k+1)! You've nearly completed the proof, but you've left out this critical step which will show that is true for all later values of k since fib(k) <= k! and fib(k-1) <= (k-1)!.

    So for the first step look at when n = 2 not n = 0 so basically show 0+1+2 < 2! since you are dealing with k+1 (which is n), k, and k-1.

    Otherwise though you have the right idea.
    Thanks from raylistic87
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2012
    From
    SG
    Posts
    2

    Re: Proof the following proposition: for all n ≥ 0 , fib(n) ≤ n!

    Quote Originally Posted by chiro View Post
    Hey raylistic87.

    You may want to look at showing its true for n = 2 instead since you are looking at k-1.

    Also for fib(k-1), use the fact that this is less than (k-1)! and group the terms to show that k! + (k-1)! < (k+1)! You've nearly completed the proof, but you've left out this critical step which will show that is true for all later values of k since fib(k) <= k! and fib(k-1) <= (k-1)!.

    So for the first step look at when n = 2 not n = 0 so basically show 0+1+2 < 2! since you are dealing with k+1 (which is n), k, and k-1.

    Otherwise though you have the right idea.
    Thanks for the reply, chiro. Great help!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: March 27th 2012, 11:34 PM
  2. Replies: 4
    Last Post: August 4th 2011, 02:45 PM
  3. Replies: 2
    Last Post: March 19th 2011, 02:38 AM
  4. Replies: 1
    Last Post: January 22nd 2011, 05:14 AM
  5. Replies: 1
    Last Post: May 27th 2008, 08:56 AM

Search Tags


/mathhelpforum @mathhelpforum