5
$\begingroup$

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?

  • 0
    generally i have not considered this,because $fib(1)!=5/3$ ;by the way,thank you very much2012-09-05

1 Answers 1

8

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

  • 0
    yes yes right,sorry,i was hurry to finish this proof that did not consider it2012-09-05