# 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