Worked examples — Mathematical induction — principle, steps, problems

This page is the drilling ground for the parent note. If a word here is unfamiliar (base case, inductive hypothesis, IH, PMI), go back and read the ritual first — everything below assumes you know those four steps.

The scenario matrix

Every cell is a distinct flavour of induction. The examples that follow are tagged with the cell they cover.

Ex 1 — Cell A · A sum formula (odd numbers)

Forecast (guess first!): Add up the first $n$ odd numbers. Try $n=3$: $1+3+5=9=3^2$. Do you believe the RHS is exactly $n^2$? Guess before reading on.

1. State $P(n)$: $1+3+\cdots +(2n-1)=n^2$. Why this step? We must write the exact object we'll manipulate, including the general term $2n-1$ (the $n$-th odd number).
2. Base case $n=1$: LHS $=2(1)-1=1$, RHS $=1^2=1$. ✓ Why this step? Without a true first domino the chain is empty.
3. IH: assume $1+3+\cdots +(2k-1)=k^2$ for a fixed $k\ge 1$.
4. Step: the $(k+1)$-th odd number is $2(k+1)-1=2k+1$. Add it to both sides: $\underset{=k^2\text{ by IH}}{\underbrace{1+3+\cdots +(2k-1)}}+(2k+1)=k^2+2k+1=(k+1{)}^2.$ Why this step? $P(k+1)$'s LHS is $P(k)$'s LHS plus exactly one more term — so add precisely that term. And $k^2+2k+1$ is the perfect square $(k+1{)}^2$, which is $P(k+1)$'s RHS. By PMI, done. ∎

Verify: $n=5$: LHS $=1+3+5+7+9=25$, RHS $=5^2=25$. ✓

The figure shows why odd numbers build squares: each odd number is the L-shaped border ("gnomon") you add to grow an $k\times k$ square into a $(k+1)\times (k+1)$ square. That L has $k$ cells on top, $k$ on the side, minus the shared corner $=2k+1$ cells. That is exactly step 4, drawn.

Ex 2 — Cell B · Sum of cubes

Forecast: The RHS is the square of the sum of the first $n$ naturals. So the sum of cubes equals $(1+2+\cdots +n{)}^2$. Surprising? Guess whether $1^3+2^3=(1+2{)}^2$.

1. State $P(n)$: ${\sum }_{i=1}^n{i}^3={\left(\frac{n(n+1)}{2}\right)}^2$.
2. Base $n=1$: LHS $=1$, RHS $={\left(\frac{1\cdot 2}{2}\right)}^2=1^2=1$. ✓
3. IH: $\sum _{i=1}^k{i}^3={\left(\frac{k(k+1)}{2}\right)}^2$.
4. Step: add $(k+1{)}^3$: ${\left(\frac{k(k+1)}{2}\right)}^2+(k+1{)}^3=(k+1{)}^2\left[\frac{k^2}{4}+(k+1)\right].$ Why this step? Factor out $(k+1{)}^2$ early — the target RHS ${\left(\frac{(k+1)(k+2)}{2}\right)}^2$ contains $(k+1{)}^2$, so pulling it out steers us straight to the goal. $=(k+1{)}^2\cdot \frac{k^2+4k+4}{4}=(k+1{)}^2\cdot \frac{(k+2{)}^2}{4}={\left(\frac{(k+1)(k+2)}{2}\right)}^2.$ That is $P(k+1)$. By PMI, done. ∎

Verify: $n=4$: LHS $=1+8+27+64=100$, RHS $={\left(\frac{4\cdot 5}{2}\right)}^2=10^2=100$. ✓

Ex 3 — Cell C · A product / telescoping formula

Forecast: A product of shrinking factors. Guess: does it settle toward $\frac{1}{2}$ as $n$ grows? (Look at the RHS $\frac{n+1}{2n}\to \frac{1}{2}$.)

1. State $P(n)$: $\left(1-\frac{1}{2^2}\right)\left(1-\frac{1}{3^2}\right)\cdots \left(1-\frac{1}{n^2}\right)=\frac{n+1}{2n}$. Why this step? Note $n_0=2$ here — the product starts at $i=2$ because $1-\frac{1}{1^2}=0$ would kill everything.
2. Base $n=2$: LHS $=1-\frac{1}{4}=\frac{3}{4}$, RHS $=\frac{3}{4}$. ✓
3. IH: product up to $k$ equals $\frac{k+1}{2k}$.
4. Step: multiply both sides by the next factor $\left(1-\frac{1}{(k+1{)}^2}\right)$: $\frac{k+1}{2k}\cdot \left(1-\frac{1}{(k+1{)}^2}\right).$ Why this step? For a product formula, $P(k+1)$'s LHS is $P(k)$'s LHS times one more factor — so multiply, don't add. Now $1-\frac{1}{(k+1{)}^2}=\frac{(k+1{)}^2-1}{(k+1{)}^2}=\frac{k(k+2)}{(k+1{)}^2}$. Substitute: $\frac{k+1}{2k}\cdot \frac{k(k+2)}{(k+1{)}^2}=\frac{k+2}{2(k+1)}=\frac{(k+1)+1}{2(k+1)}.$ That is $P(k+1)$. By PMI, done. ∎

Verify: $n=4$: LHS $=\frac{3}{4}\cdot \frac{8}{9}\cdot \frac{15}{16}=\frac{360}{576}=\frac{5}{8}$, RHS $=\frac{5}{8}$. ✓

Ex 4 — Cell D · Divisibility (all cases of the leftover)

Forecast: $7\equiv 1(\mathrm{mod}6)$, so a power of $7$ should be $\equiv 1$, making $7^n-1\equiv 0$. Guess whether it always works. (See Divisibility and Modular Arithmetic for the "$\equiv$" shorthand.)

1. State $P(n)$: $6\mid 7^n-1$, i.e. $7^n-1=6m$ for some integer $m$.
2. Base $n=1$: $7^1-1=6=6\cdot 1$. ✓
3. IH: $7^k-1=6m$ for some integer $m$, so $7^k=6m+1$.
4. Step: compute the next case: $7^{k+1}-1=7\cdot 7^k-1=7(6m+1)-1=42m+7-1=42m+6=6(7m+1).$ Why this step? We rewrite $7^{k+1}$ using $7^k=6m+1$ from the IH, so the "old divisible chunk" resurfaces and the leftover ($+6$) is itself a multiple of $6$. Since $7m+1$ is an integer, $6\mid 7^{k+1}-1$. By PMI, done. ∎

Verify: $n=3$: $7^3-1=343-1=342=6\cdot 57$. ✓ (integer quotient, so divisible.)

Ex 5 — Cell E · Inequality with a leftover to bound

Forecast: For small $n$ this is false ($n=3$: $8<9$). It only kicks in at $n=4$. Guess the base case value.

1. State $P(n)$: $2^n\ge n^2$.
2. Base $n=4$: $2^4=16$, $4^2=16$, and $16\ge 16$. ✓ Why here? At $n=2$: $4=4$ ✓, but $n=3$: $8<9$ ✗. The statement is only true from $n=4$ on, so we must start the dominoes at $4$. This is Cell F territory too (a non-1 base).
3. IH: $2^k\ge k^2$ for a fixed $k\ge 4$.
4. Step: double the IH: $2^{k+1}=2\cdot 2^k\ge 2k^2$. Why this step? Multiplying by $2$ turns $2^k$ into $2^{k+1}$ — the exact left side we need. Now we must show $2k^2\ge (k+1{)}^2$. Expand the gap: $2k^2-(k+1{)}^2=2k^2-k^2-2k-1=k^2-2k-1=(k-1{)}^2-2.$ Why this step? We need the leftover $2k^2$ to still dominate the target $(k+1{)}^2$. For $k\ge 4$, $(k-1{)}^2\ge 9>2$, so $(k-1{)}^2-2>0$, giving $2k^2\ge (k+1{)}^2$. Chaining: $2^{k+1}\ge 2k^2\ge (k+1{)}^2$. By PMI, done. ∎

Verify: $n=5$: $2^5=32\ge 25=5^2$ ✓. $n=6$: $64\ge 36$ ✓.

Ex 6 — Cell F · Base case not 1 (Bernoulli-style inequality)

Forecast: At $n=1$: $3>3$? No, equal. So it's strict only from $n=2$. Guess where to start.

1. State $P(n)$: $3^n>2n+1$.
2. Base $n=2$: $3^2=9$, $2(2)+1=5$, and $9>5$. ✓ Why $n_0=2$? At $n=1$, $3^1=3=2(1)+1$ — equality, not strict. So the smallest $n$ where the strict inequality holds is $2$. Starting the chain at $2$ is legitimate: PMI just proves the statement for all $n\ge n_0$.
3. IH: $3^k>2k+1$ for fixed $k\ge 2$.
4. Step: triple the IH: $3^{k+1}=3\cdot 3^k>3(2k+1)=6k+3$. Why this step? Multiply by $3$ to build $3^{k+1}$. Now compare to the target $2(k+1)+1=2k+3$: $6k+3-(2k+3)=4k>0(k\ge 2).$ So $3^{k+1}>6k+3>2k+3=2(k+1)+1$. By PMI, done. ∎

Verify: $n=3$: $27>7$ ✓. $n=4$: $81>9$ ✓.

Ex 7 — Cell G · Strong induction (Fibonacci needs two earlier cases)

Forecast: Fibonacci grows fast — but does it out-race powers of two? Guess whether $F_n$ stays under $2^{n-1}$. (Background: Recurrence Relations & Fibonacci.)

1. State $P(n)$: $F_n\le 2^{n-1}$.
2. Base cases (need TWO):
   • $n=1$: $F_1=1\le 2^0=1$ ✓
   • $n=2$: $F_2=1\le 2^1=2$ ✓ Why two base cases? The recurrence $F_{k+1}=F_k+F_{k-1}$ reaches back two steps. To prove $P(k+1)$ we'll use $P(k)$ and $P(k-1)$, so both must be anchored. This is the signature of strong induction.
3. Strong IH: assume $F_j\le 2^{j-1}$ for all $j$ with $1\le j\le k$ (a fixed $k\ge 2$).
4. Step: for $k+1$, $F_{k+1}=F_k+F_{k-1}\le 2^{k-1}+2^{k-2}.$ Why this step? We apply the IH to both $F_k$ and $F_{k-1}$ — allowed because strong induction hands us every earlier case. $2^{k-1}+2^{k-2}=2^{k-2}(2+1)=3\cdot 2^{k-2}\le 4\cdot 2^{k-2}=2^k=2^{(k+1)-1}.$ Why the last bound? $3\le 4$, and $4\cdot 2^{k-2}=2^2\cdot 2^{k-2}=2^k$. That is $P(k+1)$. By strong PMI, done. ∎

Verify: $n=6$: $F_6=8\le 2^5=32$ ✓. $n=7$: $F_7=13\le 64$ ✓.

Ex 8 — Cell H · Degenerate / empty case ($n=0$)

Forecast: What does the left side mean when $n=0$? There are no terms. Guess its value before reading.

1. Convention first: an empty sum (no terms) equals $0$; an empty product equals $1$. These are the "identity" values: adding $0$ or multiplying by $1$ changes nothing. Why care? Many exam statements are quietly true at $n=0$, and a clean proof can use $n_0=0$ as its base case.
2. State $P(n)$: ${\sum }_{i=1}^{n}i=\frac{n(n+1)}{2}$.
3. Base $n=0$: LHS $=$ empty sum $=0$; RHS $=\frac{0\cdot 1}{2}=0$. ✓ The formula survives the degenerate case.
4. Step (same as parent Ex 1): IH ${\sum }_{i=1}^{k}i=\frac{k(k+1)}{2}$; add $(k+1)$: $\frac{k(k+1)}{2}+(k+1)=(k+1)\frac{k+2}{2}=\frac{(k+1)(k+2)}{2}.$ Why this step? Add the next term — the same sum move, now anchored one domino earlier at $n=0$. By PMI, true for all $n\ge 0$. ∎

Verify: $n=0$: both sides $0$ ✓. $n=1$: LHS $1$, RHS $\frac{1\cdot 2}{2}=1$ ✓.

Ex 9 — Cell I · Real-world word problem (handshakes)

Forecast: Add one late guest to a party. How many new handshakes does that guest add? Guess before Step 4.

1. State $P(n)$: with $n$ people, handshakes $H(n)=\frac{n(n-1)}{2}$.
2. Base $n=1$: one person, nobody to shake with, $H(1)=0$; RHS $=\frac{1\cdot 0}{2}=0$. ✓ Why start at 1? A party can have one person; the count $0$ is the honest degenerate value (a Cell H flavour hiding inside a word problem).
3. IH: with $k$ people, $H(k)=\frac{k(k-1)}{2}$.
4. Step: person number $k+1$ walks in and shakes hands with each of the existing $k$ people — that's $k$ new handshakes, and no old ones change: $H(k+1)=H(k)+k=\frac{k(k-1)}{2}+k=\frac{k(k-1)+2k}{2}=\frac{k^2+k}{2}=\frac{(k+1)k}{2}.$ Why this step? We modelled the "next domino" as adding one guest, so the change is exactly the $k$ handshakes that guest performs. That is $P(k+1)$ (replace $n$ by $k+1$: $\frac{(k+1)k}{2}$). By PMI, done. ∎

Verify: $n=4$: pairs $\{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}=6$; RHS $=\frac{4\cdot 3}{2}=6$ ✓. (This is also the number of edges in a complete graph — see Arithmetic & Geometric Series for the same triangular numbers.)

Ex 10 — Cell J · Exam twist ("spot the bug")

Forecast: The base and the algebra look airtight. Guess which $k$ the step secretly fails at.

1. Re-examine the step's hidden assumption. The argument needs the two subsets (first $k$ and last $k$) to overlap in at least one horse, so their colours can be "linked". Why this matters? Without an overlapping horse, "first group same" and "last group same" are two unrelated facts — no bridge between them.
2. Test $k=1$, i.e. proving $P(2)$ from $P(1)$. We have $2$ horses $\{A,B\}$. Drop the last → $\{A\}$ mono (trivially). Drop the first → $\{B\}$ mono (trivially). Overlap $=\{A\}\cap \{B\}=\varnothing$ — empty! Why this is the bug: with $2$ horses the two sub-groups share no horse, so the colours of $A$ and $B$ are never actually compared. The inductive step $P(1)\Rightarrow P(2)$ is false.
3. Conclusion. The chain breaks at its very first link. Because the domino $P(1)\to P(2)$ never falls, nothing beyond $P(1)$ is proven — and indeed horses come in many colours. Lesson (Trap 3/4 from the parent): a step must work for every $k\ge n_0$, especially the smallest one. Always test the inductive step at the boundary.

Verify: the argument needs $k\ge 2$ for the overlap to be nonempty; the smallest required step is $k=1$, where overlap size $=k-1=0$. So the proof fails precisely at $k=1$. (No numeric formula to plug — the "check" is that $k-1=0$ when $k=1$.)

Connections

• Mathematical induction — principle, steps, problems — the ritual these examples drill
• Well-Ordering Principle — why induction is valid in the first place
• Sum of Squares and Cubes — Ex 2 is a direct target
• Arithmetic & Geometric Series — Ex 1, Ex 9 give triangular/square sums
• Divisibility and Modular Arithmetic — Ex 4's $\equiv$ shorthand
• Recurrence Relations & Fibonacci — Ex 7's strong induction
• Binomial Theorem — another classic induction-on-$n$ target

Concept Map