T(n) = T(n-1) + 3
= T(n-1-1) + 3 + 3
= T(n-1-1-1) + 3 + 3 + 3
...
= T(0) + n*3
= 3n+1
Solving Recurrence Formulas
One Method: Repeated Substitution
T(0) => 1;
T(n) => T(n-1) + 3;
use the above formulas repeatedly
T(n)= 3n+1
is a Òclosed formÓ solution
to the recurrence.