Mathematical induction — principle, steps, problems

WHAT is the Principle?

The assumption "$P(k)$ is true" used inside the inductive step is called the inductive hypothesis (IH).

WHY does this actually prove everything? Suppose $P$ failed somewhere. Let $m$ be the smallest number where it fails. Then $m \ne n_0$ (base case holds), so $m-1 \ge n_0$ and $P(m-1)$ is true (else $m-1$ would be smaller and failing). But the inductive step says $P(m-1)\Rightarrow P(m)$ — contradiction. So $P$ never fails. This is why PMI is equivalent to the Well-Ordering Principle (every nonempty set of naturals has a least element).

HOW to write an induction proof (the ritual)

The heart is step 4: you must manufacture $P(k+1)$ out of $P(k)$, usually by adding the "next term" to both sides.

Worked Example 1 — Sum of first $n$ naturals

Claim: $P(n):\ 1+2+\cdots+n = \dfrac{n(n+1)}{2}$.

Base case $n=1$: LHS $=1$, RHS $=\frac{1\cdot 2}{2}=1$. ✓ Why this step? Without a true starting domino, the chain proves nothing.

IH: assume $1+2+\cdots+k = \dfrac{k(k+1)}{2}$.

Step: Add the next term $(k+1)$ to both sides: $\underbrace{1+2+\cdots+k}_{\text{use IH}} + (k+1) = \frac{k(k+1)}{2} + (k+1)$ Why this step? $P(k+1)$'s LHS is just $P(k)$'s LHS plus one more term — so add exactly that term. $= (k+1)\left(\frac{k}{2}+1\right) = (k+1)\cdot\frac{k+2}{2} = \frac{(k+1)(k+2)}{2}.$ This is precisely $P(k+1)$ (replace $n$ by $k+1$ in the formula). By PMI, true for all $n\ge 1$. ∎

Worked Example 2 — Sum of squares

Claim: $P(n):\ 1^2+2^2+\cdots+n^2 = \dfrac{n(n+1)(2n+1)}{6}$.

Base $n=1$: LHS $=1$, RHS $=\frac{1\cdot2\cdot3}{6}=1$. ✓

IH: $\sum_{i=1}^{k} i^2 = \dfrac{k(k+1)(2k+1)}{6}$.

Step: add $(k+1)^2$: $\frac{k(k+1)(2k+1)}{6} + (k+1)^2 = (k+1)\left[\frac{k(2k+1)}{6} + (k+1)\right].$ Why this step? Factor out the common $(k+1)$ early — it's the target formula's leading factor. $= (k+1)\cdot\frac{k(2k+1)+6(k+1)}{6} = (k+1)\cdot\frac{2k^2+7k+6}{6} = (k+1)\cdot\frac{(k+2)(2k+3)}{6}.$ This equals $\dfrac{(k+1)(k+2)(2(k+1)+1)}{6}=P(k+1)$. By PMI, done. ∎

Worked Example 3 — Divisibility

Claim: $P(n):\ n^3 - n$ is divisible by $6$ for all $n\ge 1$.

Base $n=1$: $1-1=0$, and $6\mid 0$. ✓

IH: $6 \mid k^3-k$, i.e. $k^3-k = 6m$ for some integer $m$.

Step: Compute $(k+1)^3-(k+1)$: $(k+1)^3-(k+1) = k^3+3k^2+3k+1-k-1 = (k^3-k) + 3k^2+3k.$ Why this step? We isolate the "old" chunk $k^3-k$ (divisible by 6 by IH) plus a leftover. $= 6m + 3k(k+1).$ Now $k(k+1)$ is a product of two consecutive integers, so it's even, say $2t$. Then $3k(k+1)=6t$. Hence total $=6m+6t=6(m+t)$, divisible by 6. By PMI, done. ∎

Worked Example 4 — Inequality

Claim: $P(n):\ 2^n > n$ for all $n\ge 1$.

Base $n=1$: $2^1=2>1$. ✓

IH: $2^k > k$.

Step: $2^{k+1} = 2\cdot 2^k > 2k$ (using IH). Why this step? Multiply IH by 2 to get $2^{k+1}$. Now is $2k \ge k+1$? Yes for $k\ge 1$ since $2k-(k+1)=k-1\ge 0$. So $2^{k+1} > 2k \ge k+1$. ∎

Strong (Complete) Induction — a stronger tool

Active-Recall Flashcards

Connections

• Well-Ordering Principle — the logical foundation of induction
• Arithmetic & Geometric Series — many sum formulas are proved by induction
• Sum of Squares and Cubes — direct induction targets
• Divisibility and Modular Arithmetic — divisibility inductions
• Recurrence Relations & Fibonacci — natural home of strong induction
• Binomial Theorem — often proved by induction on $n$

Concept Map

Hinglish (regional understanding)