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