Proof by Induction

Proof by Induction consists of:

• Base Case: show that solution holds for $n=1$
• Inductive Case:
  1. Assume that it holds for $n=k$.
  2. Substitute to confirm it also holds for $n=k+1$.