9.3 Mathematical Induction

Mathematical induction is a proof technique for showing that a statement holds for every natural number. Instead of checking infinitely many cases one by one, you prove just two things: that the statement works for a starting value, and that whenever it works for one number, it must work for the next. Those two pieces together guarantee the statement is true across the board.

This technique comes up constantly when working with sequences and series, because the formulas for sums of arithmetic and geometric sequences all claim to work "for all $n$." Induction is how you actually prove those claims are valid.

Mathematical Induction Principle

more resources to help you study

practice questions

Definition and Key Components

Mathematical induction proves that a statement $P(n)$ is true for all natural numbers $n$ by establishing two things:

• Base case (basis): Show the statement holds for the first natural number, usually $n = 1$ (sometimes $n = 0$, depending on the problem).
• Inductive step: Assume the statement holds for some arbitrary natural number $k$ (this assumption is called the inductive hypothesis), then prove it must also hold for $k + 1$.

If both pieces are established, the principle guarantees the statement is true for every natural number.

Reasoning Behind the Principle

You can't check a statement for infinitely many numbers one at a time. Induction gets around this by using the structure of the natural numbers themselves. The base case starts the chain, and the inductive step keeps it going: since it's true for $n = 1$, it must be true for $n = 2$; since it's true for $n = 2$, it must be true for $n = 3$; and so on, forever. There are no gaps in the natural numbers that could break this chain, which is why the method works.

Think of it like dominoes. You knock over the first one (base case), and you've shown that any domino falling will knock over the next one (inductive step). Every domino falls.

Applying Mathematical Induction

Step-by-Step Process

1. Prove the base case. Plug in the starting value (usually $n = 1$) and verify the statement is true.
2. State the inductive hypothesis. Assume the statement is true for some arbitrary natural number $k$.
3. Prove the inductive step. Starting from the assumption that the statement holds for $k$, show it must hold for $k + 1$. This usually involves algebraic manipulation: you'll take the expression for $k + 1$, substitute in the inductive hypothesis, and simplify until you reach the desired form.
4. Conclude. State that by the principle of mathematical induction, the statement is true for all natural numbers.

Worked Example: Sum of the First $n$ Odd Numbers

Claim: $1 + 3 + 5 + \cdots + (2n - 1) = n^2$ for all natural numbers $n$.

Step 1 (Base case): When $n = 1$, the left side is just $1$, and the right side is $1^2 = 1$. They match, so the base case holds.

Step 2 (Inductive hypothesis): Assume the formula is true for $n = k$. That is, assume:

$1 + 3 + 5 + \cdots + (2k - 1) = k^2$

Step 3 (Inductive step): Show the formula holds for $n = k + 1$. The left side for $k + 1$ adds one more term:

$1 + 3 + 5 + \cdots + (2k - 1) + (2(k+1) - 1)$

By the inductive hypothesis, replace the first chunk with $k^2$:

$k^2 + (2k + 1)$

Factor:

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

That's exactly what the formula predicts for $n = k + 1$. The inductive step is complete.

Step 4 (Conclusion): By mathematical induction, $1 + 3 + 5 + \cdots + (2n - 1) = n^2$ for all natural numbers $n$.

Other Classic Statements Proven by Induction

• Sum of squares: $1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}$
• Divisibility: $3^n - 1$ is divisible by 2 for all natural numbers $n$
• Inequalities: $2^n > n$ for all $n \geq 1$
• Sum of cubes identity: $\sum_{i=1}^{n} i^3 = \left(\sum_{i=1}^{n} i\right)^2$

Induction for Sequences and Series

Arithmetic Sequences and Series

An arithmetic sequence has a constant difference $d$ between consecutive terms. Its general term is:

$a_n = a_1 + (n - 1)d$

The sum of the first $n$ terms is:

$S_n = \frac{n}{2}(2a_1 + (n-1)d)$

To prove this sum formula by induction:

1. Base case ($n = 1$): $S_1 = a_1$. The formula gives $\frac{1}{2}(2a_1 + 0) = a_1$. It checks out.
2. Inductive hypothesis: Assume $S_k = \frac{k}{2}(2a_1 + (k-1)d)$.
3. Inductive step: $S_{k+1} = S_k + a_{k+1}$. Substitute the hypothesis for $S_k$ and use $a_{k+1} = a_1 + kd$, then simplify to show you get $\frac{k+1}{2}(2a_1 + kd)$, which is the formula evaluated at $n = k + 1$.

Geometric Sequences and Series

A geometric sequence has a constant ratio $r$ between consecutive terms. Its general term is:

$a_n = a_1 \cdot r^{n-1}$

The sum of the first $n$ terms (when $r \neq 1$) is:

$S_n = \frac{a_1(1 - r^n)}{1 - r}$

To prove this sum formula by induction:

1. Base case ($n = 1$): $S_1 = a_1$. The formula gives $\frac{a_1(1 - r)}{1 - r} = a_1$. It checks out.

2. Inductive hypothesis: Assume $S_k = \frac{a_1(1 - r^k)}{1 - r}$.

3. Inductive step: $S_{k+1} = S_k + a_{k+1} = \frac{a_1(1 - r^k)}{1 - r} + a_1 \cdot r^k$. Combine these over a common denominator: $\frac{a_1(1 - r^k) + a_1 \cdot r^k(1 - r)}{1 - r} = \frac{a_1(1 - r^{k+1})}{1 - r}$. That's the formula for $n = k + 1$.

Problem Solving with Induction

General Problem-Solving Steps

1. Identify the statement and write it as $P(n)$ in terms of a natural number $n$.
2. Prove the base case by direct substitution.
3. State the inductive hypothesis: assume $P(k)$ is true.
4. Prove the inductive step: show $P(k) \Rightarrow P(k+1)$. This is where most of the work happens. Look for ways to express the $k+1$ case in terms of the $k$ case, then apply the hypothesis.
5. Conclude by invoking the principle of mathematical induction.

A common mistake is trying to prove the $k + 1$ case from scratch without actually using the inductive hypothesis. The whole point of induction is that you use the assumption for $k$ to get to $k + 1$. If your proof of the inductive step doesn't reference the hypothesis, something has gone wrong.

Examples of Problems Solved by Induction

• Divisibility: $7^n - 1$ is divisible by 6 for all $n \geq 1$. (In the inductive step, write $7^{k+1} - 1 = 7 \cdot 7^k - 1 = 7(7^k - 1) + 6$, then use the hypothesis that $7^k - 1$ is divisible by 6.)
• Inequalities: $n! < n^n$ for all $n \geq 2$.
• Telescoping sums: $\sum_{i=1}^{n} \frac{1}{i(i+1)} = \frac{n}{n+1}$
• Recursive sequences: Proving a closed-form formula for a recursively defined sequence, such as showing $a_n = 2^n - 1$ satisfies $a_n = 2a_{n-1} + 1$ with $a_1 = 1$.