Visual walkthrough — Mathematical induction — principle, steps, problems

We will build up in numbered steps. Each step tells you WHAT we did, WHY we did it, and shows a PICTURE.

---

Step 1 — What is the sum we are chasing?

WHAT. We stack blocks. Row 1 has $1$ block, row 2 has $2$ blocks, row 3 has $3$ blocks, and so on down to row $n$ which has $n$ blocks. The total number of blocks is $S(n)=\underset{\text{row }1}{\underbrace{1}}+\underset{\text{row }2}{\underbrace{2}}+\underset{\text{row }3}{\underbrace{3}}+\cdots +\underset{\text{row }n}{\underbrace{n}}.$

Here $S(n)$ is just a name for "the total number of blocks in a staircase that is $n$ rows tall." The symbol $n$ is a natural number: $1,2,3,\dots$

WHY. Before proving any formula we must be dead sure what we are counting. Counting blocks in a staircase is something a 6-year-old can do by hand — so we can always sanity-check.

PICTURE. Look at the staircase of blocks below. The magenta blocks in row $r$ number exactly $r$.

---

Step 2 — The guess: two staircases make a rectangle

WHAT. Take a copy of the staircase, flip it upside-down, and slot it against the original. The two staircases interlock into a perfect rectangle.

WHY. A single staircase is jagged and hard to count. A rectangle is trivial to count: (width) $\times$ (height). This trick — double it to straighten it — is the geometric heart of the formula.

PICTURE. The magenta staircase is $S(n)$. The violet flipped copy is another $S(n)$. Together they fill a rectangle with no gaps and no overlaps.

Count the rectangle: $\underset{\text{two staircases}}{\underbrace{2S(n)}}=\underset{\text{width}}{\underbrace{(n+1)}}\times \underset{\text{height}}{\underbrace{n}}.$

Each term:

• $2S(n)$ — the two interlocked staircases,
• width $(n+1)$ — a full row has $n$ blocks plus one extra block from the flipped partner, so each row is $n+1$ wide,
• height $n$ — there are $n$ rows.

Divide by $2$: $S(n)=\frac{n(n+1)}{2}.$

This is our conjecture. But a picture for one specific $n$ is not a proof for all $n$ (recall Trap 1 from the parent: checking cases is not proof). So we now hand this guess to the induction machine.

---

Step 3 — Name the statement $P(n)$

WHAT. We give the claim a label so we can talk about it precisely: $P(n):1+2+\cdots +n=\frac{n(n+1)}{2}.$ $P(n)$ is a true-or-false sentence about a particular $n$. $P(3)$ says "$1+2+3=\frac{3\cdot 4}{2}$", i.e. "$6=6$" — true. $P(n)$ is not a number; it is a claim.

WHY. Induction proves a statement for every $n$. To run the machine we must be able to point at "$P(k)$" and "$P(k+1)$" as separate sentences.

PICTURE. Each domino below is labelled with a value of $n$. Domino $n$ standing = "$P(n)$ not yet known"; domino $n$ fallen = "$P(n)$ proven true."

Our goal: knock over every domino.

---

Step 4 — The base case: tip the first domino

WHAT. Check $P(1)$ directly. $\text{LHS}=1,\text{RHS}=\frac{1\cdot (1+1)}{2}=\frac{2}{2}=1.\text{LHS}=\text{RHS}✓$

WHY. A chain reaction needs a first event. If no domino ever falls on its own, the whole "each knocks the next" promise is empty (Trap 2 in the parent). The base case is that first physical push.

PICTURE. Domino $n=1$ is now tipping. Nothing else has moved yet — but the chain has a starting point.

---

Step 5 — The inductive hypothesis: assume domino $k$ fell

WHAT. Freeze on an arbitrary value $k\ge 1$ and assume $P(k)$ is true: $\underset{\text{sum of first }k}{\underbrace{1+2+\cdots +k}}=\frac{k(k+1)}{2}.(\text{IH})$ Call this the inductive hypothesis (IH).

WHY. We are not claiming $P(k)$ is proven for a specific number. We are saying: "suppose domino $k$ has fallen — let me show it must topple domino $k+1$." Because $k$ is arbitrary, whatever we prove holds for every neighbour-pair. This is not assuming what we want (Trap 3): we assume $P(k)$ — one domino — and will derive $P(k+1)$ — the next domino.

PICTURE. Domino $k$ is drawn already fallen (the assumption), leaning toward the still-standing domino $k+1$.

---

Step 6 — The inductive step: force domino $k+1$ to fall

WHAT. We want $P(k+1)$, whose left side is $1+2+\cdots +k+(k+1)$ — that is, the same sum as before with one extra term $(k+1)$ added on the end. So we add $(k+1)$ to both sides of the IH.

Start from the IH and add $(k+1)$: $\underset{=\frac{k(k+1)}{2}\text{by IH}}{\underbrace{[1+2+\cdots +k]}}+(k+1)=\frac{k(k+1)}{2}+(k+1).$

WHY this move. $P(k+1)$'s left-hand side is literally $P(k)$'s left-hand side plus the next block-row. So the honest thing to do is add exactly that next term — nothing invented, nothing assumed about $k+1$.

Now simplify the right side. Factor out the common piece $(k+1)$:

= (k+1)\!\left[\frac{k}{2} + 1\right] = (k+1)\cdot\frac{k+2}{2} = \frac{(k+1)(k+2)}{2}.$$ Term by term: - $(k+1)$ pulled out front — it appears in both pieces, so factoring it is legal and tidy, - $\frac{k}{2}+1 = \frac{k+2}{2}$ — put over a common denominator, - result $\dfrac{(k+1)(k+2)}{2}$. **Is this $P(k+1)$?** Write out what $P(k+1)$ *should* say by replacing $n$ with $k+1$ in the formula: $$P(k+1): \quad 1+\cdots+(k+1) = \frac{(k+1)\big((k+1)+1\big)}{2} = \frac{(k+1)(k+2)}{2}.$$ This matches exactly what we derived. **Domino $k$ falling forces domino $k+1$ to fall.** **PICTURE.** The "$+ (k+1)$" is the little push that carries the fall from domino $k$ into domino $k+1$; the algebra reshapes $\frac{k(k+1)}{2}$ into $\frac{(k+1)(k+2)}{2}$ — the *same formula* one step further along. > [!formula] Inductive step complete > $$P(k)\ \text{true} \ \Longrightarrow\ 1+\cdots+(k+1) = \frac{(k+1)(k+2)}{2}\ =\ P(k+1)\ \text{true}.$$ --- ## Step 7 — The chain reaction: all dominoes fall **WHAT.** We now have two facts: 1. **Base (Step 4):** $P(1)$ is true. 2. **Step (Step 6):** for *every* $k$, $P(k)\Rightarrow P(k+1)$. Chain them: $P(1)$ true $\Rightarrow P(2)$ true $\Rightarrow P(3)$ true $\Rightarrow \cdots$ forever. Every domino topples. **WHY it really covers *all* $n$.** Could some domino $m$ stay standing? If a *smallest* stubborn domino $m$ existed, then $m\ne 1$ (domino 1 fell), so domino $m-1$ *did* fall — but Step 6 says a fallen $m-1$ knocks over $m$. Contradiction. No stubborn domino can exist. This is exactly the [[Well-Ordering Principle]] guaranteeing induction works. **PICTURE.** The whole row is now flat: $P(1), P(2), P(3), \dots$ all proven. $$\boxed{\ 1+2+\cdots+n = \frac{n(n+1)}{2}\quad\text{for all } n\ge 1.\ }$$ --- ## Step 8 — Edge and degenerate cases **WHAT.** Two boundary cases people worry about: **(a) The single-term case $n=1$.** The formula $\frac{1\cdot 2}{2}=1$ works — and this is *the same* thing as the base case. Good: the base case is not a special exception, it is the formula at its smallest allowed input. **(b) The empty sum $n=0$.** If we *extend* the definition to "add up zero rows," the sum is $0$ (adding nothing gives nothing). Plug $n=0$: $\frac{0\cdot 1}{2}=0$. **It still matches!** So the formula even survives the degenerate empty case, though our proof officially starts the dominoes at $n=1$. **WHY show these.** The parent's contract: never leave the reader in an unshown scenario. The formula is robust at its smallest and its empty input — nothing hidden breaks. **PICTURE.** A tiny two-panel check: $n=0$ (no blocks, value $0$) and $n=1$ (one block, value $1$), both matching the formula. > [!mistake] Don't skip the base just because the formula "looks obvious" > The staircase-into-rectangle picture (Step 2) *feels* like a proof, but geometrically we only drew one $n$. The dominoes (Steps 3–7) are what upgrade "looks true" into "is true for all $n$." Picture-intuition proposes; induction proves. --- ## The one-picture summary Everything at once: the base tips domino $1$; the inductive step is a repeatable "add $(k+1)$" gear that turns $\frac{k(k+1)}{2}$ into $\frac{(k+1)(k+2)}{2}$; the well-ordering guarantee closes the loop so the whole infinite row falls. > [!recall]- Feynman retelling (plain words) > I want to add up $1+2+3+\dots$ all the way to some number $n$. First I *see* the trick: stack the numbers as a staircase of blocks, copy it, flip the copy, and the two fit into a neat rectangle that is $n$ tall and $n+1$ wide. Two staircases fill $n(n+1)$ blocks, so one staircase is half that: $\frac{n(n+1)}{2}$. > > But a drawing only shows *one* height, so I make it airtight with dominoes. Domino number $n$ means "the formula is right for $n$." I tip over the first domino: for $n=1$, the formula gives $1$, and $1$ really is $1$. Then I show the *general knock*: if domino $k$ is down — meaning $1+\dots+k=\frac{k(k+1)}{2}$ — I just add the next number $k+1$ to both sides, tidy up, and out pops $\frac{(k+1)(k+2)}{2}$, which is exactly the formula for $k+1$. So any fallen domino always knocks over its neighbour. First one falls, each one knocks the next — so *all* of them fall, forever. That's the proof. --- ## Connections - [[Mathematical induction — principle, steps, problems (index 3.3.9)]] — the parent ritual this page draws out - [[Well-Ordering Principle]] — why "no smallest counterexample" seals the chain - [[Arithmetic & Geometric Series]] — this sum is the first arithmetic series - [[Sum of Squares and Cubes]] — the same add-the-next-term picture, one power up - [[3.3.09 Mathematical induction — principle, steps, problems (Hinglish)|Hinglish version]]