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

• Sep 28th 2012, 11:04 PM
raylistic87
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.
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.

Regards,
Raymond
• Sep 28th 2012, 11:24 PM
chiro
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.
• Sep 29th 2012, 07:56 PM
raylistic87
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! :)