# Proving $F_n \ge (\frac{1}{2}(1+\sqrt{5}))^{n-2}$ for $n \in \mathbb{N}_{>1}$ when $F_n$ is the nth Fibonacci number

Let $$F_n$$ be defined as the nth Fibonacci number.

Prove that $$F_n \ge (\frac{1}{2}(1+\sqrt{5}))^{n-2}$$ with $$n \in \mathbb{N}_{>1}$$

My approach thus far was to use induction over $$n$$. Proving that the equation holds true for $$n = 2$$ and $$n=3$$ as Induction Base is no issue. However I'm getting stuck when proving the the induction step:

With $$n = n' +1 = n'' + 2$$ assuming the assumption holds true for $$n'$$ and $$n''$$ I have the following steps:

$$F_n \ge (\frac{1+\sqrt{5}}{2})^{n-2}$$

$$F_n' + F_n'' \ge (\frac{1+\sqrt{5}}{2})^{n''}$$

But I can't seem to figure out a way to proced after this.

• How about finding an explicit formula for $F_n$? – user157227 May 20 '15 at 17:52

Your approach is just fine. As is common, denote

$$\varphi = \frac{1+\sqrt{5}}{2}$$

It is useful to notice that

$$\varphi^2 = \frac{1+2\sqrt{5}+5}{4} = \frac{3+\sqrt{5}}{2} = 1+\varphi$$

It is then straightforward to show that if $F_n \geq \varphi^{n-2}$ and $F_{n+1} \geq \varphi^{n-1}$, we have in consequence

$$F_{n+2} = F_n+F_{n+1} \geq \varphi^{n-2}+\varphi^{n-1} = \varphi^{n-2}(1+\varphi) = \varphi^n$$

It may be of interest that

$$F_n = \frac{\varphi^n-(-1/\varphi)^n}{\sqrt{5}}$$

• Thanks! I entirely missed the $\varphi^2 = 1 + \varphi$. – ntldr May 20 '15 at 18:35