Proving that for Fibonacci numbers $a_n \lt (\frac {1 + \sqrt 5} 2)^n$ for $n \ge 1$

Question

I'd like to prove that for Fibonacci numbers $a_n \lt \left(\frac {1 + \sqrt 5} 2\right)^n$ for $n \ge 1$. I suppose it needs induction so, after verifying the trivial case $n=1$, the inductive step needs to be justified: $$a_{n+1} \lt \left(\frac {1 + \sqrt 5} 2\right)^{n+1}.$$ Assume $$a_n \lt \left(\frac {1 + \sqrt 5} 2\right)^n.$$ I can only think of multiplying both sides by $\left(\frac {1 + \sqrt 5} 2\right)$, which yields $$a_n\left(\frac {1 + \sqrt 5} 2\right) \lt \left(\frac {1 + \sqrt 5} 2\right)^{n+1}$$ and then somehow show that $a_{n+1} \lt a_n\left(\frac {1 + \sqrt 5} 2\right)$. I tried using the fact that $a_{n+1}=a_n + a_{n-1}$ but wasn't able to conclude anything useful. Can you suggest me a way to prove it?

Answer 1

Let $a_n=F_n$ and $b_n=\left(\frac{1+\sqrt{5}}{2}\right)^n$. Since $\frac{1+\sqrt{5}}{2}$ is a root of the polynomial $t^2-t-1$, we have: $$ a_{n+2} = a_{n+1}+a_{n}\quad\text{as well as}\quad b_{n+2}=b_{n+1}+b_n, \tag{1}$$ hence in order to prove that $$ a_n < b_n \tag{2}$$ holds for every $n\geq 1$ it is enough to check that $(2)$ holds for $n=1,2,$ then apply induction exploiting $(1)$.

Answer 2

First note the following (this will show the relevance of Antoine's comment): $$ \left(\frac{1+\sqrt{5}}{2}\right)^n > \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n > \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n. $$ The explicit formula for Fibonacci numbers that Antoine's comment is presumably referring to is Binet's formula, which states that, for every $n\geq 0$, that $$ F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right], $$ where $F_n$ is the $n$th Fibonacci number. Hence, if you can prove Binet's formula, then you will have certainly proven what you set out to prove because $$ \left(\frac{1+\sqrt{5}}{2}\right)^n > \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right] = F_n. $$ Thus, let's prove Binet's formula using induction, and your result will follow as a "trivial" consequence, as Antoine's comment notes.

---

For every $n\geq 0$, let $A(n)$ denote the statement $$ A(n) : F_n = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]. $$ Base step: When $n=0$, the expression on the right-hand side of $A(n)$ is $0$, which is $F_0$. For $n=1$, it is also not difficult to check that each side of $A(n)$ is $1$.

Inductive step ($[A(k-1)\land A(k)]\to A(k+1)$): Suppose that for some fixed $k$, that $A(k-1)$ and $A(k)$ are true. Calculating, (where the second equality below follows from $A(k-1)$ and $A(k)$), \begin{align} F_{k+1} &= F_{k-1}+F_k\\[1em] &= \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}-\left(\frac{1-\sqrt{5}}{2}\right)^{k-1}\right]+\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{k}-\left(\frac{1-\sqrt{5}}{2}\right)^{k}\right]\\[1em] &= \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}\left(1+\frac{1+\sqrt{5}}{2}\right)-\left(\frac{1-\sqrt{5}}{2}\right)^{k-1}\left(1+\frac{1-\sqrt{5}}{2}\right)\right]\\[1em] &= \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}\left(\frac{3+\sqrt{5}}{2}\right)-\left(\frac{1-\sqrt{5}}{2}\right)^{k-1}\left(\frac{3-\sqrt{5}}{2}\right)\right]\\[1em] &= \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{k-1}\left(\frac{1+\sqrt{5}}{2}\right)^2-\left(\frac{1-\sqrt{5}}{2}\right)^{k-1}\left(\frac{1-\sqrt{5}}{2}\right)^2\right]\\[1em] &= \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^{k+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{k+1}\right], \end{align} so $A(k+1)$ is also true, completing the inductive step.

By mathematical induction, for each $n\geq 0, A(n)$ is true.

Your own claim follows as a result.