2023年6月24日发(作者：)

Chapter 2

One Step at a Time. The Method of

Mathematical Induction

2.1 Weak Induction

Let us assume it is almost midnight, and it has not rained all day today. If,

from the fact that it does not rain on a given day, it followed that it will not

rain the following day, it would then also follow that it would never rain

again. Indeed, from the fact that it does not rain today, it would follow

that it will not rain tomorrow, from which it would follow that it will not

rain the day after tomorrow, and so on.

This simple logic leads to another very powerful tool in mathematics:

the method of mathematical induction. We can try to apply this method

any time we need to prove a statement for all natural numbers m. Our

method then has two steps.

(1) The Initial Step. Prove that the statement is true for the smallest

value of m for which it is defined, usually 0 or 1.

(2) The Induction Step. Prove that from the fact that the statement is

true for n ("the induction hypothesis"), it follows that the statement

is also true for n + 1.

If we can complete both of these steps, then we will have proved our

statement for all natural values of m. Indeed, suppose not, that is, that

we have completed the two steps described above, but still there are some

positive integers for which our statement is not true. Let m + 1 be the

smallest such integer. Then m + 1 is not the smallest integer for which our

statement is defined, for that would contradict the fact that we completed

the Initial Step. So our statement is defined, and therefore, true, for m as

m + 1 was the smallest integer for which it was false. So our statement is

true for m, but false for m + l, which contradicts the fact that we completed

19 20

A Walk Through Combinatorics

the Induction Step. Indeed, choosing m = n in the Induction Step yields

this contradiction.

Having seen that the method of mathematical induction is a valid one,

let us survey some of its applications.

Example 2.1. For all positive integers n,

,9

2l + 2 + ---+m = —^

„2

229 m(m + l)(2m+1)

^ ^—L. (2.1)

Without the method of mathematical induction, we could be in trouble

here. The left-hand side is a sum that is not an arithmetic series or a

geometric series, so we could not use the known formulae for those series.

Moreover, the right-hand side look slightly counter-intuitive; for example, it

is not clear how the number 6 will show up in the denominator. The method

of mathematical induction, however, solves this problem effortlessly as we

will see below.

Solution. (1) The Initial Step. If m = 1, then the left-hand side is 1, and

so is the right-hand side, so the statement is true.

(2) The Induction Step. Now assume equation (2.1) is true for n, and prove

it for n + 1. The statement for n + 1 can be obtained from (2.1) by

replacing n by n + 1 and is as follows.

„, , / ,N2 (n + l)(n + 2)(2n + 3) .„ „N (2

2222l + 2 + ---+n + (n + l) = i ^——^ '-. (2.2)

To prove (2.2) from (2.1), note that these two equations look pretty

much alike; in fact, their difference is a rather simple equation. We

are going to prove that this difference is an equation that is in fact

an identity. This is true as the difference of the two left-hand sides is

clearly (n + l)2, while that of the two right-hand sides is

(n + l)[(n + 2)(2n + 3) - n(2n + 1)]

= (n + iy.

6

Therefore, adding the true statements

2 , o2 , , „2 _ n(n + l)(2n + 1)

r + T + • • • + n* =

t>

and

, , ,2 _ (n + l)[(n + 2)(2n + 3) - n(2n + 1)]

(n + L) - g

we get that

,2 „a 2 / ,s2 (n+l)(n + 2)(2n + 3)

222l + 2 + • • • + n + (n + l)2 = -i ^——^ '-.

6

Therefore, the statement holds for all positive integers m. One Step at a Time. The Method of Mathematical Induction 21

The previous example shows the one serious advantage and one serious

disadvantage of the method of mathematical induction. The advantage

is that instead of having to prove a general statement, we only have to

prove two specific statements. That is, first, we have to complete the initial

step, which is usually easy as the substitution m = 0 or m = 1 usually

simplifies the expressions at hand significantly. Then we have to complete

the induction step which only involves proving the statement for n + 1

assuming that it is true for n, which is again usually easier than proving

the statement for n + 1 without the induction hypothesis.

The drawback will become more apparent after the next example.

Example 2.2. Let f(m) be the maximum number of domains into which

m straight lines can divide the plane. Then /(m) = "H™+ ' + 1.

It is clear that one straight line always divides the plane into two do-mains, so /(l) = 2, and the initial step is complete. The reader can easily

verify that the constructions below are optimal for m = 2 and m = 3, and

therefore /(2) = 4, and /(3) = 7. This step is not a necessary part of our

induction proof, but it helps the reader visualize the problem.

Fig. 2.1 Optimal constructions for m = 2 and m = 3.

Now let us assume the statement is true for an integer n, and let us

prove that it is true for n + 1. Let s be one of our n + 1 straight lines; we

may think of s as the straight line we added to our picture last. Then s

intersects at most n other straight lines, since there are only n other lines

in the picture. Denote by • • • ,tk the straight lines that s crosses, in

the order it crosses them, in some order. As we said, k < n since there are 22

A Walk Through Combinatorics

n + 1 lines altogether. This means that s passes through k + 1 different

domains formed by the other n lines, and cuts each of them into two new

domains. Indeed, s cuts through a domain before crossing each £», and

after crossing tk- In other words, s increases the number of domains by

k + 1 < n +1. Therefore, we have just proved that f(n +1) < /(n) + n +1,

and equality occurs if and only if s does intersect all the other n lines. Thus

f(n + 1) = f(n) + n + 1. However, the induction hypothesis claims that

f(n) = =^tli + i. Therefore,

f{n+l) = f(n)+n+l = ^p± + l + n + l=(n + 1

f+ 2> + 1,

completing the proof.

This proof was possible because we were given a formula for /(m) to

prove, just as we were given a formula to prove for the sum of squares in

the previous example. Had we been not given these formulae beforehand,

first we would have had to guess them, then we could have proved them

by the method of mathematical induction. This is the disadvantage of the

inductive method we were referring to. However, this guessing is not always

hard to do, as the following example shows.

Example 2.3. Let ao = 1, and let an+i = 3an + 1, for all positive integers

n > 1. Find an explicit formula for am.

We will learn techniques that enable us to solve problems like this with-out any guessing. For now, however, let us compute the first few values of

the sequence. We get that they are 1,4,13,40,121. It is easy to conjecture

that am = (3m — l)/2. Now we are going to prove our statement by in-duction. For m = l, the statement is trivially true. Now assume that the

statement holds for n. Then

an+1 = 3an + 1 =

n 3 • (3" - 1) , 3n+1 - 1

1- 1 = ——,

so the statement also holds for n + 1, and the proof follows.

Remark. Readers should have a basic understanding of the method of

mathematical induction by now, and probably noticed that at the end of

the induction proofs, we always choose m = n. Therefore, we will no longer

use different variables for m and n.

For our purposes, a finite set is a finite unordered collection of different

objects. That is, {1,3,2} and {2,1,3} are the same as sets, because they

only differ in the order of their elements, and as we said, sets are unordered

structures. If an element is allowed to appear more than one time in a One Step at a Time. The Method of Mathematical Induction 23

collection, such as the element 1 in the collection (1,1,2,3), then that

collection is called a multiset. We say that the set B is a subset of the set

A, denoted B C A, if each element of B is also an element of A. In this

case it is clear that B has at most as many elements as A.

In elementary combinatorial enumeration, the most important property

of a set is the number of its elements. Usually, if a statement of enumerative

combinatorial nature is true for one set of size n, then it is true for all sets

of size n. Therefore, it is permissible, and certainly convenient, to use one

example of n-element sets for most of our discussion: that of the first n

positive integers, that is, the set {1,2,3, ••• , n}. As this set will be our

canonical example, we introduce the notation [n] = {1,2,3, • • • , n) for this

set.

Theorem 2.4. For all positive integers n, the number of all subsets of [n]

is2n.

Proof. For n = 1, the statement is true as [1] has two subsets, the empty

set, and {1}.

Now assume we know the statement for n, and prove it for n + 1. We

divide the subsets of [n + 1] into two classes: there will be those subsets

that do not contain the element n + 1, and there will be those that do.

Those that do not contain n + 1 are also subsets of [n], so by the induction

hypothesis, their number is 2™. Those that contain n +1 consist of n+1 and

a subset of [n], however, that subset of [n] can be any of the 2™ subsets of

[n], so the number of these subsets of [n +1] is once more 2™. So altogether,

[n + 1] has 2™ + 2™ = 2"+1 subsets, and the theorem is proved. •

With all its strength, the method of induction can also be dangerous

if not applied carefully. One common pitfall is to omit a careful proof of

the Initial Step, then "prove" a faulty statement by a correct Induction

Step. For example, we could "prove" the faulty statement that all positive

integers of the form In +1 are divisible by 2, if we could start the induction

somewhere, that is, if we could find just one positive integer n for which

this property holds. The Induction Step would be easy to complete as

2(n + 1) + 1 - (2n + 1) = (2n + 1) + 2 - (2n + 1) = 2 is certainly divisible

by 2, the Initial Step, however, cannot be completed.

The following provides an example of a much more subtle fallacy.

We claim that all horses have the same color. As the number of all

horses in the world is certainly finite, we can restate our claim as follows.

For any positive integer n, any n horses always have the same color. And 24

A Walk Through Combinatorics

here is our "proof" by induction. For n = 1, the statement is obviously

true: any one horse has the same color as itself. Now suppose that the

statement is true for n, and prove it for n + 1. Take n + 1 horses, and line

them up. Then the first n horses must have the same color, say black, by

the induction hypothesis, but the last n horses also must have the same

color, by the same induction hypothesis, so they too must be black as we

already have seen that all the first n horses were black, and that included

the second, third, fourth,- • • , nth horses, which are also included among

the last n horses. Therefore, all n + 1 horses are black.

It is not so easy to catch the faulty step in this argument because this

argument would indeed work for all values of n, except for n = 1. When,

however, we want to apply this argument to prove that the statement holds

for two horses using the fact that it holds for one horse, we encounter

insurmountable difficulties. The reason for this is simple: in this case the

"first n horses" simply means the first horse, while the "last n horses"

means the last horse. These two sets have no intersection, so nothing forces

the color of the horse in the first set to be the same as that of the horse in

the second one!

This fallacy shows that we must be careful that our Induction Step is

correct for all values of n greater than or equal to the value used in the

Initial Step.

Of course, our argument shows that if any two horses did have the same

color, then all horses would have the same color, but that result would be

a horse of a different color.

2.2 Strong Induction

Example 2.5. Let the sequence {an} be defined by the relations ao = 0,

and an+ — a0 + ai + a2 + • • • + an + n + 1 if n > 1. Prove that for all

positive integers n, the equality a„ = 2" - 1 holds.

Here we certainly could not hope to prove our statement by our usual

way of induction. Indeed, an+i depends not only on an, but also on

an-i,an-2, ••• ,ai, so simply using the fact that an_i = 2n_1 — 1 cannot

be sufficient.

Solution, (of Example 2.5) As a0 = 0, the initial case is true. Now let us

assume that we know that the statement is true for all positive integers less One Step at a Time. The Method of Mathematical Induction 25

than or equal to n. Then, by our recurrence relation,

an+1 = a0 + • • • + an = (2° - 1) + (21 - 1) + • • • + (2n - 1) + n + 1

1 + 2 + 4 +••• + 2" = 2"+1 -1.

This shows that our explicit formula is correct for n + 1, and the proof is

complete.

Note that if we remove a® from our sequence {an}, we get a geometric

series.

Let us review the steps of this strong induction algorithm.

(1) The Initial Step. Prove that the statement is true for the smallest value

of n for which it is defined, usually 0 or 1.

(2) The Induction Step. Prove that from the fact that the statement is true

for all integers less than n + 1 ("the induction hypothesis"), it follows

that the statement is also true for n + 1.

Just as in the case of weak induction, if we can complete both of these

steps, then we will have proved our statement for all natural numbers n.

Indeed, suppose not, that is, that we have completed the two steps described

above, but still there are some positive integers for which our statement

is not true. Let n + 1 be the smallest such integer. Then n + 1 is not

the smallest integer for which our statement is defined, for that would

contradict the fact that we completed the Initial Step. So our statement is

defined, and therefore, true, for all integers less than or equal to n, because

n + 1 was the smallest integer for which it was false. So our statement

is true for all integers less than or equal to n, but false for n + 1, which

contradicts the fact that we completed the Induction Step.

Let us see one more application of the strong induction algorithm. For

the rest of this book, denote N the set of natural numbers, that is, the set

of non-negative integers.

Example 2.6. Let / : N -> N be a function satisfying f(n + m) = f(n) +

/(m) for all m and n. Prove that there exists a constant c so that f(n) = en.

Solution. Let m = 0, then f(n + 0) = f(n) + /(0), so /(0) = 0, and the

initial step is complete. Now let us assume that we know that the statement

is true for all natural numbers less than or equal to n. That is, there exists

a constant c so that f(k) = ck if k < n. In particular, that means /(l) = c

and /(n) = en. This implies that /(n+1) = /(n) + /(l) = cn+c = c(n + l),

and the statement is proved. 26

A Walk Through Combinatorics

Notes

It is sometimes convenient to shift the parameters in an induction proof.

This means that the Induction Step involves assuming the statement for

n — 1, and proving it for n (in the weak case), or assuming the statement

for all integers less than n, and proving it for n. It can also happen that

we want to prove some property of even integers, or odd integers, in which

case we would have to adjust our Induction Step accordingly. There will

be many examples for these phenomena later in this book.

Exercises

(1) + Let p(k) be a polynomial of degree d. Prove that q(n) = ^2^=1p(k)

is a polynomial of degree d + 1. Prove that this polynomial q satisfies

q(0) = 0.

(2) At a tennis tournament, every two players played against each other ex-actly one time. After all games were over, each player listed the names

of those he defeated, and the names of those defeated by someone he

defeated. Prove that at least one player listed the names of everybody

else.

(3) At a tennis tournament, there were 2" participants, and any two of

them played against each other exactly one time. Prove that we can

find n +1 players that can form a line in which everybody has defeated

all the players who are behind him in the line.

(4) Prove that for all positive integers n, it is possible to organize a round

robin tournament of n football teams in

a. n — 1 rounds if n is even,

b. n rounds if n is odd.

A round is a set of games in which each team plays one opponent if

n is even, and there is only one idle team if n is odd. A round-robin

tournament is a tournament in which any pair of teams meet exactly

once.

(5) Let ao = 1, and let an+i = 3a„ + 2, for all non-negative integers n.

Prove that an = 2 • 3n - 1.

(6) Let ao = 1, and let an+1 = 4an — 1, for all non-negative integers n.

Prove that an = 2'4"3+1 •

(7) Let a0 = 1, and let an+i = 2^"=0a» f°r an non-negative integers n.

Find an explicit formula for an. One Step at a Time. The Method of Mathematical Induction 27

(8) There are n patients waiting in a doctor's office. Each of them took a

number, from 1 to n. The patients are told that they will not necessarily

be called in the order their numbers would indicate, but nobody will

be preceded by more patients than he would be if the order of their

numbers were strictly respected. That is, the patient holding number

i will be preceded by at most i - 1 patients.

When Mr. Jones heard this, he said, "This is just the same as respecting

the order of the numbers." Was he right?

(9) Prove that for all natural numbers n, the number a(n) = n3 + lln is

divisible by 6.

(10) Prove that 3n > n4 if n > 8.

(11) Prove that if n is a positive integer, then 8n - 14n + 27 is divisible by

7.

(12) We cut a square into four smaller squares, then we cut some of the

obtained small squares into four smaller squares, and so on. Prove that

at any given point of time during this operation, the number of all

squares we have is of the form 3m + 1.

(13) (Some calculus required.) Recall that n! = 1 • 2 n. Prove that for

all positive integers n, the inequality n! > ^ holds.

(14) Prove that there exists a positive integer TV so that if n > N, then the

inequality

n! <

(2.5)"

holds.

(15) + Give an induction proof for the inequality between the geometric

and the arithmetic mean, that is, prove that if oi, a2, • • • , an are non-negative numbers, then

^/aia2 ---an <

a + a2 H

n

-an

. (2.3)

(16) + Give an induction proof for the inequality between the harmonic

mean and the geometric mean, that is, prove that if 01, a2, • • • ,an are

positive real numbers, then