# 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

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.
$$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}.$$
what i have missed is $+(5/3)^{n-1}$ instead of this i used multiplication –  dato datuashvili Sep 5 '12 at 7:06