Mathematical Induction

Mathematical induction is a proof technique for establishing that a statement is true for every natural number. Think of it like knocking over an infinite line of dominoes: if you can knock over the first one (the base case) and prove that any domino knocking over the next one (the inductive step), then every domino falls. Induction is the standard method for proving summation formulas, divisibility properties, and inequalities that hold for all integers from some starting point onward.

The Principle of Mathematical Induction

To prove that a statement $P(n)$ is true for all integers $n \ge n_0$ (often $n_0 = 1$):

Step 1 — Base Case: Show that $P(n_0)$ is true.

Step 2 — Inductive Step: Assume $P(k)$ is true for some arbitrary integer $k \ge n_0$ (the induction hypothesis). Then prove that $P(k+1)$ must also be true.

Conclusion: By the principle of mathematical induction, $P(n)$ is true for all $n \ge n_0$.

The induction hypothesis is not assuming what you want to prove. You are assuming the statement for one specific value $k$ and using that assumption to prove it for the next value $k + 1$. The logical chain then carries the truth from the base case to every subsequent integer.

Proving Summation Formulas

Example 1: Sum of the First n Natural Numbers

Prove: $1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}$ for all $n \ge 1$.

Base Case ($n = 1$):

Left side: $1$. Right side: $\frac{1(2)}{2} = 1$. They match. Base case holds.

Inductive Step: Assume the formula holds for $n = k$:

$1 + 2 + \cdots + k = \frac{k(k+1)}{2} \quad \text{(induction hypothesis)}$

We must show it holds for $n = k + 1$:

$1 + 2 + \cdots + k + (k+1) = \frac{(k+1)(k+2)}{2}$

Starting from the left side, use the induction hypothesis:

$\underbrace{1 + 2 + \cdots + k}_{\text{induction hypothesis}} + (k+1) = \frac{k(k+1)}{2} + (k+1)$

$= \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{k(k+1) + 2(k+1)}{2}$

$= \frac{(k+1)(k+2)}{2}$

This is exactly the formula with $n = k + 1$. The inductive step is complete.

Conclusion: By mathematical induction, $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ for all $n \ge 1$.

Example 2: Sum of Squares

Prove: $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ for all $n \ge 1$.

Base Case ($n = 1$):

Left: $1^2 = 1$. Right: $\frac{1 \cdot 2 \cdot 3}{6} = 1$. Holds.

Inductive Step: Assume true for $k$: $\sum_{i=1}^{k} i^2 = \frac{k(k+1)(2k+1)}{6}$.

Show for $k + 1$:

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

$= \frac{k(k+1)(2k+1) + 6(k+1)^2}{6}$

Factor out $(k+1)$:

$= \frac{(k+1)[k(2k+1) + 6(k+1)]}{6}$

$= \frac{(k+1)(2k^2 + k + 6k + 6)}{6}$

$= \frac{(k+1)(2k^2 + 7k + 6)}{6}$

$= \frac{(k+1)(k+2)(2k+3)}{6}$

$= \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6}$

This matches the formula with $n = k + 1$.

Proving Divisibility

Example 3: Divisibility by 6

Prove: $n^3 - n$ is divisible by 6 for all $n \ge 1$.

Base Case ($n = 1$): $1^3 - 1 = 0$. Zero is divisible by 6 (since $0 = 6 \times 0$). Holds.

Inductive Step: Assume $k^3 - k$ is divisible by 6 for some $k \ge 1$. That means $k^3 - k = 6m$ for some integer $m$.

Show $(k+1)^3 - (k+1)$ is divisible by 6:

$(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1$

$= (k^3 - k) + 3k^2 + 3k$

$= (k^3 - k) + 3k(k + 1)$

By the induction hypothesis, $k^3 - k = 6m$. Also, $k(k+1)$ is the product of two consecutive integers, so it is always even: $k(k+1) = 2j$ for some integer $j$. Therefore:

$3k(k+1) = 3 \cdot 2j = 6j$

So $(k+1)^3 - (k+1) = 6m + 6j = 6(m + j)$, which is divisible by 6.

Proving Inequalities

Example 4: Exponential Growth Beats Linear Growth

Prove: $2^n > n$ for all $n \ge 1$.

Base Case ($n = 1$): $2^1 = 2 > 1$. Holds.

Inductive Step: Assume $2^k > k$ for some $k \ge 1$.

Show $2^{k+1} > k + 1$:

$2^{k+1} = 2 \cdot 2^k > 2 \cdot k = 2k$

We need $2k \ge k + 1$, which simplifies to $k \ge 1$. This is true since $k \ge 1$ by our base case assumption.

Therefore $2^{k+1} > 2k \ge k + 1$.

Example 5: Factorial Inequality

Prove: $n! > 2^n$ for all $n \ge 4$.

Base Case ($n = 4$): $4! = 24$ and $2^4 = 16$. Since $24 > 16$, it holds.

Inductive Step: Assume $k! > 2^k$ for some $k \ge 4$.

$(k+1)! = (k+1) \cdot k! > (k+1) \cdot 2^k$

Since $k \ge 4$, we have $k + 1 \ge 5 > 2$, so:

$(k+1) \cdot 2^k > 2 \cdot 2^k = 2^{k+1}$

Therefore $(k+1)! > 2^{k+1}$.

Note: The base case starts at $n = 4$, not $n = 1$. Induction proves the statement from the base case onward. Check: for $n = 3$, $3! = 6$ and $2^3 = 8$, so $3! > 2^3$ fails — confirming that $n = 4$ is the right starting point.

Strong Induction (Brief)

In strong induction, the inductive step assumes $P(n_0)$, $P(n_0 + 1)$, …, $P(k)$ are all true (not just $P(k)$), then proves $P(k+1)$. This is useful when the $(k+1)$th case depends on a case earlier than $k$.

Strong induction is logically equivalent to ordinary induction but sometimes makes proofs easier. A classic example is proving that every integer greater than 1 can be written as a product of primes.

Real-World Application: Algorithm Correctness

Induction is the standard technique for proving that recursive algorithms are correct. For example, the merge sort algorithm works by:

• Base case: A list of 1 element is already sorted
• Inductive step: If merge sort correctly sorts lists of size up to $k$, then splitting a list of size $k + 1$ into two halves, recursively sorting each, and merging the results produces a correctly sorted list

Computer scientists use this reasoning to guarantee that the algorithm works for any input size.

Common Mistakes

1. Skipping the base case. Without it, the chain of reasoning has no starting point. Consider the false “proof” that all horses are the same color — it fails because the base case for $n = 1$ does not properly connect to $n = 2$.
2. Assuming what you want to prove. You assume $P(k)$ (for one specific $k$), then show $P(k+1)$ follows. You are NOT assuming $P(k+1)$.
3. Not clearly using the induction hypothesis. The power of the proof comes from explicitly invoking the assumption. Underline or annotate where you use it.
4. Choosing the wrong base case. The statement must be checked at the actual starting point. If the claim is for $n \ge 4$, the base case is $n = 4$.

Practice Problems

Key Takeaways

• Mathematical induction proves statements for all $n \ge n_0$ using two steps: base case and inductive step
• The base case establishes the starting truth; the inductive step propagates it to all larger values
• You assume $P(k)$ (induction hypothesis) and prove $P(k+1)$ — you do not assume what you are trying to prove
• Induction works for summation formulas, divisibility, and inequalities
• Strong induction assumes all cases up to $k$ (useful when the next case depends on earlier cases)
• Always verify your base case carefully — a wrong starting point invalidates the entire proof

Return to College Algebra for more topics in this section.