2.1 Mathematical induction

Why induction is needed

Many early MATH1025 statements are not about one number. They are about every positive integer at once. Checking the first few cases can suggest a pattern, but it does not prove the pattern. For example,

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

is true for $n=1,2,3,4$, but the statement claims infinitely many facts. A finite table cannot justify all of them. Mathematical induction is the proof principle that turns one verified starting point and one repeatable implication into a proof for every positive integer.

The hidden idea is simple: once the first statement is true, and once truth of one statement always forces truth of the next, the chain cannot break.

Statements indexed by integers

Before writing an induction proof, always state P(n) explicitly. This avoids two common errors: proving a different formula from the one claimed, or using the induction assumption without knowing exactly what it says.

The second condition is not the statement $P(k+1)$ by itself. It is a conditional statement: assuming P(k), prove $P(k+1)$. The proof is allowed to use the assumption P(k), but only after clearly declaring it.

The standard proof format

An induction proof normally has four visible pieces:

1. Define P(n).
2. Verify the base case.
3. Prove the induction step: assume P(k) for an arbitrary k in the allowed range and deduce $P(k+1)$.
4. Invoke the induction principle.

This format is not decoration. It records exactly where the infinite claim enters the proof.

The key line in the example is not the algebra alone. It is the moment where the assumed formula for the first k cubes is used to rewrite the first part of the sum for $k+1$.

Divisibility induction

Induction is not limited to closed-form sums. It also proves divisibility statements.

The proof works because the induction assumption gives a precise multiple of 3, not merely a vague pattern.

What can go wrong

Variations

Sometimes the first relevant integer is not 1. If a statement begins at $n_0$, the base case is $P(n_0)$, and the induction step must prove $P(k+1)$ from P(k) for every $k \ge n_0$.

Sometimes a problem naturally splits into even and odd cases. Then an induction step from P(k) to $P(k+2)$ may be used, but it needs the correct starting case for the parity being proved.

Strong induction is useful when the next case depends on several earlier cases, not only the immediately previous one.

Quick checks

Exercises

1. Prove by induction that 1+2+\cdots+n=n(n+1)/2 for every $n \in Z^+$.
2. Prove that $4 \mid (5^n-1)$ for every $n \in Z^+$.
3. Prove that $n^2<2^n$ for every integer $n \ge 5$.
4. Explain precisely why the overlapping-subset argument in the false proof fails at the first nontrivial transition.

Guided solutions

1. Let P(n) be the summation formula. The base case is immediate. For the step, add $k+1$ to the formula for $1+\cdots+k$ and simplify to (k+1)(k+2)/2.
2. Base case: $5-1=4$. If $5^k-1=4q$, then $5^{k+1}-1=5(5^k)-1=5(4q+1)-1=20q+4=4(5q+1)$.
3. Start at $n=5$. If $k^2<2^k$ and $k \ge 5$, then $(k+1)^2=k^2+2k+1<2^k+2^k=2^{k+1}$ because $2k+1<2^k$ for $k \ge 5$.
4. The two subsets used in the induction step overlap only when $n \ge 2$. The step from one object to two objects therefore has no shared object, so the argument cannot transfer the property.