Discrete Mathematics and Proof

Strong induction and well-ordering

To prove a claim about n, what if the step needs the claim at some smaller value that you cannot name in advance, not at n - 1?

You need

How induction works: base case, hypothesis and stepPrecalculus

Where you are 3 in Proof by induction

Logic, proof and discrete math6

Proof techniques14

Proof by induction3

How induction works: base case, hypothesis and step Induction on a sum formula

Strong induction and well-ordering

When you reach for it

An ordinary induction step (how induction works) proves P(k+1) from P(k). That fits when case k+1 is case k with one piece more. Many objects break apart otherwise. A composite n splits as n = ab, and a may be 2, or \displaystyle \frac{n}{2}, or anything between. Halving n lands near \displaystyle \frac{n}{2}, nowhere near n - 1. The step needs the claim at a smaller value, but not one fixed in advance.

Strong induction hands the step every smaller case at once. Reach for it when breaking case n apart gives pieces of unknown size below n. Its partner, the well-ordering principle, runs the same idea as a contradiction: if the claim failed anywhere, there would be a smallest failure, and you show that it cannot exist.

The procedure

Day 1: the strong hypothesis

Let P(n) be a statement about each integer n \ge n_0. If the lines above the bar hold, the line below it holds.

\begin{array}{c} P(n_0) \text{ is true} \\ P(n_0) \land \cdots \land P(k) \to P(k+1) \\ \text{for every } k \ge n_0 \\ \hline P(n) \text{ is true for every } n \ge n_0 \end{array}

The assumption that P(n_0), \dots, P(k) all hold is the strong hypothesis, and the step may call on any of these cases, as often as it likes. Proofs often write n for k + 1: “Let n > n_0, and assume P(m) for every m with n_0 \le m < n.”

Figure 1Both steps prove P(k+1). Ordinary induction may assume only P(k); strong induction may assume every shaded case.

Every value the step calls on must be at least n_0, since the hypothesis says nothing below n_0, and strictly less than the value being proved, or the argument is circular.

Day 1: how many base cases

A base case is a value the step cannot handle, so the step decides the count. Try its argument at the smallest values one at a time.

If the step calls only on values it can always reach, such as a factor a with 2 \le a < n, the single base case P(n_0) is enough.
If the step for P(n) calls on P(n - r) for a fixed r, it runs only from n = n_0 + r, and the r values n_0, \dots, n_0 + r - 1 are base cases.
If the step splits into cases, such as even and odd, check the smallest value in each.

Day 1: why it is no stronger

Strong induction proves nothing that ordinary induction cannot. Let Q(n) say “P(n_0), \dots, P(n) all hold”. Then Q(n_0) is P(n_0). If Q(k) holds, the strong step gives P(k+1), and Q(k) with P(k+1) is Q(k+1). So ordinary induction proves Q(n) for every n \ge n_0, and Q(n) includes P(n). Strong induction is ordinary induction on “P holds up to n”; what it saves is carrying the earlier cases along by hand.

Day 2: the well-ordering principle

The well-ordering principle. Every nonempty set of positive integers has a least member, written \min S for the set S.

By a shift, a nonempty set of integers that are all at least some fixed c also has a least member (Exercise 18); so does every nonempty set of nonnegative integers.

The principle is taken as a basic property of the positive integers, and it is equivalent to induction. How induction works proves induction from it. The converse is a strong induction. Let S be a set of positive integers with no least member, and let P(n) say “n \notin S”. P(1) holds, or 1 would be least. If 1, \dots, k lie outside S, then k + 1 \notin S, or it would be least. So S is empty, and a nonempty set has a least member.

Day 2: proof by smallest counterexample

To prove P(n) for every n \ge n_0, suppose, for contradiction, that it fails somewhere. The failing values have a least member m, the smallest counterexample, and P holds from n_0 to m - 1. Use that to show either that P(m) holds after all, or that a smaller counterexample exists. Either contradicts the choice of m.

The first ending is strong induction turned around. The second, a smaller counterexample, is often built by dividing a solution by 2 or 3, and the counterexamples need only be measured by a positive integer (Example 5). The proof in Proof by contradiction that \displaystyle \sqrt{2} is irrational, by the smallest denominator, has this shape. On a set with no least member, such as \mathbb{Z}, “take the smallest counterexample” picks nothing (Example 7).

Worked examples

Examples 1 to 4 go with Day 1, Examples 5 to 7 with Day 2.

Example 1

Products of primes

Prove that every integer n \ge 2 is a product of primes. (A prime alone counts as a product with one factor.)

Solution

The step factors n, and the factors can be any size below n.

Proof. Let P(n) say “n is a product of primes”. Base case. 2 is prime. Step. Let n \ge 3 and assume P(m) for every m with 2 \le m < n. If n is prime, we are done. Otherwise n has a divisor a with 1 < a < n, and n = ab where \displaystyle b = \frac{n}{a} also satisfies 1 < b < n. By the hypothesis a = p_1 \cdots p_r and b = q_1 \cdots q_s with every p_i and q_j prime, so n = p_1 \cdots p_r q_1 \cdots q_s. By strong induction P(n) holds for every n \ge 2. \square

For instance 360 = 18 \cdot 20, with 18 = 2 \cdot 3 \cdot 3 and 20 = 2 \cdot 2 \cdot 5, so 360 = 2^3 \cdot 3^2 \cdot 5. Knowing that 359 is a product of primes says nothing about 360, so ordinary induction would be stuck.

This proves existence only. That the product is the same however n is split, apart from order, is the fundamental theorem of arithmetic, first met as unique factorization. One prime divisor comes more quickly from the least-divisor argument in There are infinitely many primes.

Example 2

A rule that looks back three terms

A sequence has c_1 = 1, c_2 = 2, c_3 = 4 and c_n = c_{n-1} + c_{n-2} + c_{n-3} for n \ge 4. Prove that c_n < 2^n for every n \ge 1.

Solution

The step for c_n calls on three earlier terms, so it needs n - 3 \ge 1. The values 1, 2 and 3 are base cases.

Proof. Base cases. c_1 = 1 < 2, c_2 = 2 < 4 and c_3 = 4 < 8. Step. Let n \ge 4 and assume c_m < 2^m for 1 \le m < n. Then

\begin{aligned} c_n &= c_{n-1} + c_{n-2} + c_{n-3} \\ &< 2^{n-1} + 2^{n-2} + 2^{n-3} \\ &= 7 \cdot 2^{n-3} < 8 \cdot 2^{n-3} = 2^n \end{aligned}

So c_n < 2^n for every n \ge 1. \square

Check. c_4 = 7 < 16 and c_5 = 13 < 32. With only two base cases, the step at n = 3 would need c_0, which does not exist, and nothing would reach c_3.

Example 3

Sums of distinct powers of 2

Prove that every positive integer is a sum of distinct powers of 2 (one power alone counts). Then follow the proof to write 45 this way.

Solution

Halving n lands far below n - 1, so the hypothesis must cover every smaller value.

Proof. Let P(n) say “n is a sum of distinct powers of 2”. Base case. 1 = 2^0. Step. Let n \ge 2 and assume P(m) for 1 \le m < n.

If n is even, n = 2m with 1 \le m < n, and m = 2^{e_1} + \cdots + 2^{e_r} with distinct exponents. Then n = 2^{e_1 + 1} + \cdots + 2^{e_r + 1}, still with distinct exponents.

If n is odd, n = 2m + 1, and n \ge 3 gives 1 \le m < n. Doubling the sum for m writes 2m with distinct powers, each at least 2^1, and adding 2^0 = 1, not among them, writes n.

By strong induction P(n) holds for every n \ge 1. \square

For 45: 45 = 2 \cdot 22 + 1, 22 = 2 \cdot 11, 11 = 2 \cdot 5 + 1, 5 = 2 \cdot 2 + 1 and 2 = 2 \cdot 1. Building back up from 1:

n	from	sum
2	double 1	2
5	double 2, add 1	4 + 1
11	double 5, add 1	8 + 2 + 1
22	double 11	16 + 4 + 2
45	double 22, add 1	32 + 8 + 4 + 1

So 45 = 32 + 8 + 4 + 1, which is 101101 in base two. The odd branch needs m \ge 1, which fails at n = 1; that is why 1 is the base case.

Example 4

Assembling a jigsaw puzzle

A jigsaw puzzle has n pieces. At every moment the pieces lie in sections: a loose piece is a section, and so is any group already fitted together. A join fits two sections into one. Prove that assembling the whole puzzle takes exactly n - 1 joins, in whatever order they are made.

Solution

Count from the end: the last join fits together two sections of any sizes adding to n.

Proof. Let P(n) say “every complete assembly of an n-piece puzzle uses exactly n - 1 joins”. Base case. A 1-piece puzzle needs 0 joins. Step. Let n \ge 2 and assume P(m) for 1 \le m < n. In any complete assembly the last join fits sections A and B together, with a and b pieces, a + b = n and a, b \ge 1, so a, b < n.

Joins only merge sections, so every section formed along the way lies wholly inside A or wholly inside B: one holding pieces of both would still hold them just before the last join, when the only sections are A and B. So the earlier joins split into those assembling A, which number a - 1 by P(a), and those assembling B, which number b - 1. In all

(a - 1) + (b - 1) + 1 = a + b - 1 = n - 1

By strong induction P(n) holds for every n \ge 1. \square

Check. Each join turns two sections into one, so the number of sections falls by 1 per join, from n to 1: that is n - 1 joins.

Example 5

The smallest solution

Prove that there are no positive integers x and y with x^3 = 2y^3.

Solution

A solution is a pair, so measure it by x: if solutions exist, the x values in them form a nonempty set of positive integers.

Proof. Suppose, for contradiction, that solutions exist. By the well-ordering principle there is a least x occurring in a solution; fix such a solution (x, y). Since x^3 = 2y^3 is even, x is even, because an odd x = 2j + 1 has x^3 = 2(4j^3 + 6j^2 + 3j) + 1. Write x = 2u. Then 8u^3 = 2y^3, so y^3 = 4u^3 is even, and y = 2v in the same way. Then 8v^3 = 4u^3, that is u^3 = 2v^3. So (u, v) is a positive solution with \displaystyle u = \frac{x}{2} < x, contradicting the choice of x. \square

The proof built a smaller solution from the smallest one, an argument by descent. It also shows that \displaystyle \sqrt[3]{2} is irrational, since \displaystyle \sqrt[3]{2} = \frac{x}{y} would give x^3 = 2y^3.

Example 6

A take-away game

Tiponi and Marlee share a pile of n counters. They take turns, and a turn removes 1, 3 or 4 counters. Whoever takes the last counter wins, so a player facing an empty pile has lost. A pile is a losing position if the player about to move loses against best play, and a winning position otherwise. Prove that n is losing exactly when it leaves remainder 0 or 2 on division by 7.

Solution

From n the moves reach n - 1, n - 3 and n - 4, so the step needs a strong hypothesis. A position is winning if some move reaches a losing position, and losing if every move reaches a winning one, or there is no move.

Figure 2Pile sizes from 0 to 20 in rows of seven. The shaded sizes are the losing positions of Example 6, the ones leaving remainder 0 or 2 on division by 7.

Proof. Let L be the set of n \ge 0 leaving remainder 0 or 2, and let P(n) say “n is losing exactly when n \in L”. Base case. At n = 0 there is no move, the player has lost, and 0 \in L. Step. Let n \ge 1, assume P(m) for 0 \le m < n, and let r be the remainder of n on division by 7.

If n \notin L, then r is 1, 3, 4, 5 or 6. Remove 1 when r = 1, 3 when r is 3 or 5, and 4 when r is 4 or 6. Each move removes at most r \le n counters and leaves remainder 0 or 2, a losing position by the hypothesis. So n is winning.

If n \in L and n \ge 1, then r = 0 with n \ge 7, and the moves leave remainders 6, 4, 3; or r = 2, and they leave 1, 6, 5 (from n = 2 only the first move exists). No move reaches L, so by the hypothesis every move reaches a winning position, and n is losing.

By strong induction P(n) holds for every n \ge 0. \square

So 30 = 4 \cdot 7 + 2 is losing, and from 31 the winning move removes 3 and leaves 28. One base case is enough because the step, written with “each allowed move”, works at every n \ge 1.

Example 7

Where the least member is missing

Find the least member, if any, of (a) the integers n with n^2 < 20, and (b) the positive rationals q with q < 1. Then explain why this argument fails: “Suppose some integer is negative, and let m be the least negative integer. Then m - 1 is negative and smaller, a contradiction. So no integer is negative.”

Solution

(a) For an integer, n^2 < 20 means -4 \le n \le 4, so the least member is -4. The set holds negatives, but it is bounded below, and that is all well-ordering needs.

(b) None. If q is in the set, so is \displaystyle \frac{q}{2}, which is rational, positive and less than q.

The conclusion is false, since -1 is negative. The error is “let m be the least negative integer”: the negative integers have no lower bound and no least member, so a smallest-counterexample proof over \mathbb{Z} cannot begin.

Boundaries

The hypothesis covers only n_0 to k. A step calling on a value below n_0, or on the value being proved, is invalid. In Example 3 the odd branch fails at n = 1, where it would call on 0.

Every value the step skips is a base case. Example 2 needs three. Exercise 11 shows a false claim slipping through a step that fails at one value.

Strong induction is not a stronger logic. It proves exactly what ordinary induction proves.

Well-ordering needs integers bounded below. It fails for \mathbb{Z}, the positive rationals and the positive reals. Picking “the smallest” needs a nonempty set inside such a range, or objects measured by a positive integer, as the solutions in Example 5 were measured by x.

Where this goes next

Strong induction is the usual tool wherever an object breaks into smaller pieces of unknown size, and for rules that look back several terms (closed forms for recurrences). Example 1 is the existence half of the fundamental theorem of arithmetic. Well-ordering gives the remainder in the division algorithm (Exercise 17), and it is why the Euclidean algorithm stops: its remainders are nonnegative integers that keep shrinking.

Exercises

Day 1: base cases and hypotheses

A strong induction for n \ge 1 has a step that proves P(n) from P(n - 2) and P(n - 4) only. Which values must be base cases, and from which n does the step run?
A sequence has a_1 = 1, a_2 = 2, a_3 = 3 and a_n = a_{n-1} + a_{n-2} - a_{n-3} for n \ge 4. Prove that a_n = n for every n \ge 1.
A sequence has b_1 = 1, b_2 = 5, b_3 = 7 and b_n = 2b_{n-1} + b_{n-2} - 2b_{n-3} for n \ge 4. Prove that b_n = 2^n + (-1)^n for every n \ge 1.
A sequence has s_1 = s_2 = s_3 = 1 and s_n = s_{n-1} + s_{n-3} for n \ge 4. Prove that \displaystyle s_n \le \left(\frac{3}{2}\right)^n for every n \ge 1.

Day 1: building from smaller pieces

Follow the proof in Example 3 to write 100 and 77 as sums of distinct powers of 2.
Prove by strong induction that every positive integer n can be written as n = 2^a m, where a \ge 0 is an integer and m is odd.
Prove that every positive integer is a sum of powers of 3 (1, 3, 9, 27, \dots) in which each power is used at most twice. (Write n = 3m + r with r equal to 0, 1 or 2.)
Marlee splits a pile of n counters into two smaller piles and scores the product of their sizes. She keeps splitting piles of more than one counter until every pile has one. Prove that her total score is \displaystyle \frac{n(n-1)}{2} however she splits.

Day 1: reasoning

Prove that the sum in Example 3 is unique: a positive integer cannot be written as a sum of distinct powers of 2 in two different ways. (Ask whether 2^0 appears.)
Write Example 1 as an ordinary induction on Q(n): “every integer from 2 to n is a product of primes”. Say where the strong step is used.
Find the flaw. Claim: 4n = 0 for every integer n \ge 0. Base case: 4 \cdot 0 = 0. Step: let n \ge 1 and assume 4m = 0 for 0 \le m < n. Write n = i + j with 0 \le i, j < n. Then 4n = 4i + 4j = 0 + 0 = 0.

Day 2: least members

Find the least member of each set, or show that it has none. (a) The positive integers n with n^3 > 500. (b) The integers n with 3n + 7 > 0. (c) The integers n with n^2 < 30. (d) The rational numbers q with q > 2. (e) The positive integers n with 2^n > n^4.
Tiponi and Marlee play the game of Example 6, but a turn removes 1 or 4 counters. Find the losing positions from 0 to 12, and prove that n is losing exactly when it leaves remainder 0 or 2 on division by 5.
Now a turn removes 2 or 3 counters, and a player who cannot move loses. Prove that n is losing exactly when it leaves remainder 0 or 1 on division by 5. How many base cases does the proof use?

Day 2: reasoning

Prove by smallest counterexample that n! \ge 2^{n-1} for every integer n \ge 1.
Prove that there are no positive integers x, y, z with x^2 + y^2 = 3z^2. (A square leaves remainder 0 or 1 on division by 3.)
Let a \ge 0 and b \ge 1 be integers, and let S be the set of integers a - bq \ge 0 with q a nonnegative integer. Explain why S has a least member r, and prove that 0 \le r < b.
Let S be a nonempty set of integers, all at least some integer c. Prove from the well-ordering principle that S has a least member.
Prove the principle of strong induction, for n_0 = 1, from the well-ordering principle.

Answers

P(1) to P(4) are base cases, and the step runs from n = 5, since it needs n - 4 \ge 1. All four are used: n = 5 calls on P(3) and P(1), and n = 6 on P(4) and P(2).
Base cases a_1 = 1, a_2 = 2, a_3 = 3. Step, n \ge 4: a_n = (n - 1) + (n - 2) - (n - 3) = n. Three base cases, since the step reaches back to n - 3.
Base cases 2 - 1 = 1, 4 + 1 = 5, 8 - 1 = 7. Step, n \ge 4: substitute the formula. The powers of 2 give 2^n + 2^{n-2} - 2^{n-2} = 2^n. Since (-1)^{n-1} = (-1)^{n-3} = -(-1)^n and (-1)^{n-2} = (-1)^n, the signs give (-2 + 1 + 2)(-1)^n = (-1)^n.
Base cases \displaystyle 1 \le \frac{3}{2}, \displaystyle 1 \le \frac{9}{4}, \displaystyle 1 \le \frac{27}{8}. Step, n \ge 4: \displaystyle s_n \le \left(\frac{3}{2}\right)^{n-1} + \left(\frac{3}{2}\right)^{n-3}, which is \displaystyle \frac{26}{8}\left(\frac{3}{2}\right)^{n-3}, at most \displaystyle \frac{27}{8}\left(\frac{3}{2}\right)^{n-3} = \left(\frac{3}{2}\right)^n.
100 \to 50 \to 25 \to 12 \to 6 \to 3 \to 1, then back up 3 = 2 + 1, 6 = 4 + 2, 12 = 8 + 4, 25 = 16 + 8 + 1, 50 = 32 + 16 + 2, 100 = 64 + 32 + 4. And 77 \to 38 \to 19 \to 9 \to 4 \to 2 \to 1, then 9 = 8 + 1, 19 = 16 + 2 + 1, 38 = 32 + 4 + 2, 77 = 64 + 8 + 4 + 1.
Base case 1 = 2^0 \cdot 1. Step, n \ge 2: if n is odd, n = 2^0 \cdot n. If n is even, n = 2k with 1 \le k < n, so k = 2^a m with m odd, and n = 2^{a+1} m.
Base cases 1 = 1 and 2 = 1 + 1. Step, n \ge 3: n = 3m + r with 1 \le m < n, so m is such a sum. Multiplying by 3 raises every power by one, so 3m uses only 3, 9, \dots, each at most twice, and adding r ones uses 1 at most twice.
Base case n = 1: score 0. Step, n \ge 2: the first split makes piles of a and b, with a + b = n and 1 \le a, b < n, and every later split is inside one of them. By the hypothesis the total is \displaystyle ab + \frac{a(a-1)}{2} + \frac{b(b-1)}{2}, which equals \displaystyle \frac{(a+b)^2 - (a+b)}{2} = \frac{n(n-1)}{2}.
For n = 1 every power except 2^0 exceeds 1, so 2^0 is the only sum. For n \ge 2, assume uniqueness below n. All powers except 2^0 are even, so 2^0 appears exactly when n is odd, in both sums or neither. Remove it if present and halve the other terms: two sums for \displaystyle m = \left\lfloor \frac{n}{2} \right\rfloor, with 1 \le m < n, which are equal by the hypothesis. So the two sums for n were equal.
Q(2) holds, as 2 is prime. If Q(k) holds for some k \ge 2, that is exactly the hypothesis of Example 1’s step for n = k + 1, which gives P(k+1); and Q(k) with P(k+1) is Q(k+1). Ordinary induction gives Q(n) for all n \ge 2, which includes P(n).
The step fails at n = 1: the only choice is i = j = 0, and 0 + 0 \ne 1. So P(1), which says 4 = 0, is skipped by the step, needed to be a base case, and is false. For n \ge 2 the split n = 1 + (n - 1) works, which hides the gap.
(a) 8, since 7^3 = 343 and 8^3 = 512. (b) -2, since 3n + 7 > 0 means \displaystyle n > -\frac{7}{3}. (c) -5, since the set is -5, \dots, 5. (d) None: if q > 2, then \displaystyle \frac{q + 2}{2} is rational and \displaystyle 2 < \frac{q + 2}{2} < q. (e) 1, since 2^1 = 2 > 1 = 1^4; the next member is 17.
Losing positions 0, 2, 5, 7, 10, 12. Strong induction, base case n = 0. For remainder 1, 3 or 4 on division by 5, remove 1, 1 or 4, leaving remainder 0, 2 or 0. For remainder 0 (so n \ge 5) the moves leave 4 and 1; for remainder 2 they leave 1 and, when n \ge 7, 3. None of these is 0 or 2.
Two base cases, n = 0 and n = 1: no move, so losing. Step, n \ge 2: for remainder 2 remove 2, for 3 remove 3, for 4 remove 3, leaving remainder 0, 0 or 1. For remainder 0 (so n \ge 5) the moves leave 3 and 2; for remainder 1 (so n \ge 6) they leave 4 and 3. None is 0 or 1.
Suppose not, and let m be the least n \ge 1 with n! < 2^{n-1}. Then m \ne 1, as 1! = 2^0. So m \ge 2 and (m - 1)! \ge 2^{m-2}, giving m! = m \cdot (m - 1)! \ge 2 \cdot 2^{m-2}, which is 2^{m-1}, a contradiction.
Take a solution with z least. The remainders of x^2 and y^2, each 0 or 1, add to a multiple of 3 only if both are 0, so 3 \mid x and 3 \mid y. With x = 3u, y = 3v: z^2 = 3(u^2 + v^2), so 3 \mid z, and z = 3w gives u^2 + v^2 = 3w^2 with 0 < w < z, a contradiction.
q = 0 puts a in S, so S is a nonempty set of nonnegative integers, with a least member r = a - bq (Exercise 18). r \ge 0 by definition. If r \ge b, then r - b = a - b(q + 1) \ge 0 lies in S and is smaller than r, a contradiction.
The numbers s - c + 1 with s \in S form a nonempty set of positive integers, with a least member s_0 - c + 1, s_0 \in S. Every s \in S has s - c + 1 \ge s_0 - c + 1, so s \ge s_0.
Suppose P(1) and the strong step hold but some P(n) fails. Let m be the least failure. Then m \ne 1, so m - 1 \ge 1, and P(1), \dots, P(m-1) all hold. The step at k = m - 1 gives P(m), a contradiction.