Recurrences and induction

Suppose T is a recurrence relation defined as follows.

T(0) = D
T(n) = 2 ⋅ T(n) + C

Theorem: T can be represented by the closed-form equation T(n) = D ⋅ 2ⁿ + C ⋅ (2ⁿ − 1).

Proof: We will proceed by induction.

• For n = 0: We want to show T(0) = D ⋅ 2⁰ + C ⋅ (2⁰ − 1).

  T(0)	= D	(by definition of T above)
  	= D ⋅ 1 + C ⋅ 0	(algebraic expansion)
  	= D ⋅ 20 + C ⋅ (20 − 1)	(algebraic expansion)

• For n = k: Our inductive hypothesis is that for all j < k, we know T(j) = D ⋅ 2^j + C ⋅ (2^j − 1). Supposing this, we want to show that T(k) = D ⋅ 2^k + C ⋅ (2^k − 1).

  T(k)	= 2 ⋅ T(k − 1) + C	(by definition of T above)
  	= 2 ⋅ (D ⋅ 2k − 1 + C ⋅ (2k − 1 − 1)) + C	(by inductive hypothesis using k − 1 for j)
  	= D ⋅ 2 ⋅ 2k − 1 + C ⋅ 2 ⋅ (2k − 1 − 1) + C	(distributing 2)
  	= D ⋅ 2 ⋅ 2k − 1 + C ⋅ (2 ⋅ 2k − 1 − 2 ⋅ 1 + 1)	(factoring C)
  	= D ⋅ 2k + C ⋅ (2k − 1)	(algebraic simplification)