Data Structures, Algorithms, & Applications in C++
Chapter 2, Exercise 36

t(n) = 2 + t(n-1)
     = 4 + t(n-2)
     = 6 + t(n-3)
     .
     .
     .
     = 2n + t(0)
     = 2n + 2
     = 2(n+1)

t(n) = 2n + t(n-1)
     = 2n + 2(n-1) + t(n-2)
     = 2n + 2(n-1) + 2(n-2) + t(n-3)
     .
     .
     .
     = 2(n + n-1 + n-2 + ... + 1) + t(0)
     = 2n(n+1)/2 + 0
     = n(n+1)

t(n) = 3 * t(n-1)
     = 9 * t(n-2)
     = 27 * t(n-3)
     .
     .
     .
     = 3n * t(0)
     = 3n