Recursion notes

From raju

tower of Hanoi

recurrence
<math>

\begin{array}{lcl} T_0 = 0; & & \\ T_n = 2 T_{n-1} + 1, & & \text{for } n > 0 \end{array} </math>

closed form
<math>

\begin{array}{lcl} T_n = 2^n -1, & & \text{for } n \geqslant 0 \end{array} </math>