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)\)