# 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 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)$$