Proving Fibonacci inequality

Question

I didn't see a question regarding this particular inequality, but I think that I have shown by induction that, for $n>1$. I am hoping someone can verify this proof. $$\left(\frac{1+\sqrt{5}}{2}\right)^{n-1}<F_{n+1}<\left(\frac{1+\sqrt{5}}{2}\right)^{n}$$

Here we state that $F_0=0, F_1=1$. The base case is established since $$\left(\frac{1+\sqrt{5}}{2}\right)<F_{3}<\left(\frac{1+\sqrt{5}}{2}\right)^{2}$$ $$1.61803...<2<2.61803...$$ Now assume that $n=k$ and that the following holds: $$\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}<F_{k+1}<\left(\frac{1+\sqrt{5}}{2}\right)^{k}$$ Starting with the left side of the inequality, and looking at $F_{k+2}=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{k+2}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{k+2}$ $$F_{k+2}>\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{k+2}=\frac{2}{\sqrt{5}+\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{k+2}>\frac{2}{3+\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{k+2}=\left(\frac{2}{1+\sqrt{5}}\right)^2\left(\frac{1+\sqrt{5}}{2}\right)^{k+2}=\left(\frac{1+\sqrt{5}}{2}\right)^{k}$$ So the left side didn't need the induction hypothesis, just some careful analysis. Now the right side of the inequality. By the induction hypothesis, $$\left(\frac{1+\sqrt{5}}{2}\right)^{k}>F_{k+1} \Rightarrow \left(\frac{1+\sqrt{5}}{2}\right)^{k+1}>\left(\frac{1+\sqrt{5}}{2}\right)F_{k+1} $$ But since $F_{k+1}=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^{k+1}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^{k+1}$ $$\left(\frac{1+\sqrt{5}}{2}\right)^{k+1}>\left(\frac{1+\sqrt{5}}{2}\right)F_{k+1}=F_{k+2} $$ Therefore, $$\left(\frac{1+\sqrt{5}}{2}\right)^{k}<F_{k+2}<\left(\frac{1+\sqrt{5}}{2}\right)^{k+1}$$ I feel as though the analysis is good. Is there any holes or misstatements?

Answer 1

Your proof is valid, but i like a little less tedious proof:

Note that $$\phi^2=\phi+1$$ $$\phi^3=\phi^2+\phi=2\phi+1$$ $$\phi^4=2\phi^2+\phi=3\phi+2$$ $$\phi^5=3\phi^2+2\phi=5\phi+3$$ see the Fibonacci numbers in the coeficcients, now generally: $$\phi^n=F_n\phi+F_{n-1}$$, so we can rewrite your problem: $$\phi^{n-1}=F_{n-1}\phi+F_{n-2}<F_{n+1}<F_n\phi+F_{n-1}=\phi^n$$ since $F_n+F_{n-1}=F_{n+1}$, and $1<\phi$ it follows that $F_n<F_n\phi$ and $$F_{n+1}=F_n+F_{n-1}<F_n\phi+F_{n-1}$$ since $2F_{n-1}+F_{n-2}=F_{n}+F_{n-1}=F_{n+1}$ and $\phi<2$, it follows that $F_{n-1}\phi<2F_{n-1}$ and $$F_{n-1}\phi+F_{n-2}<2F_{n-1}+F_{n-2}=F_{n+1}$$ thus we are done.

Answer 2

I think your proof would be clearer if you wrote things in terms of the golden ratio $\phi=\dfrac{1+\sqrt{5}}{2}$. As a demonstration of why that's helpful, let me give a non-inductive proof of the upper bound. Note that this inequality is equivalent by the Binet formula to $$ \frac{1}{\sqrt{5}}\left(\phi^{n+1}-(-\phi)^{-n-1}\right)< \phi^{n}.$$ Dividing out $\phi^{n-1}/\sqrt{5}$ gives

$$\phi^2+(-1)^n \phi^{-2n}<\phi\sqrt{5}.$$

But $\phi^2=\phi+1$, $\sqrt{5}=2\phi-1$, and $\phi^{-2} = (\phi^2-\phi)\phi^{-2} =1-\phi^{-1}\cdot(\phi^2-\phi) = 2-\phi.$ So the inequality becomes $$\phi+1+(\phi-2)^n<2\phi^2-\phi =\phi+2\implies (\phi-2)^n < 1.$$ But $-1<\phi-2 <0$, so it follows that $|\phi-2|<1$ and so $(\phi-2)^n\leq|\phi-2|^n<1$ for $n\geq 2$. This completes the proof.