Fill-in-the-blank Recurrence Exercises

1. Find a closed form solution for recurrence S below:

   S(1) = 3
   S(n) = 5 + S(n-1)
   
   Expand:
   S(n) = 5 + S(n-1)
      
        = 5 + (____________________________________) (expand)
   
   
        = _____________________________________________ (expand again)  
   
   
   General form: _________________________________________________.
   
   
   To get the S term to the base case, let k = ___________________.  This gives
   
   
   ____________________________________________________________________________
   
   which is the guess.
   

   Verify that given the definition for S above, S(n) = _______________________.

   Base case (n=1): _______________________________________
   
   Inductive Step: (Hint: If the guess holds for k, it also holds for k+1.  Write this out mathematically using the actual guess.)
   
   _______________________________________________________________________________.
   
   Proof:
   By the definition of S, S(k+1) = _____________________________________________.
   
   By the inductive hypothesis, _________________________________________________.
   
   Substituting into line 1, this gives S(k+1) =  _______________________________
   
   = (simplify) ______________________________________________________________________________.
   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

2. Find a closed form solution for recurrence T below:

   T(1) = 6
   T(n) = 4 + T(n/2)
   
   Expand:
   T(n) = 4 + T(n/2)
      
        = 4 + (_________________________________________) (expand)
   
   
        = ______________________________________________ (expand again)
   
   
   General form: _________________________________________________.
   
   
   To get the T term to the base case, let k = ___________________.  This gives
   
   
   ____________________________________________________________________________
   
   which is the guess.
   

   Verify that given the definition for T above, T(n) = _______________________.

   Base case (n=1): _______________________________________
   
   Inductive Step: (Hint: If the guess holds for all values between 1 and k, 
   it also holds for k+1.  Write this out mathematically using the actual guess.)
   
   
   _______________________________________________________________________________.
   
   Proof:
   By the definition of T, T(k+1) = _____________________________________________.
   
   
   By the inductive hypothesis, _________________________________________________.
   
   Substituting into line 1, this gives T(k+1) =  _______________________________
   
   
   = (simplify) ______________________________________________________________________________.