Upper and Lower Bound of Fibonacci Number
Jump to navigation
Jump to search
Theorem
For all $n \in \N_{> 0}$:
- $\phi^{n - 2} \le F_n \le \phi^{n - 1}$
where:
- $F_n$ is the $n$th Fibonacci number
- $\phi$ is the golden section: $\phi = \dfrac {1 + \sqrt 5} 2$
Proof
From Fibonacci Number greater than Golden Section to Power less Two:
- $F_n \ge \phi^{n - 2}$
From Fibonacci Number less than Golden Section to Power less One:
- $F_n \le \phi^{n - 1}$
$\blacksquare$
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.8$: Fibonacci Numbers