3.4 Mathematical and Strong Induction

The previous sections proved universal claims by choosing an arbitrary object. Some claims are indexed by consecutive integers:

and one case naturally supports later cases. Mathematical induction turns that dependency into a proof method.

Induction does not mean checking many examples. It proves a starting case and a general transmission rule. Together they cover infinitely many cases.

The two parts of mathematical induction

To prove $P(n)$ for every integer $n\ge n_0$, ordinary induction requires:

1. Base case: prove $P(n_0)$.

2. Inductive step: for an arbitrary $k\ge n_0$, assume $P(k)$ and prove $P(k+1)$.

The temporary assumption $P(k)$ is the inductive hypothesis. We do not assume the entire theorem. We assume one arbitrary case so we can prove that truth passes to its next case.

The logical pattern is

Why does this reach every case?

• the base establishes $P(n_0)$;

• the step gives $P(n_0+1)$;

• applying the step again gives $P(n_0+2)$;

• the chain continues through every integer at or above $n_0$.

The domino metaphor is useful only when both parts are remembered. Standing dominoes do not fall without a first push, and pushing one domino does not reach the rest if the spacing rule has a gap.

Change the induction stride. The rule $P(k)\to P(k+2)$ does not connect odd and even indices. A single base case reaches only one parity chain; adding a second base case can cover the other. The simulation exposes exactly which claims the stated base and step actually prove.

A complete induction proof of a summation formula

We will prove that for every positive integer $n$,

The dots mean that all consecutive integers from $1$ through $n$ are added.

Define the proposition

Base case

For $n=1$, the left side is $1$, and the right side is

Therefore $P(1)$ is true.

Inductive hypothesis

Let $k\ge1$ be arbitrary. Assume $P(k)$:

This assumption is a tool for proving the next case. It must be written explicitly so we know exactly what may be substituted.

Inductive step

The $(k+1)$-case adds one new term:

Use the inductive hypothesis to replace the first block:

This final expression is exactly the formula with $n=k+1$:

Thus $P(k+1)$ follows from $P(k)$.

Conclusion

The base case $P(1)$ is true, and $P(k)\to P(k+1)$ holds for every $k\ge1$. Therefore, by mathematical induction,

for every positive integer $n$.

Common induction failures

Induction proofs often fail in recognizable ways:

Before finishing, point to the exact line where the inductive hypothesis is used. If it is never used, the proof may be a valid direct argument, or it may be missing the essential connection.

Strong induction may use all earlier cases

In strong induction, the inductive hypothesis assumes every case from the starting point through $k$:

and uses them to prove $P(k+1)$.

Ordinary induction assumes $P(k)$ alone. Strong induction gives access to a whole verified history. The two methods are logically equivalent in proving power, but one may match a problem’s dependency structure more naturally.

Strong induction is useful when the next object is built from a smaller object that is not necessarily the immediate predecessor. Examples later in the course include recursive algorithms, factorizations, and tree structures.

Worked strong-induction proof with postage

Theorem. Every integer postage amount $n\ge12$ can be formed using only $4$-unit and $5$-unit stamps.

First verify four consecutive base cases:

Now let $k\ge16$ and assume every amount from $12$ through $k-1$ can be formed. We must form $k$.

Since

the amount $k-4$ lies among the earlier cases covered by the strong inductive hypothesis. Form $k-4$ using $4$- and $5$-unit stamps, then add one more $4$-unit stamp. The result has value

Therefore $k$ can also be formed. By strong induction, every amount $n\ge12$ is possible.

Why were four base cases needed? The step reaches back by $4$. Consecutive bases $12,13,14,15$ start all four residue chains; one base would leave gaps.

Change stamp denominations and the claimed starting amount. The map distinguishes verified reachability from a wishful statement that “large values should work.” For $4$ and $5$, inspect the consecutive base window and then trace each later amount to an earlier reachable amount.

Chapter bridge

Chapter 3 assembled a proof toolkit: precise definitions, counterexamples, direct proof, cases, contraposition, contradiction, witnesses, uniqueness, and induction. Chapter 4 will use these methods to study functions and relations. The definitions will become richer, but the proof questions remain familiar: What must be shown, what evidence is sufficient, and which strategy makes the logical dependency clearest?