Solutions to recurrence problems from class 4/9/2003

1. Expand and "guess" a closed form solution for

   T(1) = 1
   T(n) = 1 + 2*T(n-1)
   

   Solution:

   T(n) = 1 + 2*T(n-1)
   
        = 1 + 2*(1 + 2*T(n-2))
        = 1 + 2 + 4*T(n-2)
        = 3 + 4*T(n-2)
   
        = 1 + 2 + 4*(1 + 2*T(n-3))
        = 1 + 2 + 4 + 8*T(n-3)
        = 7 + 8*T(n-3)
   
   General form is 
             2k-1 + 2k*T(n-k).
   To use base case, let k = n-1
          => 2n-1-1 + 2n-1*T(1).
           = 2*2n-1-1
           = 2n-1.  This is the guess.
   

2. Verify that 3ⁿ-2 is a closed form solution for

   T(1) = 1
   T(n) = 4 + 3*T(n-1)
   

   Proof (by induction):

   Base case (n=1): 31-2 = 1 = T(1)
   
   Inductive step: If T(k) = 3k-2
                   then T(k+1) = 3k+1-2
   
   Proof: By the definition of T,
             T(k+1) = 4 + 3*T(k)
          By the inductive hypothesis, this is 
                    = 4 + 3*(3k-2)
                    = 4 + 3k+1-6
                    = 3k+1-2.