- 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 2

^{k}-1 + 2^{k}*T(n-k). To use base case, let k = n-1 => 2^{n-1}-1 + 2^{n-1}*T(1). = 2*2^{n-1}-1 = 2^{n}-1. This is the guess. - Verify that 3
^{n}-2 is a closed form solution forT(1) = 1 T(n) = 4 + 3*T(n-1)

Proof (by induction):Base case (n=1): 3

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