TAOCP 1.2.1 Exercise 4
Let P(n): \qquad F_n \ge \phi^{\,n-2}, where $\phi=(1+\sqrt5)/2$ and $n$ is a positive integer.
Section 1.2.1: Mathematical Induction
Exercise 4. [20] Prove that, in addition to Eq. (3), Fibonacci numbers satisfy $F_n \ge \phi^{n-2}$ for all positive integers $n$.
Verified: yes
Solve time: 27s
Let
$$ P(n): \qquad F_n \ge \phi^{,n-2}, $$
where $\phi=(1+\sqrt5)/2$ and $n$ is a positive integer.
We prove $P(n)$ for all positive integers $n$ by mathematical induction.
For the basis, when $n=1$,
$$ F_1=1, $$
and since $\phi<2$,
$$ \phi^{-1}=\frac1\phi<1. $$
Hence
$$ F_1=1\ge \phi^{-1}=\phi^{1-2}. $$
When $n=2$,
$$ F_2=1=\phi^0=\phi^{2-2}. $$
Thus $P(1)$ and $P(2)$ are true.
Now assume that $P(1),P(2),\ldots,P(n)$ are true for some $n>1$. In particular,
$$ F_{n-1}\ge \phi^{,n-3}, \qquad F_n\ge \phi^{,n-2}. $$
Using the Fibonacci recurrence,
$$ F_{n+1}=F_n+F_{n-1}, $$
we obtain
$$ F_{n+1} \ge \phi^{,n-2}+\phi^{,n-3} = \phi^{,n-3}(\phi+1). $$
By equation (5),
$$ 1+\phi=\phi^2, $$
therefore
$$ F_{n+1} \ge \phi^{,n-3}\phi^2 = \phi^{,n-1}. $$
Since
$$ \phi^{,n-1}=\phi^{(n+1)-2}, $$
this is precisely $P(n+1)$.
The basis cases $P(1)$ and $P(2)$ have been established, and the truth of $P(n-1)$ and $P(n)$ implies the truth of $P(n+1)$ for every $n>1$. Therefore, by mathematical induction,
$$ F_n \ge \phi^{,n-2} $$
for all positive integers $n$.
$$ \boxed{F_n \ge \phi^{,n-2}\ \text{for all positive integers } n} $$
This completes the proof.
∎