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) ______________________________________________________________________________.

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) ______________________________________________________________________________.