Asymptotic bound of a recursive function
The recurrence relation $T(n) = T(n-1) + T(n-2)$, with initial conditions $T(2) = T(1) = 1$, has as solution the Fibonacci numbers, whose asymptotic growth is known to be $\Theta(\phi^n)$, where $\phi = \frac{1+\sqrt{5}}{2} &lt; 2$. The same bound holds for arbitrary positive initial conditions.