Proof by Induction: Climb an Infinite Ladder

Prove a statement for every natural number by checking one starting step and showing how each step follows.

By Rishipal Singh · · 5 min read

Prove the first domino falls, then prove each domino knocks down the next.
Visual guide: Prove the first domino falls, then prove each domino knocks down the next.

Mathematical induction is a method for proving that a statement is true for every natural number. Picture a row of dominoes: show the first one falls, then show that each falling domino knocks over the next.

The two parts of an inductive proof

  1. Base case: verify the statement for the first value, often n = 0 or n = 1.
  2. Inductive step: assume it is true for an arbitrary value k, then use that assumption to prove it for k + 1.

The assumption for k is called the inductive hypothesis. It is not a guess about one particular number; it is an assumption used to establish the next step for any k in the range.

A familiar example

To prove 1 + 2 + ... + n = n(n + 1)/2, first check the base case n = 1. For the step, assume the sum through k is k(k + 1)/2. Add the next term, k + 1, and simplify:

k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2

This is the same formula with n = k + 1, so the step is complete.

How to avoid a gap

State the base case clearly, name the exact inductive hypothesis, and show each algebraic transformation. Induction is especially useful for proving properties of recursive programs, sequences, and algorithms.

Practice: identify the induction steps

To prove a statement for every integer n ≥ 1 by induction, what two obligations must your proof establish?

Reveal the explanation

Show the base case (typically n = 1), then show the inductive step: assuming the statement holds for an arbitrary k ≥ 1, prove it holds for k + 1.