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 \gt 0 \end{array} [/math]
closed form
[math] \begin{array}{lcl} T_n = 2^n -1, & & \text{for } n \geqslant 0 \end{array} [/math]