Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
$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
1  
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
    
    
Thanks all for helping out in my question. Really appreciate it! :) –  Ray.R.Chua Sep 30 '12 at 5:11
add comment

1 Answer

up vote 3 down vote accepted

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.