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

```