Proof by Induction

Pick a claim about every whole number n. Each domino below is one n, coloured by whether the claim is true there, checked directly. The arrow out of a domino is the inductive step from n to n + 1. Only a true base domino with an unbroken run of arrows after it is a proof, and the dominoes that run reaches fall over.

Worked example — Proof by Induction

Step from 1 to 2	fails
Proved, among n up to 12	1
First false n, up to 12	2

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

The theory — Proof by Induction

Proof by induction proves a statement P(n) for every whole number n from some n₀ on, in two parts: the base case, P(n₀) checked directly, and the inductive step, an argument that P(k) forces P(k + 1) for every k ≥ n₀. Together they reach every n, the way each falling domino knocks over the next.

What each symbol means

P(n): the statement about n; at each n it is simply true or false
n₀: the base case, where the proof starts, checked by hand
k: a general n inside the step: the argument assumes P(k) and must reach P(k + 1)

Where the formula comes from

Why the two parts are enough. Suppose the base case holds and the step works for every k ≥ n₀, but P is false somewhere from n₀ on. Among the n where it is false there is a smallest; call it m. It is not n₀, because P(n₀) was checked, so m − 1 ≥ n₀, and P(m − 1) is true because m was the smallest failure. The step then gives P(m), which contradicts P(m) being false. So there is no failure. Both parts are used: without the base, m could be n₀; with the step missing at a single k, m could be k + 1.
Why n² + n + 41 had to fail. At n = 40 the first two terms combine, 40² + 40 = 40 × 41, so 40² + 40 + 41 = 40 × 41 + 41 = 41 × 41. At n = 41 every term is a multiple of 41, and the value is 41 × 43. The idea goes further: no polynomial with whole-number coefficients that is not a constant can give only primes, however many it gives first (Lehman, Leighton and Meyer prove it in Problem 1.25). So no inductive step for this claim could ever have existed.
2ⁿ > n² for every n ≥ 5, done properly. Base case: 2⁵ = 32 > 25 = 5². Step: let k ≥ 5 and assume 2ᵏ > k². Then 2ᵏ⁺¹ = 2 · 2ᵏ > 2k² = k² + k². Since k ≥ 5, k² ≥ 5k = 2k + 3k > 2k + 1, so 2k² > k² + 2k + 1 = (k + 1)², and 2ᵏ⁺¹ > (k + 1)², which is P(k + 1). The step itself needs only k ≥ 3. The base had to be 5 because P(2), P(3) and P(4) are false.

Forty true cases, then 41 × 41 🖖

Press n² + n + 41. The values 41, 43, 47, 53, 61, … are prime for every n from 0 to 39, forty in a row, and at n = 40 the value is 1,681 = 41 × 41. You can see it coming once you look: 40² + 40 + 41 = 40 × 41 + 41. The chart has no arrows because there is no step. Knowing that p(39) = 1,601 is prime says nothing about p(40), which is p(39) + 80. Of the first thousand values 581 are prime, which is why the pattern is so persuasive.

The step for 2ⁿ > n² works from k = 3; the claim only from n = 5 🖖

Press 2ⁿ > n² from 1. The base case holds, since 2 > 1. The step says that if 2ᵏ > k², then 2ᵏ⁺¹ > 2k², and 2k² ≥ (k + 1)² exactly when k² ≥ 2k + 1, which is true from k = 3. So from n₀ = 1 the arrows out of 1 and 2 are broken, and the claim is false at 2, 3 and 4. The arrows out of 3 and 4 work while P(3) and P(4) are both false: a correct step with a false domino behind it pushes nothing. Press 2ⁿ > n² from 5 and the same arrows prove every n from 5 on.

The horses argument is right at every step but one 🖖

Press The horses. The step takes n + 1 horses, applies the claim to the first n and to the last n, and joins them through the horses the two groups share. From n = 2 on that works, and every arrow from 2 onward is solid. From 1 to 2 the groups are one horse each and share none, so the argument proves nothing at the one place it is needed. Put the base at 5 instead and every step works, but P(5) is false, and the chain has nothing to push.

Problem solved in full

From where on does 2ⁿ stay ahead of n³? 4 steps
Prove that 2ⁿ > n³ for every large enough n. The step is easy to write down. Where does it start working, and where must the base case be?

Open this problem in the tool
1. Assume P(k): 2ᵏ > k³. Doubling is the only move available:
  
  $2^{k} > k^{3} \Rightarrow 2^{k + 1} = 2 \cdot 2^{k} > 2 k^{3}$
2. So the step works when 2k³ ≥ (k + 1)³. Divide both sides by k³:
  
  $2 k^{3} \geq (k + 1)^{3} ⟺ (1 + \frac{1}{k})^{3} \leq 2 ⟺ k \geq \frac{1}{3 2 - 1} = 3.847$
3. The step works from k = 4, not from 3:
  
  $k = 3 : 2 \cdot 27 = 54 < 64 = 4^{3}, k = 4 : 2 \cdot 64 = 128 \geq 125 = 5^{3}$
4. But the claim itself is false from n = 2 to n = 9. The base case is the first n where it holds again:
  
  $2^{9} = 512 < 729 = 9^{3}, 2^{10} = 1, 024 > 1, 000 = 1 0^{3}$
Answer

2ⁿ > n³ holds for every n ≥ 10, and at n = 0 and 1. The step works from k = 4, so for k = 4 to 9 a correct step sits behind a false claim, just as 2ⁿ > n² does at 3 and 4 on this page. Press 2ⁿ > n² from 5 to compare.

$2^{n} > n^{3} for every n \geq 10 (and n = 0, 1); step from k = 4, base n_{0} = 10$

Learning path

Methods of proof

References (3)

Both of this page's broken arguments, worked through: n² + n + 41 prime through n = 39 and 41·41 at n = 40 (§1.1), and the horses, whose failure the text pins to the one step P(1) → P(2) (§5.1): E. Lehman, F. T. Leighton and A. R. Meyer, Mathematics for Computer Science, MIT, revised 6 June 2018, §1.1 and §5.1.
The primes n² + n + 41 takes, with the forty consecutive prime values from n = 0 to 39: OEIS Foundation, "A005846: Primes of the form k² + k + 41", The On-Line Encyclopedia of Integer Sequences.
Where the horses come from: George Pólya posed the argument as an induction exercise in 1954: ProofWiki, "All Horses are the Same Colour/Historical Note", citing G. Pólya, Induction and Analogy in Mathematics (Princeton University Press, 1954).

By the 42Math team · Reviewed against published sources. Corrections welcome.