# 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.

Regards, Raymond

-
$0!\ne0$; $0!=1$. –  Gerry Myerson Sep 29 '12 at 7:03
You want your induction hypothesis to be $f_k\le k!$, not $f_k=k!$. –  Gerry Myerson Sep 29 '12 at 7:04
You assert $k!+f_{k-1}$ can't be greater than $(k+1)k!$, but you don't support this assertion. –  Gerry Myerson Sep 29 '12 at 7:05
–  Martin Sleziak Sep 29 '12 at 7:21
Thanks all for helping out in my question. Really appreciate it! :) –  Ray.R.Chua Sep 30 '12 at 5:11

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$).

-
A classical Brian M. Scott answer, correct and complete. –  akkkk Sep 29 '12 at 11:52
Thanks Brian M.Scott. Your answer was not only helpful but is clear and complete. Really appreciate it! :) –  Ray.R.Chua Sep 30 '12 at 5:04
@Ray: You’re welcome; glad it helped. –  Brian M. Scott Sep 30 '12 at 6:50