< Home

Proofs by Induction

Suppose we want to prove P(n)P(n) for any integer n≥1n \geq 1 (typical case)

  1. Base Case (BC): Prove P(n)P(n) for the smallest non-negative integer
  2. Induction Hypothesis (IH): "Assume P(n)P(n) holds for some positive integer n>[base case]n > \text{[base case]}"
  3. Induction Step (IS): Using the truth of P(n)P(n), show that P(n+1)P(n+1) also holds.
  4. "Thus by the Principle of Mathematical Induction (PMI), P(n)P(n) holds for all integers n≥[base case]n \geq \text{[base case]}" QED

Examples

Example 1

Prove that if n∈Z+n \in \mathbb{Z} ^+ then $$

\sum _{i = 1} ^{n} i = \left( \frac{n(n+1)}{2} \right) $$

BC: let n=1n = 1 P(1):∑i=11i=1(1(1+1)2)=1 \begin{align} P(1): & \sum _{i =1} ^ 1 i = 1 \\ & \left( \frac{1(1 + 1)}{2} \right) = 1 \end{align}

Thus P(1)P(1) holds.

IH: Assume P(n)P(n) holds for some positive integer n>1n > 1.

We will solve for: >∑i=1n+1i=(n+1)(n+1+1)2> > \sum _{i=1} ^{n + 1} {i} = \frac{(n+1)(n+1+1)}{2} >

IS: Consider ∑i=1n+1i=∑i=1ni+(n+1)=n(n+1)2⏟ From the IH +n+1By IH=n(n+1)+2(n+1)2=(n+1)(n+2)2 \begin{align} &\sum _{i=1} ^{n + 1} {i} \\ &= \sum _{i=1} ^{n} {i} + (n + 1)\\ \\ &= \underbrace{ \frac{n(n+1)}{2} }_{ \text{ From the IH } } + n + 1 &\text{By IH} \\ &= \frac{n(n+1) + 2(n+1)}{2} \\ &= \frac{(n+1)(n+2)}{2} \end{align}

Thus P(n+1)P(n+1) holds

By PMI, P(n)P(n) holds for all integers n≥1n \geq 1

QED