# prove that $\operatorname{fib}(n)<{(5/3)}^n$

I am trying to prove that

$$\operatorname{fib}(n)<\left(\frac{5}{3}\right)^n$$

where $\operatorname{fib}(n)$ is the $n^{th}$ fibonacci number. For a proof I used induction, as we know

$$\operatorname{fib}(1)=1,\, \operatorname{fib}(2)=1,\, \operatorname{fib}(3)=2$$

and so on. So for $n=1$; $\operatorname{fib}(1)<\frac{5}{3}$, and for general $n>1$ we will have

$$\operatorname{fib}(n+1)<\left(\frac{5}{3}\right)^{n+1}$$ First of all, $$\left(\frac{5}{3}\right)^{n+1} = \left(\frac{5}{3}\right)^{n} \cdot \left(\frac{5}{3}\right)$$

We have $\operatorname{fib}(n)<\left(\frac{5}{3}\right)^n$ and $\operatorname{fib}(n+1)=\operatorname{fib}(n)+\operatorname{fib}(n-1)$, so by induction we would have $\operatorname{fib}(n-1)<\left(\frac{5}{3}\right)^{n-1}$, and because $\frac{5}{3}>1$, we have $\left(\frac{5}{3}\right)^{n}>1$, so we get the correct result. Are there any flaws in my proof?

-
Did you show that $5/3 + 1 = 8/3 < (5/3)^2$? –  Tunococ Sep 5 '12 at 6:50
no thanks for this –  dato datuashvili Sep 5 '12 at 6:50
generally i have not considered this,because $fib(1)!=5/3$ ;by the way,thank you very much –  dato datuashvili Sep 5 '12 at 6:55

## 1 Answer

I don't quite understand how you claim you have proved $fib(n + 1) < (5/3)^{n+1}$. You have not even used $fib(n+1) = fib(n) + fib(n-1)$. I only see that $(5/3)^{n+1} > 1$ from your proof.

This is what the induction step is supposed to look like:

$$fib(n + 1) = fib(n) + fib(n - 1) < \left(\frac 53\right)^{n} + \left(\frac 53\right)^{n-1} = \left(\frac 53\right)^{n-1}\left(\frac 83\right) < \left(\frac 53\right)^{n+1}.$$

-
please see my proof,i have used that one –  dato datuashvili Sep 5 '12 at 7:02
what i have missed is $+(5/3)^{n-1}$ instead of this i used multiplication –  dato datuashvili Sep 5 '12 at 7:06
@dato: What you missed is absolutely crucial and is why what you wrote isn’t a proof. –  Brian M. Scott Sep 5 '12 at 7:08
yes yes right,sorry,i was hurry to finish this proof that did not consider it –  dato datuashvili Sep 5 '12 at 7:10