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

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.

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

Quote:

Originally Posted by

**chiro** 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! :)