Proof the following proposition: for all $n \geq 0, \mathrm{fib}(n) \leq n!$ 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$. $\mathrm{fib}(0) = 0$, $0! = 0$. Thus,  $\mathrm{fib}(n) \leq n!$ is true when $n = 0$.
Assume $n = k$, $\mathrm{fib}(k) \leq k!$, for all values of $n \geq 2$.
Proof: $\mathrm{fib}(k+1) \leq (k+1)!$
$\mathrm{fib}(k+1) = \mathrm{fib}(k) + \mathrm{fib}(k-1)$
$\mathrm{fib}(k) + \mathrm{fib}(k-1) \leq (k+1)!$
$\mathrm{fib}(k) + \mathrm{fib}(k-1) \leq (k+1)\times k!$
$k! + \mathrm{fib}(k-1) \leq (k+1)\times k!$
Since $k! + \mathrm{fib}(k-1)$ can never be greater than $(k+1)\times k!$, it is true that $\mathrm{fib}(k+1) \leq (k+1)!$. This, for all $n \geq 0$, $\mathrm{fib}(n) \leq n!$ is true.
Thanks and please advise!
Regards,
Raymond
 A: I prefer to write $F_n$ for your $\operatorname{fib}(n)$. First, a small correction: $0!=1$, not $0$. Of course, it’s still true that $F_0\le 0!$. You also need to check that it’s true for $n=1$: $F_1=1=1!$, so it is. You need this because each Fibonacci number is calculated from the previous two Fibonacci numbers, not just from the immediately preceding Fibonacci number.
Your statement of the induction hypothesis is a bit confused. You say:

Assume n = k, fib(k) = k!, for all values of n≥2.

This says that you’re assuming that $F_k=k!$ for all $k\ge 2$, which isn’t what you want. You should be assuming that $F_k=k!$ for $k\le n$, where $n\ge 1$ is some fixed integer. Then you can say that
$$F_{n+1}=F_n+F_{n-1}\le n!+(n-1)!$$
by the definition of the Fibonacci numbers and the induction hypothesis applied to $F_n$ and $F_{n-1}$. But $n!+(n-1)!=n(n-1)!+(n-1)!=(n+1)(n-1)!\le(n+1)n(n-1)!=(n+1)!$, so $F_{n+1}\le(n+1)!$. This shows that if $F_n\le n!$ and $F_{n-1}\le(n-1)!$, then $F_{n+1}\le(n+1)!$, completing the induction step and allowing you to conclude that $F_n\le n!$ for all $n\in\Bbb N$.
To the extent that I can tell what you were thinking, I believe that you were attempting to reason backwards from the desired conclusion. This can be a good way to discover how the proof should go, but the proof itself must go forward from the hypothesis to the conclusion, as in my argument above.
Added: By the way, you can also prove it using the Binet formula, $$F_n=\frac{\varphi^n-\hat\varphi^n}{\sqrt5}\;,$$ where $$\varphi=\frac{1+\sqrt5}2\quad\text{and}\quad\hat\varphi=\frac{1-\sqrt5}2\;.$$ $|\hat\varphi|<1$, so $$F_n=\frac{\varphi^n}{\sqrt5}-\frac{\hat\varphi^n}{\sqrt5}\le\frac{\varphi^n}{\sqrt5}+\left|\frac{\hat\varphi^n}{\sqrt5}\right|<\varphi^n+1\le2\varphi^n\;.$$
Now $\varphi^2=\varphi+1$, so $\varphi^3=\varphi^2+\varphi=2\varphi+1$, $\varphi^4=2\varphi^2+\varphi=3\varphi+2$, and $$2\varphi^4=6\varphi+4=7+3\sqrt5<4!\;.$$
Now suppose that $2\varphi^n<n!$ for some $n\ge 4$. Then 
$$\begin{align*}
\varphi^{n+1}&=\varphi(2\varphi^n)&\\
&<\varphi\cdot n!&\text{induction hypothesis}\\
&<(n+1)n!&\text{because }\varphi<n+1\\
&=(n+1)!\;,
\end{align*}$$
and by induction we conclude that $2\varphi^n<n!$ for all $n\ge 4$. It follows that $F_n<2\varphi^n<n!$ for all $n\ge 4$. And since $F_0=0<1=0!$, $F_1=1=1!$, $F_2=2=2!$, and $F_3=3<6=3!$, we’ve actually shown that $F_n\le n!$ for all $n\ge 0$ (and $F_n<n!$ for all $n\ge 3$).
