PG3.1 Why induction works

Simulate

Check the claim with numbers

Lesson 1.5.1 built a sequence from a rule: start at $a_1 = 1$ , and make each term from the one before by $a_{n+1} = 2a_n + 1$ . Its terms 1, 3, 7, 15 suggested a formula, $a_n = 2^n - 1$ . Test it on many more terms.

terms = [1] # a_1 = 1 for n in range(1, 30): terms.append(2 * terms[-1] + 1) # a_(n+1) = 2a_n + 1 print(terms[:8]) print([2**n - 1 for n in range(1, 9)]) print(all(terms[n - 1] == 2**n - 1 for n in range(1, 31)))

⌘/Ctrl + Enter runs the cell

The first eight terms match, and the last line prints True: all thirty agree. Python's whole numbers are exact, so no rounding can hide a gap.

The formula also depends on where the sequence starts. Keep the rule, but start at $a_1 = 2$ :

terms = [2] # the same rule, a different first term for n in range(1, 8): terms.append(2 * terms[-1] + 1) print(terms) print([t - (2**n - 1) for n, t in enumerate(terms, start=1)])

⌘/Ctrl + Enter runs the cell

Now every term misses: 2, 5, 11, 23 against 1, 3, 7, 15. The misses are 1, 2, 4, 8, …, because the rule doubles the first error at every step. So a proof must use both the rule and the first term.

Conjecture

a_1 = 1

Thirty terms agree. That is evidence, not a proof: the claim is about every $n$ , and no computer can check them all. The next section shows a pattern that holds for a long time and then fails.

Checking is not proving

A claim about every whole number $n$ is really infinitely many claims, one for each $n$ . A computer can check a million of them and still miss the one that fails. Here is a claim that survives more than a hundred checks.

Grow $1 in two ways. With 2% simple interest a period (case study 0.3.5), after $n$ periods it is worth $1 + 0.02n$ . With 1% compounded each period (case study 1.4.6), it is worth $1.01^n$ .

1.01^n < 1 + 0.02n

from fractions import Fraction n = 1 while Fraction(101, 100) ** n < 1 + Fraction(2, 100) * n: n = n + 1 print("first failure:", n) for m in [127, 128]: print(m, round(float(Fraction(101, 100) ** m), 4), 1 + 0.02 * m)

⌘/Ctrl + Enter runs the cell

Someone who checked the first 100 periods would believe a false claim. A claim about every $n$ needs an argument that covers every $n$ at once, and induction is one.

How induction proves every case

Write $P(n)$ for the claim about $n$ . Here $P(n)$ says that $a_n = 2^n - 1$ , so $P(1)$ says $a_1 = 1$ and $P(2)$ says $a_2 = 3$ . Induction proves $P(n)$ for every $n \ge 1$ with two arguments instead of infinitely many checks.

Rule: Proof by induction

\begin{gathered} P(1) \text{ is true} \\ P(k) \Rightarrow P(k+1) \text{ for every } k \ge 1 \\ \text{so } P(n) \text{ is true for every } n \ge 1 \end{gathered}

The base case proves $P(1)$ . The inductive step proves that whenever $P(k)$ is true, so is $P(k + 1)$ . Its assumption, $P(k)$ , is the induction hypothesis.

The arrow $\Rightarrow$ reads "implies". The inductive step does not claim that $P(k)$ is true. It claims only that if $P(k)$ is true, then $P(k + 1)$ is true too.

Together the two steps reach every case. The base case gives $P(1)$ , the step with $k = 1$ turns it into $P(2)$ , and the step with $k = 2$ turns that into $P(3)$ . Any $n$ is reached after $n - 1$ uses of the step.

Think of a row of dominoes: the first one falls, and each one knocks over the next, so they all fall.

a_k = 2^k - 1

import sympy as sp k = sp.symbols("k", integer=True, positive=True) next_term = 2 * (2**k - 1) + 1 # the rule applied to 2^k - 1 print(sp.expand(next_term)) print(sp.simplify(next_term - (2**(k + 1) - 1)))

⌘/Ctrl + Enter runs the cell

A recursive rule and induction fit together. The rule builds $a_{k+1}$ from $a_k$ , and the inductive step proves $P(k + 1)$ from $P(k)$ .

Format 1

Reorder the steps

Here is the induction proof of the conjecture, with its lines shuffled. Put them in this order: the claim, the base case, the inductive step, the conclusion.

By induction, $P(n)$ is true for every $n \ge 1$ : the formula $a_n = 2^n - 1$ holds.
Inductive step: fix $k \ge 1$ and assume $P(k)$ , that is, $a_k = 2^k - 1$ .
That is $2^{k+1} - 2 + 1 = 2^{k+1} - 1$ , so $P(k + 1)$ is true.
The rule and this assumption give $a_{k+1} = 2a_k + 1 = 2(2^k - 1) + 1$ .
Base case: $a_1 = 1$ and $2^1 - 1 = 1$ , so $P(1)$ is true.
Write $P(n)$ for the claim $a_n = 2^n - 1$ .

Why the chain cannot break

The dominoes are a picture, not a proof. The proof is an argument by contradiction (stage PG2). It rests on one basic property of the whole numbers, which we take as given.

Rule: Well-ordering

\begin{gathered} \text{every non-empty set} \\ \text{of whole numbers} \\ \text{has a smallest member} \end{gathered}

Any set of whole numbers $n \ge 1$ with at least one member has a smallest member. The real numbers do not behave like this: the positive numbers have no smallest member, since half of any one is smaller.

Suppose both steps hold, but some $P(n)$ is false. Among the failures, take the smallest, $m$ . It is not 1, because the base case holds; so $m - 1 \ge 1$ , and $P(m - 1)$ is true, because $m - 1$ is below the smallest failure.

The inductive step with $k = m - 1$ now makes $P(m)$ true. That contradicts the choice of $m$ , so there is no failure at all.

Read the other way, the argument says where a false claim breaks. At its smallest failure $m$ , either $m = 1$ and the base case fails, or $P(m - 1)$ is true and the step from $m - 1$ to $m$ fails.

4^n + 1

from fractions import Fraction def first_failure(claim): n = 1 while claim(n): n = n + 1 return n claims = { "4^n + 1 is a multiple of 3": lambda n: (4**n + 1) % 3 == 0, "3^n > n^3": lambda n: 3**n > n**3, "1.01^n < 1 + 0.02n": lambda n: Fraction(101, 100) ** n < 1 + Fraction(2, 100) * n, } for name, claim in claims.items(): m = first_failure(claim) print(f"{name}: fails at {m}; holds at {m - 1}: {m > 1 and claim(m - 1)}") print([(4**n + 1) % 3 for n in range(1, 11)])

⌘/Ctrl + Enter runs the cell

The first claim shows why the base case is not a formality. Its inductive step holds: if $4^k + 1$ is a multiple of 3, so is $4^{k+1} + 1 = 4(4^k + 1) - 3$ . Yet the claim fails for every $n$ the cell tries, since the remainder is always 2.

Format 1

Reorder the argument

This is the argument above, written as a proof that induction is valid. Put its lines in order.

This contradicts the choice of $m$ . So no $P(n)$ is false, and $P(n)$ holds for every $n \ge 1$ .
Suppose $P(1)$ is true and $P(k) \Rightarrow P(k + 1)$ for every $k \ge 1$ , but some $P(n)$ is false.
The inductive step with $k = m - 1$ turns $P(m - 1)$ into $P(m)$ , so $P(m)$ is true.
$P(1)$ is true, so $m \ne 1$ . Hence $m \ge 2$ , and $m - 1$ is a whole number with $m - 1 \ge 1$ .
$m - 1$ is smaller than $m$ , the smallest failure, so $P(m - 1)$ is true.
Then the set of $n$ with $P(n)$ false is not empty, so by well-ordering it has a smallest member, $m$ .

Starting somewhere else

Induction need not start at 1. To prove $P(n)$ for every $n \ge n_0$ , prove $P(n_0)$ , and the step $P(k) \Rightarrow P(k + 1)$ for every $k \ge n_0$ . The same argument works, with the smallest failure now at least $n_0$ .

Lesson PG3.2 uses the two steps to prove the geometric series formula of lesson 1.5.2. Lesson PG3.4 lets the step use every earlier case, not only the one before.

n

Why induction works

Check the claim with numbers

Checking is not proving

How induction proves every case

Rule: Proof by induction

Reorder the steps

Why the chain cannot break

Rule: Well-ordering

Reorder the argument

Starting somewhere else

Summary card

Free further reading