Massachusetts Institute of Technology Lecture 3 6.042J/18.062J: Mathematics for Computer Science September 14, 2000 Professors Nancy Lynch and Shlomi Dolev

Proof by Induction, continued

Topics for today:

• More (regular) inductive proofs

• Strong induction

• Strong induction proof examples

Reading: Velleman 6.3, 6.4; Rosen 3.2

Last time we introduced the basic structure of a proof by induction, and did some basic examples. Today we’ll continue with more basic examples of inductive proofs. Then we’ll go on to two fancier forms of induction, called strong induction and structural induction.

Last time, I forgot to mention a feature of the tiling example: It not only showed the existence of a tiling—it actually gave a recipe for producing one. Example: To tile a 2^{3} × 2^{3} square leaving the upper right corner empty, divide it into 4, put one tile in the center, and recursively tile the 4 pieces, each with one square missing. [[[Diagram]]]

Inductive proof here yields a recursive tiling algorithm.

1 More Regular Inductive Proofs

The examples in this section involve functions that are defined recursively.

1.1 Fibonacci numbers

The Fibonacci number are interesting numbers that arise, e.g., in biology, where they model some types of growth processes (plants, cells, rabbit populations,...). The Fibonacci numbers are written as F_{i}, i = 0, 1, 2, . . .. They are defined recursively by:

F_{0} = 0
F_{1} = 1
F_{i} = F_{i−1} + F_{i−2} for i ≥ 2.

So the sequence starts out 0, 1, 1, 2, 3, 5, 8, 13, 21, . . ..

The Fibonacci numbers satisfy many cute identities, so they provide lots of fun for mathematicians. For example:

Theorem 1.1 ∀n ≥ 0(Σ_{i=0}^{n}F_{i}^{2} = F_{n}F_{n+1})

Example: n = 4: 0^{2} + 1^{2} + 1^{2} + 2^{2} + 3^{2} = 15 = 3 · 5. Let’s try a proof by induction. The theorem statement suggests trying it with P (n) defined as:

∑_{i=0}^{n} F_{i}^{2} = F_{n}F_{n+1}

Prove: ∀n ≥ 0(Σ_{i=0}^{n}F_{i}^{2} = F_{n}F_{n+1})

1. (Base) Σ_{i=0}^{0}F_{i}^{2} = F_{0}F_{1}

2. (Inductive step) ∀n ≥ 0(Σ_{i=0}^{n}F_{i}^{2} = F_{n}F_{n+1} ⇒ Σ_{i=0}^{n+1}F_{i}^{2} = F_{n+1}F_{n+2})

???

3. QED Induction

Now we stare at the gap between P (n) and P (n + 1). P (n + 1) is given by a summation that’s obtained from that for P (n) by adding one term; this suggests that, once again, we subtract. The difference is just the term F_{n+1}^{2}. Now, we are assuming that the original P (n) summation totals F_{n}F_{n+1} and want to show that the new P (n + 1) summation totals F_{n+1}F_{n+2}. So we would like the difference to be

F_{n+1}F_{n+2} − F_{n}F_{n+1}

So, the actual difference is F_{n+1}^{2} and the difference we want is F_{n+1}F_{n+2} − F_{n}F_{n+1}. Are these the same? We want to check that:

F_{n+1}^{2} = F_{n+1}F_{n+2} − F_{n}F_{n+1}

But this is true, because it is really the Fibonacci definition in disguise: to see this, divide by F_{n+1}. Here’s the complete proof:

Prove: ∀n ≥ 0(Σ_{i=0}^{n}F_{i}^{2} = F_{n}F_{n+1})

1. (Base) Σ_{i=0}^{0}F_{i}^{2} = F_{0}F_{1} Both sides are 0.

2. (Inductive step) ∀n ≥ 0(Σ_{i=0}^{n}F_{i}^{2} = F_{n}F_{n+1} ⇒ Σ_{i=0}^{n+1}F_{i}^{2} = F_{n+1}F_{n+2})

1. Fix n ≥ 0.

2. Assume Σ_{i=0}^{n}F_{i}^{2} = F_{n}F_{n+1}

3. Σ_{i=0}^{n+1}F_{i}^{2} = F_{n+1}F_{n+2} 1. Σ_{i=0}^{n+1}F_{i}^{2} = Σ_{i=0}^{n}F_{i}^{2} + F_{n+1}^{2} Summation has one extra term 2. Σ_{i=0}^{n}F_{i}^{2} + F_{n+1}^{2} = F_{n}F_{n+1} + F_{n+1}^{2} Inductive hypothesis (2.2)

3. F_{n}F_{n+1} + F_{n+1}^{2} = F_{n+1}(F_{n} + F_{n+1}) Algebra

4. F_{n+1}(F_{n} + F_{n+1}) = F_{n+1}F_{n+2} Fibonacci definition

5. QED Combining the equations

4. QED Implication, UG 3. QED Induction

1.2 Double Induction

Here’s a trickier use of induction, used twice, in a nested way, in the same proof. Define a function of two natural number variables recursively as follows: f(0, k) = 1 for all k ≥ 0. f(n, 0) = 1 for all n ≥ 0. For n, k ≥ 0, f(n + 1, k + 1) = f(n, k + 1) + f(n + 1, k).

Why does this define a function? We can see by looking at a table. The first two rules fill in the first row and column, respectively. For each other entry, you obtain the value by adding bottom and left neighbors. It is left to the reader to see that this defines a unique function, that is, fills in all the spaces, in exactly one way.

4 — 1 5 15 35 70 3 — 1 4 10 20 35 2 — 1 3 6 10 15 1 — 1 2 3 4 5 0 — 1 1 1 1 1 ——————————– 0 1 2 3 4

We will see these numbers later in the term (around lecture 16). For now, here is a formula (which we pull out of thin air), giving the exact value of the function on any pair of arguments:

f(n, k) = \frac{(n + k)!}{n!k!}.

Here we are using the factorial function (written “!”):

0! = 1
1! = 1
n! = n(n − 1) … 1

Example: f(3, 4) = \frac{7!}{3!4!} = \frac{7.6.5.4.3.2.1}{3.2.1.4.3.2.1} = 35.

Lemma 1.2 ∀n, k ∈ N[f(n, k) = \frac{(n+k)!}{n!k!}].

We can prove this by induction. But there are two variables, n and k. So, we will do the proof in 2 levels. The main strategy is by induction on n. And for each particular n, we work by induction on k. We are doing induction inside an induction. Let’s break up the statement to make the two levels clearer:

Lemma 1.3 ∀n[∀k[f(n, k) = \frac{(n+k)!}{n!k!}]]

Define Q(n, k) to be the predicate f(n, k) = \frac{(n+k)!}{n!k!}. Q(n, k) says that the value in position (n, k) is correct (satisfies the formula). Define P (n) to be ∀k[Q(n, k)], that is, ∀k[f(n, k) = \frac{(n+k)!}{n!k!}]. P (n) means that all the values in row n are correct.

We use the induction pattern:

Prove: ∀n ≥ 0(P (n))

1. (Base) P (0)

2. (Inductive step) ∀n ≥ 0[P (n) ⇒ P (n + 1)]

3. QED Induction

Expanding this pattern:

Prove: ∀n ≥ 0[P (n)]

1. (Base) P (0)

1. ∀k[f(0, k) = \frac{(0+k)!}{0!k!}] Both sides are 1 (for any k)

2. QED Definition of P (0)

2. (Inductive step) ∀n ≥ 0[P (n) ⇒ P (n + 1)] 1. Fix n ≥ 0.

2. Assume P (n), that is, row n is correct.

3. P (n + 1), that is, row n + 1 is correct. ???

4. QED Implication, UG

3. QED Induction

Now, how to prove 3? It involves saying something about the whole row n+1. We use induction to handle all the elements in this row one at a time. Our goal 3 can be rewritten, using the definition of P in terms of Q. Note that this is all talking just about the particular row n + 1.

3. P (n + 1)
1. ∀k[Q(n + 1, k)]

1. (Base) Q(n + 1, 0)

2. (Inductive step) ∀k ≥ 0[Q(n + 1, k) ⇒ Q(n + 1, k + 1)].

3. QED Induction

2. QED Definition of P (n + 1)

The base case for the inner induction follows by expanding the definition of Q(n + 1, 0):

1. (Base) Q(n + 1, 0)

1. f(n + 1, 0) = \frac{(n+1+0)!}{(n+1)!0!} Both sides are 1

2. QED Definition of Q(n + 1)

The inductive step involves a little algebra:

2. (Inductive step) ∀k ≥ 0[Q(n + 1, k) ⇒ Q(n + 1, k + 1)].
1. Fix k ≥ 0.
2. Assume Q(n + 1, k).
3. Q(n + 1, k + 1)
1. f(n + 1, k + 1) = f(n, k + 1) + f(n + 1, k)

Definition of f(n + 1, k + 1)

2. f(n + 1, k) = \frac{(n+1+k)!}{(n+1)!k!} Inductive hypothesis 2.3.1.2.2, definition of Q(n + 1, k).

3. f(n, k + 1) = \frac{(n+k+1)!}{n!(k+1)!} Inductive hypothesis 2.2,

definition of P (n, k + 1).

4. f(n + 1, k + 1) = \frac{(n+k+1)!}{n!(k+1)!} + \frac{(n+1+k)!}{(n+1)!k!} = \frac{(n+1+k+1)!}{(n+1)!(k+1)!} Combining equations, algebra

5. QED Definition of Q(n + 1, k + 1)

4. QED Induction

The “inner” inductive hypothesis (the one involving Q(n+1, k)) is invoked to get information about the previous element in the same row, n + 1. The “outer” inductive hypothesis (the one involving P (n, ∗)), is invoked to get information about element k + 1 of the previous row. (The proof uses UI in the invocation of the outer inductive hypothesis.)

2 Strong induction

Now we define an apparently-more-powerful variant on the ordinary induction principle. Recall ordinary induction:

Prove: ∀n ≥ 0[P (n)]

1. (Base) P (0)

2. (Inductive step) ∀n ≥ 0[P (n) ⇒ P (n + 1)]

3. QED Induction

Strong induction gives an alternative way to prove the same kind of statement:

Prove: ∀n ≥ 0[P (n)]

1. (Base) P (0)

2. (Inductive step) ∀n ≥ 0[(∀i, 0 ≤ i ≤ n(P (i))) ⇒ P (n + 1)]

3. QED Strong induction

The implication within the inductive step is easier to show than it is for ordinary induction, because now in order to prove P (n + 1), we get to assume all of the hypotheses P (0), P (1), P (2), …, P (n), not just P (n). This is written like a new deduction rule. We can also write it as an axiom:

[P (0) ∧ ∀n ≥ 0[(∀i, 0 ≤ i ≤ n(P (i))) ⇒ P (n + 1)]] ⇒ ∀n[P (n)].

Why does this method work? Well, we want to prove for 0, 1, 2, . . .. We get P (0) for free. Then we know P (0) ⇒ P (1), which tells us P (1) (modus ponens). Then we know P (0) ∧ P (1) ⇒ P (2), which, since we know P (0) ∧ P (1), tells us P (2). Etc.

Of course, we can do the same thing starting from any k, not just 0:

Prove: ∀n ≥ k[P (n)]

1. (Base) P (k)

2. (Inductive step) ∀n ≥ k[(∀i, k ≤ i ≤ n(P (i))) ⇒ P (n + 1)]

3. QED Strong induction

3 Strong Induction Proof Examples

3.1 Block towers

Given an unlimited number of blocks of heights 3 and 7, what height towers can be built?

Try some possible heights: 1: no 2: no 3: yes, 3 4: no 5: no 6: 3+3 7: 7 8: no 9: 3+3+3 10: 3 + 7 11: no 12: 3+3+3+3 13: 7+3+3 14: 7+7 15: 3+3+3+3+3 16: 7+3+3+3

From this point on, can we make all larger height towers? Define P (n) to be “we can build a tower of height n”. We prove this by strong induction:

Prove: ∀n ≥ 12(P (n))

1. (Base) P (12) Use 3+3+3+3

2. (Inductive step) ∀n ≥ 12[(∀i, 12 ≤ i ≤ n(P (i))) ⇒ P (n + 1)]

3. QED Strong induction

Here’s the idea for the inductive step. We can build a tower of height n − 2, by strong inductive hypothesis, then add one 3-block. That is, use P (n − 2) to show P (n + 1). But there’s a catch: this works only if n − 2 ≥ 12, i.e., n ≥ 14. (We can only assume P for arguments ≥ 12.)

For n = 12, 13, need to make special arguments.

So, we really have an argument by cases, within the inductive step:

2. (Inductive step) ∀n ≥ 12[(∀i, 12 ≤ i ≤ n(P (i))) ⇒ P (n + 1)] 1. Fix n ≥ 12.

2. (∀i, 12 ≤ i ≤ n(P (i))) ⇒ P (n + 1)

1. Assume ∀i, 12 ≤ i ≤ n(P (i)
2. P (n + 1))

1. n = 12 ⇒ P (n + 1) Use 7+3+3 2. n = 13 ⇒ P (n + 1) Use 7+7 3. n ≥ 14 ⇒ P (n + 1) ???

4. QED Cases

3. QED Implication 3. QED UG

The first two special cases are easy—we’ve already done them. The last case is the one covered by the idea sketched earlier.

3. n ≥ 14 ⇒ P (n + 1)

1. Assume n ≥ 14.

2. P (n − 2) By inductive hypothesis 2.2.1 and the fact that n − 2 ≥ 12

3. P (n + 1) Add one block to the tower from the previous step.

4. QED Implication

Look at the logical structure. I wrote this as a single base case (for 12) and inductive step, where the inductive step breaks down into two special cases (for 13 and 14) plus the rest. I could also formulate a variant on the proof rule:

Prove: ∀n ≥ 12(P (n))

1. (Base) P (12)

2. (Base) P (13)

3. (Base) P (14)

4. (Inductive step) ∀n ≥ 14[(∀i, 12 ≤ i ≤ n(P (i))) ⇒ P (n + 1)]

3. QED Very specialized strong induction

In examples like these, you must be careful to consider all the needed base (or special) cases. Otherwise, you might “prove” false theorems, e.g., that we can build all towers of size ≥ 3:

Prove: ∀n ≥ 3(P (n))

1. (Base) P (3)

2. (Inductive step) ∀n ≥ 3[(∀i, 3 ≤ i ≤ n(P (i))) ⇒ P (n + 1)]

3. QED Strong induction

If we try to mimic the previous proof for this situation, we find we can’t make the jump to 4 or 5.

3.2 Nim

The game of Nim is defined as follows: Some positive number of sticks are placed on the ground. Two players take turns removing one, two, or three sticks. The player to remove the last stick loses.

Theorem 3.1 The first player loses if the number of sticks, n, is 4k + 1 for some k, and wins (if he plays optimally) otherwise.

We can formalize this by defining a strategy as a rule for how many sticks to remove when there are n left. We then show that if n = 4k + 1, then player 2 has a strategy that will force a win for him, otherwise, player 1 has a strategy that will force a win for him.

Proof. We show that if n = 4k + 1 the first player loses, and if n = 4k, 4k + 2, or 4k + 3, the first player wins. This exhausts all possible cases for n.

Proceed by strong induction, starting from 1. Base case: n = 1. The first player has no choice but to remove 1 stick and lose, which is what the theorem says for this case.

Strong inductive step: Suppose the theorem is true for numbers 1 through n and show that it is true for n + 1. For the inductive step, there are four cases:

• n + 1 = 4k + 1: show that the first player loses. We’ve already handled the base case (1) so we can assume n + 1 ≥ 5. Consider what the first player might do to win: he can choose to remove 1, 2 or 3 sticks. If he removes one stick, the remaining number of sticks is n = 4k. By strong induction, the player who plays at this point should win (if he uses his best strategy). So the player who played first will lose.

Similarly, if the first player removes two sticks, the remaining number is 4(k − 1) + 3. Again, he loses, by the same reasoning. Similarly, by removing 3 sticks, he loses. So, however the first player moves, he loses.

• n + 1 = 4k: show that the first player can win.

Have first player remove 3 sticks: the second player then sees 4(k − 1) + 1 sticks, and loses, by the strong inductive hypothesis.

• n + 1 = 4k + 2: show that the first player can win.

Have first player remove 1 stick: the second player then sees 4k + 1 sticks, and loses as in the previous case.

• n + 1 = 4k + 3: show that the first player can win.

Have first player remove 2 sticks: again, the second player sees 4k + 1 sticks and loses.

3.3 Fibonacci examples

3.3.1 Another false theorem

Here is another false “theorem”. The fallacy is like the blocks example—we don’t have enough base cases.

False Theorem 1 All Fibonacci numbers are even.

We try strong induction, where P (n) is defined to be “F_{n} is even.”

Prove: ∀n ≥ 0[P (n)]

1. (Base) P (0) F_{0} = 0, which is even.

2. (Inductive step) ∀n ≥ 0[(∀i, 0 ≤ i ≤ n(P (i))) ⇒ P (n + 1)] ???

3. QED Strong induction The inductive step is supposed to prove that F_{n+1} is even, using the fact that all smaller Fibonacci numbers are even. The idea is to express F_{n+1} as usual, as F_{n−1}+F_{n}. Then use the strong inductive hypothesis to say that F_{n−1} and F_{n} are both even. The sum is therefore also even. What’s the error? We proved: P (0) P (0) ∧ P (1) ⇒ P (2) P (1) ∧ P (2) ⇒ P (3), etc. But we never proved P (1).

3.3.2 A lower bound

Here’s a correct proof about Fibonacci numbers. It shows a lower bound on their values.

Lemma 3.2 ∀n ≥ 2[F_{n} ≥ (\frac{3}{2})^{n−2}]

Proof. Use strong induction. Let P (n) = F_{n} ≥ (\frac{3}{2})^{n−2}

Prove: ∀n ≥ 2[P (n)]

1. (Base) P (2) F_{2} = 1 = (\frac{3}{2})^{0}

2. (Base) P (3) F_{3} = 2 ≥ (\frac{3}{2})^{1}

3. (Inductive step) ∀n ≥ 3[(∀i, 2 ≤ i ≤ n(P (i))) ⇒ P (n + 1)] 1. Fix n ≥ 3

2. Assume ∀i, 2 ≤ i ≤ n(P (i))

3. P (n + 1) ???

4. QED Implication, UG 4. QED Strong induction

Now in proving the ??? we are only worrying about n ≥ 3 and we may assume the inequality for all i from 2 up to n, inclusive. Because of the way Fibonacci numbers are defined, it turns out that the ones we need are just n and n − 1. Those are in the range for which we can assume the property.

3. P (n + 1)

1. F_{n} ≥ (\frac{3}{2})^{n−2} Inductive hypothesis 3.2

2. F_{n−1} ≥ (\frac{3}{2})^{n−3} Inductive hypothesis 3.2

3. F_{n+1} = F_{n} + F_{n−1} Definition

4. F_{n+1} ≥ (\frac{3}{2})^{n−2} + (\frac{3}{2})^{n−3} Plug the inequalities into the equation 5. QED Algebra

1. \frac{3}{2} + 1 ≥ (\frac{3}{2})^{2} Arithmetic

2. (\frac{3}{2})^{n−2} + (\frac{3}{2})^{n−3} ≥ (\frac{3}{2})^{n−1} Algebra

3. F_{n+1} ≥ (\frac{3}{2})^{n−1} Algebra (3.3.4 and 3.3.5.2)

4. QED Definition of P (n + 1)

3.4 Prime Factorization

Recall that a prime is a number not evenly divisible by any number but itself and one. 2, 3, 5, 7, 11, … are primes. 4, 6, 8, 9, 10, 12, … are not. They are composites. Notice, however, that each composite can be broken down (factored) into primes. E.g., 12 = 2×2×3. This is not a coincidence.

Theorem 3.3 Every natural number ≥ 2 can be written as the product of one or more primes.

Proof. We use strong induction, starting from 2, where P (n) is the predicate “n can be written as the product of one or more primes”.

Prove: ∀n ≥ 2[P (n)]

1. P (2) Use 2 itself

2. ∀n ≥ 2[(∀i, 2 ≤ i ≤ n)(P (i)) ⇒ P (n + 1)] 1. Fix n ≥ 2

2. Assume ∀i, 2 ≤ i ≤ n[P (i)], that is, all numbers up to and including n can be factored into primes

3. P (n + 1), that is, n + 1 can be factored into primes.

???

4. QED Implication, UG

3. QED Strong induction

The argument about factoring n + 1 breaks down into cases, depending on whether or not n + 1 itself is prime:

3. P (n + 1), that is, n + 1 can be factored into primes.

1. If n + 1 is prime, then n + 1 can be factored into primes. Use n + 1 itself

2. If n + 1 is not prime, then n + 1 can be factored into primes. 1. Assume n + 1 is not prime.

2. n + 1 can be written as a × b, where 1 < a, b < n + 1 Definition of “prime”

3. a can be factored into primes. Strong inductive hypothesis (2.2)

4. b can be factored into primes. Strong inductive hypothesis (2.2)

5. n + 1 can be factored into primes. Use all the factors from a and b.

6. QED Implication

3. QED Cases

We can do step 5 a little more carefully. If a is written as a product 2^{a_{2}}3^{a_{3}}5^{a_{5}} ⋯ and b is written as a product 2^{b_{2}}3^{b_{3}}5^{b_{5}} ⋯ then n + 1 = ab is written as 2^{a_{2}+b_{2}}3^{a_{3}+b_{3}}5^{a_{5}+b_{5}} · · ·. We just add the number of occurrences of each separate prime factor.

Example 3.4 A factorization of 144 can be obtained by noticing that 144 = 8 × 18 (among other possibilities). 8 can be written as 2^{3}, and 18 as 2 × 3^{2}. So, write 144 as 2^{3+1}3^{2}, or 2^{4}3^{2}.

3.5 Tournaments

A pure math example, interesting and slightly complicated (ordinary and strong) inductive proofs.

A new Internet game company is conducting a chess tournament on the Internet. Round robin, not elimination. That is, everyone plays everyone exactly once. Can represent the results nicely by arrows, e.g.:

A beats B, C, D B beats D C beats B D beats C

Structure called a “digraph”. Will study them carefully soon.

Now, the gaming company wants to use this information to make some decisions, e.g., award first prize, rank everyone. It wants to do this in such a way that its customers don’t complain about the rankings being unfair.

There are some problems with doing this.

3.5.1 Cycles

Problem: The tournament graph can contain cycles. Example: Above, B beats D beats C beats B.

If there’s a cycle, then any ranking method is a least a little problematic: someone who beat someone else would be ranked lower.

Of course, the company has no power to avoid cycles in play results. The gaming company might hope that “most of the time”, when there is a cycle, it’s very big (so the people involved aren’t likely to discover this). However, tournaments have an unfortunate property:

Theorem 3.5 Any tournament that contains any cycle, contains a cycle of length 3 (3-cycle).

That is, three players, e.g., B, C, D, above, have an “inconsistent” set of results.

This can be proved by ordinary induction, where P (n) is the predicate “Any tournament that contains an n-cycle contains a 3-cycle.”

Prove: ∀n ≥ 3[P (n)]

1. (Base) P (3) Trivial by assumption.

2. (Inductive step) ∀n ≥ 3[P (n) ⇒ P (n + 1)] 1. Fix n ≥ 3

2. Assume P (n)
3. P (n + 1)

1. Fix T, a tournament, and p_{1} → p_{2} → … → p_{n+1} → p_{1}, an n + 1-cycle in T.

2. T contains a 3-cycle. ???

3. QED Implication, UG

4. QED Implication, UG 3. QED

How can we find a 3-cycle in T? Example: [[[Draw 5-cycle]]]. To get a 3-cycle, notice that p_{1} and p_{3} have an arrow, one way or the other. If from p_{3} to p_{1}, then p_{1}, p_{2}, p_{3} form a cycle. If the other way, then can reduce the size of the cycle to omit p_{2}. Then use induction on the smaller cycle. This generalizes:

2. T contains a 3-cycle.

1. If p_{3} → p_{1} then T contains a 3-cycle. Use p_{1} → p_{2} → p_{3} → p_{1}.

2. If p_{1} → p_{3} then T contains a 3-cycle.

1. Assume p_{1} → p_{3}.

2. T contains an n-cycle. Use p_{1} → p_{3} → p_{4} → p_{n+1} → p_{1}.

3. T contains a 3-cycle. By inductive hypothesis (2.2)

3. QED Cases

A detail to be careful about here: This argument depends on the fact that the arrow we add between p_{1} and p_{3} is not already part of the original cycle. That’s true because we know that the original cycle had length n + 1, which is at least 4.

[[[In Fall, 00, lecture got to this point. The following subsection should be covered in tutorial tomorrow. The last subsection, on nice rankings and number of wins, is purely optional.]]]

3.5.2 “Nice” rankings

The gaming company decides that, although they cannot avoid inconsistent orders, they would at least like to make the ranking “nice”, by which they mean that if one player p is ranked immediately ahead of another player q, then p must have beaten q. (They might want to tell each player who the players were that are ranked immediately above and below him, and don’t want someone to complain that the guy ranked above him is someone he beat.) They are happy to discover:

Theorem 3.6 Any tournament has a nice ranking.

Example: Above: Can use ranking A, D, C, B.

Prove by strong induction, where P (n) says “any n-player tournament has a nice ranking”. The strategy is to “split” the players into those that beat and those that lose to a particular player x. Rank those two subsets separately, by using the inductive hypothesis. (Subtournaments) Then put the rankings together.

Prove: ∀n ≥ 1[P (n)]

1. (Base) P (1) Obvious—just one player to be ranked.

2. (Inductive step) ∀n ≥ 1[(∀i, 1 ≤ i ≤ n(P (i))) ⇒ P (n + 1)] 1. Fix n ≥ 1

2. Assume ∀i, 1 ≤ i ≤ n[P (i)].

3. P (n + 1)

1. Fix any n + 1-player tournament T.

2. T has a nice ranking.

1. Choose x to be any player, B the set of players that beat x, and L the set of players that lose to x.

2. B has a nice ranking. Inductive assumption (2.2).

3. L has a nice ranking. Inductive assumption (2.2).

4. Define a ranking R of all the players by: B ranking, then x, then L ranking.

5. R is a nice ranking for T.

6. QED EG

3. QED UG 4. QED Implication, UG

3. QED Strong induction

3.5.3 Nice rankings and number of wins

For a while, the customers are happy with just nice rankings. But then a game comes up where just “niceness” doesn’t work out so well:

Example: A beats B B beats C C beats A,D D beats A,B,E E beats A,B,C

[[[Diagram]]]

Here, A,B,C,D,E is a nice ranking. However, it’s in the reverse order according to number of wins. Bad. Now it occurs to the company that it would be nice if the rankings could also be consistent with number of wins. It turns out this is not possible (in combination with “niceness”). So then they decide they will be happy to settle for a nice ranking in which the highest ranked player has the largest number of wins (can be tied). This would rule out the bad example above.

Turns out this is possible:

In fact, in the event of a tie, the company has the option of choosing which best player is ranked first:

Define P (n): For any n-player tournament T and any z that has the largest number of wins in T, there exists a nice ranking with z ranked first.

Prove: ∀n ≥ 1[P (n)]

This can be proved by induction, but the inductive step is more complicated than in the previous proof.

First proof attempt: Try a proof like the previous one, this time splitting on some x that loses to z. Now split all-but-x into B and L as before, based on their records with respect to x. We know that z is in B, because it beats x. Now try to use the inductive hypothesis to rank B while keeping z first, and to rank L. Then combine as before.

Sounds plausible—but wrong: Applying the inductive hypothesis requires that z have the best won-lost record in the “subtournament” involving just the B elements. But it might not:

Example: Players z, y, x, and a lot of p’s z and y beat x x beats all of the p’s y beats z z beats all the p’s All the p’s beat B Doesn’t matter what happens among the p’s.

[[[diagram]]]

z has the best record overall, but in the two-player subtournament consisting of guys that beat x, z is worse than y.

Try again: It turns out that a correct proof can be given using ordinary (not strong) induction: Recall P (n): For any n-player tournament T and any z that has the largest number of wins in T, there exists a nice ranking with z ranked first.

Prove: ∀n ≥ 1(P (n))

1. (Base) P (1) Only one possibility.

2. (Inductive step) ∀n ≥ 1[P (n) ⇒ P (n + 1)] 1. Fix n ≥ 1.

2. Assume P (n).

3. P (n + 1).

1. Fix T, an n + 1-player tournament, and z, a player with the most wins.

2. ∃ a nice ranking of T with z first. ???

3. QED UG 4. QED Implication, UG

3. QED Induction

The key step will break down into cases, based on whether or not z lost any matches. The case where z won everything is easy; the other case is tricky: Here’s the easy case:

2. ∃ a nice ranking of T with z first.

1. If z is undefeated in T then ∃ a nice ranking of T with z first. 1. Assume z is undefeated in T.

2. Choose R to be a nice ranking of all-but-z.

Previous theorem says this exists, EI

3. z then R is a nice ranking of T.

4. ∃ a nice ranking of T with z first.

EG

5. QED Implication

2. If z is defeated by someone then ∃ a nice ranking of T with z first. ???

3. QED Cases

And the tricky case:

2. If z is defeated by someone then ∃ a nice ranking of T with z first. 1. Assume z is defeated by someone.

2. Choose x to be someone who defeated z.

3. z has the best record in the subtournament involving all-but-x.

z had the best record in T,

no wins are removed.

4. ∃ ranking of subtournament having z first.

Inductive hypothesis, z has best record.

5. Choose R to be a ranking of all-but-x having z first.

EI

6. In T, x is defeated by someone. z was defeated, and x’s record in T can’t be better than z’s.

7. Define ranking S to be R, with x inserted right after the lowest-ranked player that beats x.

8. S is a nice ranking of T.

R is nice, x is beaten by the player ranked just above it and beats all ranked below it.

9. z is first in S. z is first in R, and x is not inserted at the top.

10. ∃ a nice ranking of T with z first.

S works, EG

QED Implication