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?

  • 3
    Did you show that $5/3 + 1 = 8/3 < (5/3)^2$?2012-09-05
  • 0
    no thanks for this2012-09-05
  • 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
    please see my proof,i have used that one2012-09-05
  • 0
    what i have missed is $+(5/3)^{n-1}$ instead of this i used multiplication2012-09-05
  • 1
    @dato: What you missed is absolutely crucial and is why what you wrote isn’t a proof.2012-09-05
  • 0
    yes yes right,sorry,i was hurry to finish this proof that did not consider it2012-09-05