Exercise 1038Logic, sets and proofs › Proof techniques › InductionL1Added 3 Nov 2026

Fibonacci growth bound

#induction#Fibonacci#growth

Statement

Prove by induction that $F_n\le\varphi^n$ where $\varphi=(1+\sqrt5)/2$ and $F_0=0,F_1=1$ .

Hint

$\varphi^2=\varphi+1$ . Strong induction: $F_{n+2}=F_{n+1}+F_n\le\varphi^{n+1}+\varphi^n=\varphi^n(\varphi+1)=\varphi^{n+2}$ .

Show solutionHide solution

Solution

Base cases. $F_0=0\le1=\varphi^0$ . $F_1=1\le\varphi\approx1.618$ . ✓

Inductive step. Assume $F_n\le\varphi^n$ and $F_{n+1}\le\varphi^{n+1}$ . Then
$F_{n+2}=F_{n+1}+F_n\le\varphi^{n+1}+\varphi^n=\varphi^n(\varphi+1)=\varphi^n\cdot\varphi^2=\varphi^{n+2}.$

Conclusion. $F_n\le\varphi^n$ for all $n$ .

Fibonacci growth bound

Statement

Solution

More problems in Induction