Proof by Mathematical Induction

Many of the most useful results in mathematics are not single statements but entire families of statements, one for every positive integer $n$: "the sum of the first $n$ integers is $\tfrac{n(n+1)}{2}$," "$7^n - 1$ is divisible by $6$," "$n! > 2^n$ for $n \geq 4$." None of the four proof techniques from Chapter 2 is quite suited to proving infinitely many statements at once — direct proof, contrapositive and contradiction each establish a single claim. Mathematical induction is the technique built precisely for this job, and it is the one you will use more often than any other in this course from here on.

The idea behind induction is often compared to a row of standing dominoes: knock over the first one, and show that every domino, if it falls, knocks over the next one — and the whole row falls, however long it is. This chapter makes that picture rigorous, states the principle precisely, and works through the standard families of induction proofs: summation formulas, divisibility, and inequalities. Have to hand: comfort with algebraic manipulation of sums, and patience, since the "inductive step" is the part every student finds awkward on first exposure.

1. The Principle of Mathematical Induction

Let $P(n)$ be a statement depending on a positive integer $n$ (an open sentence, in the language of Chapter 2, with domain $\mathbb{Z}^{+}$ or a subset of it). The principle of mathematical induction states:

If (1) $P(1)$ is true (the base case), and (2) for every $k \geq 1$, $P(k)$ being true implies $P(k+1)$ is true (the inductive step), then $P(n)$ is true for every positive integer $n$.

Why does this work? The base case gives $P(1)$. The inductive step with $k=1$ then gives $P(1) \Rightarrow P(2)$, so $P(2)$ is true. The inductive step with $k=2$ gives $P(2) \Rightarrow P(3)$, so $P(3)$ is true. This chains forward indefinitely: having established $P(k)$ for some value, the inductive step immediately produces $P(k+1)$, and since this holds for every $k$, no positive integer is ever skipped. Induction is therefore not really a fifth, independent proof technique so much as a single, infinitely repeated application of the inductive step, licensed all at once by the principle.

The inductive hypothesis. In the inductive step, the assumption "$P(k)$ is true" is called the inductive hypothesis. It is assumed, not proved — the entire content of the inductive step is the single conditional claim $P(k) \Rightarrow P(k+1)$, proved (typically) by a direct proof of its own.

Both parts are indispensable. Omitting the base case leaves the chain of dominoes with nothing to start falling — the inductive step alone, however correctly argued, proves nothing, since $P(k)\Rightarrow P(k+1)$ for every $k$ is vacuously satisfiable even if no $P(k)$ is ever true. Omitting the inductive step leaves only a single verified instance, $P(1)$, with no mechanism to extend it any further.

2. Summation Formulas by Induction

The most common application of induction in this course is proving a formula for $\sum_{i=1}^{n} f(i)$, a sum of $n$ terms.

Worked example — the sum of the first $n$ positive integers. Prove that for every $n \in \mathbb{Z}^{+}$,

Base case ($n=1$): the left side is $1$; the right side is $\dfrac{1(1+1)}{2} = 1$. They match, so $P(1)$ holds.

Inductive step. Assume $P(k)$ holds for some $k \in \mathbb{Z}^{+}$, i.e.

We must show $P(k+1)$ follows: that $1 + 2 + \cdots + k + (k+1) = \dfrac{(k+1)(k+2)}{2}$. Starting from the left side of $P(k+1)$ and using the inductive hypothesis to replace the first $k$ terms:

Factor out $(k+1)$:

which is exactly the right side of $P(k+1)$. The inductive step is complete: $P(k) \Rightarrow P(k+1)$ for every $k \in \mathbb{Z}^{+}$. By the principle of induction, $P(n)$ holds for all $n \in \mathbb{Z}^{+}$. $\blacksquare$

The one non-negotiable move. Every inductive step for a summation formula follows the same pattern: start from the $(k+1)$-term sum, split off the last term, replace the remaining $k$-term sum using the inductive hypothesis, and then show the resulting algebraic expression equals the formula's right side with $n$ replaced by $k+1$. Skipping the substitution of the inductive hypothesis — and instead just "verifying" the formula directly for $k+1$ — proves nothing, since it never uses $P(k)$ at all.

Worked example — sum of squares. Prove $\displaystyle\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ for all $n \in \mathbb{Z}^{+}$.

Base case ($n=1$): left side $=1^2=1$; right side $=\dfrac{1\cdot2\cdot3}{6}=1$. Match.

Inductive step: assume $\displaystyle\sum_{i=1}^{k} i^2 = \frac{k(k+1)(2k+1)}{6}$. Then

(the quadratic $2k^2+7k+6$ factors as $(k+2)(2k+3)$), which is the formula's right side with $n = k+1$ substituted: $\dfrac{(k+1)(k+2)(2(k+1)+1)}{6}$. The inductive step holds, so the formula is true for all $n \in \mathbb{Z}^{+}$ by induction.

3. Divisibility Proofs by Induction

Induction also proves statements of the form "$f(n)$ is divisible by $d$" for all $n$.

Worked example. Prove $7^n - 1$ is divisible by $6$ for every $n \in \mathbb{Z}^{+}$.

Base case ($n=1$): $7^1 - 1 = 6 = 6 \times 1$, divisible by $6$.

Inductive step: assume $7^k - 1 = 6m$ for some integer $m$ (inductive hypothesis, rewritten to isolate $7^k$: $7^k = 6m+1$). Consider $n=k+1$:

Since $7m+1 \in \mathbb{Z}$, $7^{k+1}-1$ is divisible by $6$. The inductive step holds, completing the proof by induction.

The key move in every divisibility induction is the same: rewrite the inductive hypothesis to isolate the awkward term ($7^k = 6m+1$ here), substitute it into the $(k+1)$-case expression, and factor out the required divisor from what remains.

4. Inequality Proofs by Induction

Induction proves inequalities too, though the algebra in the inductive step is often an inequality manipulation rather than an equation.

Worked example. Prove $2^n > n^2$ for all integers $n \geq 5$.

Here the base case is $n=5$, not $n=1$, since the claim is false for smaller $n$ (e.g. $n=4$: $2^4=16$, $4^2=16$, not strictly greater). Induction works perfectly well starting from any fixed integer base case, not only $n=1$; the chain of dominoes simply starts further along.

Base case ($n=5$): $2^5 = 32 > 25 = 5^2$. True.

Inductive step: assume $2^k > k^2$ for some $k \geq 5$. We want $2^{k+1} > (k+1)^2$. Starting from the inductive hypothesis and multiplying both sides by $2$:

It remains to show $2k^2 \geq (k+1)^2$ for $k \geq 5$, which would chain the inequality through:

For $k \geq 5$: $k^2 - 2k - 1 = k(k-2) - 1 \geq 5(3) - 1 = 14 > 0$, so $2k^2 > (k+1)^2$ for $k \geq 5$. Chaining:

so $2^{k+1} > (k+1)^2$, completing the inductive step. By induction, $2^n > n^2$ for all $n \geq 5$.

Inequality inductive steps need an extra algebraic bridge. Unlike equation-based inductive steps, which end in a single chain of equalities, an inequality inductive step often needs an auxiliary inequality (here, $2k^2 \geq (k+1)^2$ for $k\geq5$) to connect what the inductive hypothesis directly gives to what $P(k+1)$ requires.

5. Strong Induction (a Brief Extension)

Ordinary induction's inductive step uses only $P(k)$ to establish $P(k+1)$. Strong induction instead allows the inductive step to assume $P(1), P(2), \ldots, P(k)$ all true, and deduce $P(k+1)$ from any (or all) of them. This is especially useful when the claim about $n$ naturally depends on a smaller value that is not necessarily $n-1$ — for instance, proving every integer $n \geq 2$ has a prime factor, which may rely on a strictly smaller factor several steps back, not the immediately preceding case. Strong induction and ordinary induction are logically equivalent in what they can prove; strong induction is simply more convenient when the recursive structure of the problem demands it.

6. Common Exam Pitfalls

• Omitting the base case. An inductive step alone, however elegant, establishes nothing: $P(k) \Rightarrow P(k+1)$ is a conditional that is vacuously satisfiable without any $P(k)$ ever being true.
• Not actually using the inductive hypothesis. The inductive step must explicitly substitute $P(k)$'s truth into the expression for $P(k+1)$ — merely re-deriving the $k+1$ case from scratch, independently, is not a valid inductive argument, since it does nothing to show the implication $P(k)\Rightarrow P(k+1)$ itself.
• Confusing what is assumed with what is proved. $P(k)$ is assumed (the inductive hypothesis); $P(k+1)$ is what must be derived. Writing the target equation for $P(k+1)$ and manipulating both sides "to make it true" reverses the logic of the argument.
• Forgetting to adjust the base case for a restricted domain. A claim true only for $n \geq 5$ (as in Section 4) needs base case $n=5$, not $n=1$ — check the claim's stated domain before starting.
• Sloppy algebra hiding the factor the problem asks for. In a divisibility proof, the final expression must be explicitly factored to display the required divisor (e.g. $6(7m+1)$, not left as $42m+6$) — an unfactored expression does not, by itself, demonstrate divisibility.
• Treating induction as proving a single case. Induction proves a statement for all $n$ in the stated range at once; checking the formula for a few specific values of $n$ (however many) is never a substitute for the inductive step.

Summary

• Principle of induction: if $P(1)$ is true (base case) and $P(k)\Rightarrow P(k+1)$ for every $k\geq1$ (inductive step), then $P(n)$ is true for all $n\in\mathbb{Z}^{+}$.
• The inductive hypothesis is the assumption $P(k)$ is true, used explicitly inside the inductive step to derive $P(k+1)$.
• Summation proofs: split off the last term of the $(k+1)$-sum, substitute the inductive hypothesis for the remaining $k$-term sum, and show the result algebraically matches the formula with $n=k+1$.
• Divisibility proofs: rewrite the inductive hypothesis to isolate the relevant power or term, substitute into the $(k+1)$-case, and factor out the required divisor explicitly.
• Inequality proofs: start from the inductive hypothesis, scale or manipulate it, and often need an auxiliary inequality to bridge to the $(k+1)$-case; the base case need not be $n=1$ if the claim only holds from some larger starting value.
• Strong induction allows the inductive step to assume all of $P(1),\ldots,P(k)$, useful when the recursive structure does not depend solely on the immediately preceding case.