Solve T(n) = 2T(n-1) + a, assuming T(0) = 1

Solution
T(n) = 2T(n-1) + a
= 2{2(T(n-2) + a} + a
= (2^2)T(n-2) + a (2^2 + 1)
... = (2^k)T(n-k) + a (2^k - 1)
When n-k = 0, we get
T(n) = (2^k) + a (2^k - 1)

Proof
T(0) = 2^0 + a (2^0 - 1) = 1 (formula true for n=1)
Assume true fro 1...k
T(k+1) = 2T(k) + a
= 2{2^k + a (2^k -1) + a}
= 2^(k+1) + 2a(2^k -1) + a
= 2^(k+1) + a(2^(k+1) -1)
therefore the formula is true for (k+1) and so for all n

Also see: http://math.stackexchange.com/questions/9731/prove-by-induction-tn-2tn-2-2