fibonacci

F0 = 0, F1 = 1, Fn = Fn − 1 + Fn − 2

theorems

Fn ≤ ϕn − 1 for all positive integers n

We use proof_by_induction.

If n = 1, then F1 = 1 = ϕ0. Step 1 is done.

P(2) is also true, since F2 = 1 < 1.6 < ϕ1 = ϕ2 − 1. Now, if P(1), P(2), …, P(n) are true, and n > 1, we have, in particular, that P(n − 1) and P(n) are also true, so Fn − 1 ≤ ϕn − 2 and Fn ≤ ϕn − 1. Adding these inequalities, we get Fn + 1 = Fn − 1 + Fn ≤ ϕn − 2 + ϕn − 1 = ϕn − 2(1 + ϕ)

Note, $\phi `:=` \frac{\left( 1+\sqrt{5} \right)}{2}$, and so $\phi^2 = \frac{1}{4} \left( 1 + 2 \sqrt{5} + 5 \right) = \frac{3}{4} + \frac{\sqrt{5}}{2} = 1 + \frac{1}{2}\left( 1 + \sqrt{5} \right) = 1 + \phi$

Putting this in the equation before gives up Fn − 1 + Fn ≤ ϕn − 2 + ϕn − 1 = ϕn − 2(1 + ϕ) = ϕn which P(n + 1).

backlinks