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.

  • $\begingroup$ How about finding an explicit formula for $F_n$? $\endgroup$ – 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}} $$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.