Mathematical Induction: Proof Techniques

Proof Techniques, Part II: Mathematical Induction

• $P(n)$ represents a statement parameterized by $n$
• To prove that $P(n)$ is true for all $n \geq n_0$, show:
  • Base Case: $P(n_0)$ is true
  • Inductive Step: For all $n \geq n_0$, if $P(n)$ is true, then $P(n + 1)$ is true

Template for an Inductive Proof

• Theorem: State the theorem, such as $P(n)$ is true for all $n \geq n_0$
• Proof: Proceed by induction
  • Base Case: Proof that $P(n_0)$ is true
  • Inductive Step:
    • Assume that $P(n)$ is true for some $n \geq n_0$. (Inductive hypothesis)
    • Prove that $P(n + 1)$ is true, using the inductive hypothesis
    • Conclude that $P(n + 1)$ is true
• Therefore, $P(n)$ is true for all $n \geq n_0$

Example 1: Gaussian Sum

• Theorem: For all $n \geq 1$, $\sum_{i=1}^{n} i = \frac{n(n + 1)}{2}$
• Proof: Proceed by induction
  • Base Case: When $n = 1$, the summation is $1$, and $\frac{n(n + 1)}{2} = \frac{1 \cdot 2}{2} = 1$, so the theorem holds
  • Inductive Step: Assume $\sum_{i=1}^{n} i = \frac{n(n + 1)}{2}$ for some $n \geq 1$
    • $\sum_{i=1}^{n + 1} i = (\sum_{i=1}^{n} i) + (n + 1)$
    • $= \frac{n(n + 1)}{2} + (n + 1)$
    • $= \frac{n(n + 1) + 2(n + 1)}{2}$
    • $= \frac{(n + 1)(n + 2)}{2}$
    • Therefore, $\sum_{i=1}^{n + 1} i = \frac{(n + 1)((n + 1) + 1)}{2}$
• Therefore, $\sum_{i=1}^{n} i = \frac{n(n + 1)}{2}$, for all $n \geq 1$

Example 2: Geometric Sum

• Theorem: For all $n \geq 0$ and $x \neq 1$, $\sum_{i=0}^{n} x^{i} = \frac{1 - x^{n + 1}}{1 - x}$
• Proof: Proceed by induction
  • Base Case: When $n = 0$, the summation is $x^{0} = 1$, and $\frac{1 - x^{n + 1}}{1 - x} = \frac{1 - x}{1 - x} = 1$, so the theorem holds
  • Inductive Step: Assume $\sum_{i=0}^{n} x^{i} = \frac{1 - x^{n + 1}}{1 - x}$ for some $n \geq 0$
    • $\sum_{i=0}^{n + 1} x^{i} = (\sum_{i=0}^{n} x^{i}) + x^{n + 1}$
    • $= \frac{1 - x^{n + 1}}{1 - x} + x^{n + 1}$
    • $= \frac{1 - x^{n + 1} + x^{n + 1}(1 - x)}{1 - x}$
    • $= \frac{1 - x^{n + 2}}{1 - x}$
    • Therefore, $\sum_{i=0}^{n + 1} x^{i} = \frac{1 - x^{(n + 1) + 1}}{1 - x}$
• Therefore, $\sum_{i=0}^{n} x^{i} = \frac{1 - x^{n + 1}}{1 - x}$, for all $n \geq 0$

Strong Induction

• $P(n)$ is a statement parameterized by $n$
• To prove that $P(n)$ is true for all $n \geq n_0$, show:
  • Base Case: $P(n_0)$ is true
  • Inductive Step: For all $n > n_0$, if $P(k)$ is true for all $n_0 \leq k < n$, then $P(n)$ is true

Example 3: Postage

• Theorem: Every amount of postage that is at least 12 cents can be formed using only 4-cent and 5-cent stamps
• Proof: Proceed by strong induction
  • Base Case: For $n = 12$, the theorem holds because $12 = 3 \cdot 4$
  • Inductive Step: Assume that for some $n > 12$, every amount of postage between 12 cents and $n - 1$ cents is formable using only 4-cent and 5-cent stamps
    • We must show that $n$ cents can also be formed using only 4-cent and 5-cent stamps
    • Since $n > 12$, $n - 4 \geq 12 - 4 = 8$
    • Therefore, $n - 4$ is an amount of postage between 12 cents and $n - 1$ cents, so by the inductive hypothesis, we can form $n - 4$ cents using only 4-cent and 5-cent stamps.
    • By adding one additional 4-cent stamp, we can form $n$ cents using only 4-cent and 5-cent stamps
• Therefore, every amount of postage that is at least 12 cents can be formed using only 4-cent and 5-cent stamps