Mathematical Induction

Principle of Mathematical Induction

To prove $P(n)$ is true for all positive integers $n \geq n_0$:

1. Base Case: Prove $P(n_0)$ is true
2. Inductive Step: Prove $P(k) \rightarrow P(k+1)$ for all $k \geq n_0$

Why It Works

• Base case establishes $P(n_0)$
• Inductive step gives: $P(n_0) \rightarrow P(n_0+1) \rightarrow P(n_0+2) \rightarrow \cdots$
• Like dominoes falling!

Template for Weak Induction

Theorem: For all $n \geq n_0$, $P(n)$.

Proof by induction:

Base Case: [Verify $P(n_0)$]

Inductive Hypothesis: Assume $P(k)$ is true for some $k \geq n_0$.

Inductive Step: We must show $P(k+1)$. [Use the hypothesis to prove $P(k+1)$]

Therefore, by mathematical induction, $P(n)$ holds for all $n \geq n_0$. $\square$

Example 1: Sum Formula

Theorem: For all $n \geq 1$:

$\sum_{i=1}^{n} i = 1 + 2 + \cdots + n = \frac{n(n+1)}{2}$

Proof:

Base Case ($n = 1$):

• Left side: $\sum_{i=1}^{1} i = 1$
• Right side: $\frac{1(2)}{2} = 1$ ✓

Inductive Hypothesis: Assume for some $k \geq 1$: $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$

Inductive Step: Show it holds for $k + 1$:

$\sum_{i=1}^{k+1} i = \sum_{i=1}^{k} i + (k+1)$ $= \frac{k(k+1)}{2} + (k+1) \text{ (by IH)}$ $= \frac{k(k+1) + 2(k+1)}{2}$ $= \frac{(k+1)(k+2)}{2}$ $= \frac{(k+1)((k+1)+1)}{2}$ ✓ $\square$

Example 2: Inequality

Theorem: For all $n \geq 4$: $2^n < n!$

Proof:

Base Case ($n = 4$): $2^4 = 16 < 24 = 4!$ ✓

Inductive Hypothesis: Assume $2^k < k!$ for some $k \geq 4$.

Inductive Step: $2^{k+1} = 2 \cdot 2^k < 2 \cdot k! \text{ (by IH)}$ $< (k+1) \cdot k! = (k+1)!$ ✓

(Since $k \geq 4$, we have $k + 1 > 2$) $\square$

Strong Induction

Instead of assuming only $P(k)$, assume $P(n_0), P(n_0+1), \ldots, P(k)$ are all true.

Template

Base Case: Prove $P(n_0)$ (and possibly more base cases)

Inductive Hypothesis: Assume $P(j)$ is true for all $n_0 \leq j \leq k$.

Inductive Step: Prove $P(k+1)$ using any of $P(n_0), \ldots, P(k)$.

Example: Fundamental Theorem of Arithmetic

Theorem: Every integer $n > 1$ can be written as a product of primes.

Proof (by strong induction):

Base Case ($n = 2$): 2 is prime, so it's a product of one prime ✓

Inductive Hypothesis: Every integer $j$ with $2 \leq j \leq k$ can be written as a product of primes.

Inductive Step: Consider $k + 1$.

• If $k + 1$ is prime, we're done
• If $k + 1$ is composite: $k + 1 = ab$ where $2 \leq a, b < k + 1$
• By IH, both $a$ and $b$ are products of primes
• Therefore $k + 1 = ab$ is a product of primes $\square$

Structural Induction

Used for recursively defined structures (trees, lists, etc.).

Example: Binary Trees

To prove property $P$ for all binary trees:

1. Base: Prove $P$ for empty tree and single-node tree
2. Inductive: Assume $P$ for trees $T_1$ and $T_2$, prove for combined tree

Common Summation Formulas

$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$

$\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$

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

$\sum_{i=0}^{n} r^i = \frac{r^{n+1} - 1}{r - 1} \text{ for } r \neq 1$

$\sum_{i=0}^{n} 2^i = 2^{n+1} - 1$

Tips for Induction Proofs

1. Identify what you're proving: $P(n) = ?$
2. Determine base case(s)
3. Write the inductive hypothesis clearly
4. In the inductive step, look for where to apply the hypothesis
5. For strong induction, you can use any previous cases