Thread: 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

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.

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!