# Solving fibonacci by induction

$$\begin{split} F(0) &= 0 \\ F(1) &= 1 \\ F(n) &= F(n - 1) + F(n - 2) \ for\ n \geq 2 \end{split}$$

Observe $2F(n-2) \leq F(n) \leq 2F(n-1).

*We assume by Analysis conventions ^{ᛦ} that \(F(n - 1) \geq F(n - 2)\)*

Implies F exponential in n. Assume \(F(n) < ab^n\) for some real numbers a, b.

We have to prove:

$$ ab^{n - 1} + ab^{n - 2} \leq ab^n $$

This is equivalent to \(b^2 - b - 1 \geq 0\).

Which is satisfied for \(b \geq (\sqrt{5} + 1) / 2\). (We can ignore negative parts because runtime / memory consumption won’t be negative)

Note that the `10`

supplied here in arbitrary.

**TODO**: include explanation about using 10, due to lower bound in inequality above.

If we use induction to prove the following:

$$ \frac{\phi}{10} \leq F(n) \leq \phi^n \ for\ n \geq 1 $$

Where $$ \phi = \frac{\sqrt{5} + 1}{2} $$

We can attain a asymptotic tight bound: \(F(n) = \Theta(\phi^n)\)