Skip to content
LearnMathora

Discrete mathematics · 04 · Infinity from a ladder · 9 min

Recursion & induction

How do you prove something for all infinity of the natural numbers — or compute with a structure nested inside itself? The same trick, worn two ways: secure step one, secure each step's handoff to the next, and the whole infinite ladder is yours.

Build the intuition

Induction: base case + handoff

Claim: 1+2+⋯+n = n(n+1)/2. Check n = 1: true. Then show: if it holds for n, adding (n+1) keeps it holding. Those two facts together topple the infinite line of dominoes — every n is reached by finitely many handoffs from the base. Two finite checks, infinitely many theorems.

1+2+⋯+n=n(n+1)21 + 2 + \cdots + n = \frac{n(n+1)}{2}

Recursion: the same ladder, descended

A recursive definition builds big cases from smaller ones: factorial(n) = n × factorial(n−1), stopping at factorial(0) = 1. Induction climbs up to prove; recursion calls down to compute. A folder containing folders, a fractal coastline, this very sentence's grammar — self-similar things demand self-referring tools.

Divide and conquer

Recursion's killer app: split the problem in half, solve each half (recursively), merge. Merge sort orders a million items in ~20 levels of splitting because halving reaches 1 in log₂(n) steps. The same halving logic is why binary search finds a name in a billion-entry list in 30 peeks.

See it move

InteractiveCounting without listing

number of heads k

6
With 6 coin flips there are 64 possible sequences (2 choices, 6 times: 2^6). The bars count how many land exactly k heads — Pascal's triangle, row 6, and already the outline of a bell curve.

Pascal's triangle is recursion you can see: every count is built from the row above it — base case at the tip, handoffs all the way down.

A worked example

Prove the domino formula

  1. Base: n = 1. Left side: 1. Right side: 1·2/2 = 1 ✓

  2. Handoff: assume 1+⋯+n = n(n+1)/2. Add (n+1):

    n(n+1)2+(n+1)=(n+1)(n+2)2\frac{n(n+1)}{2} + (n+1) = \frac{(n+1)(n+2)}{2}

  3. That's the formula with n+1 in n's place — the handoff succeeds, and the claim holds for every natural number, forever. Gauss's party trick, certified.

Out in the world

Proving software can't fail

Flight-control and payment systems are verified by induction: prove the system starts in a safe state (base), prove every possible operation preserves safety (handoff) — conclude safety holds after any number of operations. Critical infrastructure runs on lesson-four logic.

Common confusion, cleared

“Induction assumes what it's proving.”

It assumes the case for n only to secure the handoff to n+1 — like checking each domino reaches its neighbor. The base case supplies the initial push; nothing is circular.

“Recursion without end loops forever.”

Correct recursion always shrinks toward a base case — that's the contract. (Break it and your program does indeed discover infinity, briefly.)

Check yourself

PracticeQuick check

  1. An inductive proof needs…

  2. How many halvings get 1,000,000 down to 1?

Recap

  • Induction = base case + inductive handoff = proof for all n.
  • Recursion computes by self-reference shrinking to a base case.
  • Divide-and-conquer halving gives the log-speed algorithms behind search and sort.