Induction

Induction is used to prove a sequence of statements $P_1$ , $P_2$ , $P_3$ , .... There may be finitely many statements, but often there are infinitely many.

For example, consider the statement

$$1 + 2 + 3 + \cdots + n = \dfrac{n(n + 1)}{2} \quad\hbox{for}\quad n \ge 1.$$

This is actually an infinite set of statements, one for each integer $n \ge 1$ :

$$\eqalign{ 1 & = \dfrac{1(1 + 1)}{2} \cr \noalign{\vskip2pt} 1 + 2 & = \dfrac{2(2 + 1)}{2} \cr \noalign{\vskip2pt} 1 + 2 + 3 & = \dfrac{3(3 + 1)}{2} \cr \noalign{\vskip2pt} 1 + 2 + 3 + 4 & = \dfrac{4(4 + 1)}{2} \cr \noalign{\vskip2pt} & \vdots \cr}$$

You might think of proving this result by induction --- and in fact, I'll do so below.

On the other hand, this statement is also an infinite set of statements:

$$x^2 + 1 \ge 2 x \quad\hbox{for all}\quad x \in \real.$$

However, there is one for each real number. You are unlikely to prove this by induction.

The fact that a statement involves integers does not mean induction is appropriate. For example, consider the statement

"The sum of two even numbers is even."

It's true that this is a statement about an infinite set of pairs of integers.

$$\eqalign{ 2 + 2 & \quad\hbox{is even} \cr 6 + (-14) & \quad\hbox{is even} \cr 112 + 64 & \quad\hbox{is even} \cr &\vdots \cr}$$

However, the problem with using induction here is that there isn't an obvious way to arrange the statements in a sequence.

Likewise, consider the statement

"If n is an integer, then $4 n + 1$ is odd."

While it's conceivable that you could give an induction proof, it would be overkill: $4 n + 1 = 2(2 n) + 1$ expresses $4 n + 1$ as 2 times something plus 1, so it must be odd.

How does induction work? Suppose you have a sequence of statements $P(1)$ , $P(2)$ , ..., $P(n)$ , ..., one for each positive integer. (There's no harm in starting your numbering with 0 if it's convenient.) In the simplest case, to give a proof by induction:

1. Prove $P_1$ .

2. Let $n > 1$ , and assume $P_{n - 1}$ is true.

3. Using the assumption that $P_{n - 1}$ is true, prove that $P_n$ must be true.

If you can complete these steps, you can conclude that $P_n$ is true for all $n \ge 1$ , by induction.

The assumption that $P_{n - 1}$ is true is often called the induction hypothesis, or the inductive assumption.

Why does it work? Induction follows from a fundamental fact about the positive integers called the Well-Ordering Axiom.

Well-Ordering Axiom. Every nonempty subset of the positive integers has a smallest element.

The Well-Ordering Axiom is an axiom for the positive integers, so there's no question of proving it.

Example. Verify the Well-Ordering Axiom for the following subsets of positive integers:

(a) The positive even integers: $\{2, 4, 6, \ldots\}$ .

(b) The subset of the positive integers which consists of positive integers whose decimal representations begin and end with "1". For example, 101, 128391, and 1651 are elements of this set.

(a) The smallest element of this set is 2.

(b) The smallest element of this set is 1.

Theorem. (Principle of Mathematical Induction) Let $P_1$ , $P_2$ , ... be a set of statements indexed by the positive integers. Suppose that:

(a) $P_1$ is true.

(b) For every $n > 1$ , if $P_{n - 1}$ is true, then $P_n$ is true.

Then $P_n$ is true for all $n \ge 1$ .

The intuitive idea is illustrated below:

$$\hbox{\epsfysize=1.5in \epsffile{induction-1.eps}}$$

Assumption (a) says that $P_1$ is true. Assumption (b) says that if a statement is true, the next statement below it is true. I've represented this with a "C-shaped" arrow connector from the known true statement to the next one. As you move the connector down, you find that $P_1$ being true makes $P_2$ true, $P_2$ being true makes $P_3$ true, and so on. Thus, all the statements are true.

Proof. I'll prove the result by contradiction.

Assume that $P_1$ is true, and for every $n > 1$ , if $P_{n - 1}$ is true, then $P_n$ is true. Suppose that it isn't true that $P_n$ is true for all $n \ge 1$ .

Consider the set of integers $n \ge 1$ such that $P_n$ is false. Since $P_n$ is not true for all $n \ge 1$ , there must be some n for which $P_n$ is false. Hence, the set of integers $n \ge 1$ such that $P_n$ is false is nonempty.

Since this is a nonempty subset of the positive integers, by Well-Ordering it contains a smallest element MIN. Thus, $P_{\hbox{MIN}}$ is false, and $P_n$ is not false (i.e. $P_n$ is true) for all $n < \hbox{MIN}$ .

Now MIN can't be 1, because $P_1$ is true by assumption. Thus, $\hbox{MIN} > 1$ . So $\hbox{MIN} - 1$ is a positive integer, and $P_{\hbox{MIN} - 1}$ must be true.

But now my second assumption --- if a statement in the sequence is true, the following statement is true --- shows that $P_{\hbox{MIN} - 1 + 1} = P_{\hbox{MIN}}$ must be true. This contradicts the fact that $P_{\hbox{MIN}}$ is false.

This contradiction proves that $P_n$ is true for all $n \ge 1$ .

Remark. You can also do the induction step by assuming the result for n, and proving it for $n + 1$ , and I will often do this. Usually, there is no difference in the difficulty, so you should use whichever approach you find comfortable.

Also, some inductions begin with a statement numbered "0" --- or "42". The numbering doesn't matter.

Example. Prove that

$$1 + 2 + 3 + \cdots + n = \dfrac{n(n + 1)}{2} \quad\hbox{for}\quad n \ge 1.$$

The formula is true for $n = 1$ , since the left side is 1 and the right side is

$$\dfrac{1 \cdot 2}{2} = 1.$$

Suppose the formula holds for n. This means that

$$1 + 2 + 3 + \cdots + n = \dfrac{n(n + 1)}{2}.$$

I want to prove that the formula holds for $n + 1$ .

Suggestion: You might want to write the formula for $n + 1$ out on scratch paper so you know what you're trying to prove. You get it by replacing "n" with "$n + 1$ " in the formula for n:

$$1 + 2 + 3 + \cdots + n + (n + 1) = \dfrac{(n + 1)[(n + 1) + 1]}{2} = \dfrac{(n + 1)(n + 2)}{2}.$$

Don't start with this equation! --- that would be assuming what you want to prove. Instead, start with the left side and work until you get the right side.

$$\matrix{ 1 + 2 + 3 + \cdots + n + (n + 1) & = & \dfrac{n (n + 1)}{2} + (n + 1) \hfill & \hbox{Induction hypothesis} \cr \noalign{\vskip2pt} & = & (n + 1) \left(\dfrac{n}{2} + 1\right) \hfill & \hbox{Algebra} \cr \noalign{\vskip2pt} & = & (n + 1) \dfrac{n + 2}{2} \hfill & \hbox{Common denominator} \cr \noalign{\vskip2pt} & = & \dfrac{(n + 1)(n + 2)}{2} \hfill & \hbox{Algebra} \cr}$$

This proves the formula for $n + 1$ . Hence, the result is true for all $n \ge 1$ , by induction.

Notice that when I wrote out the left side of the formula for $n + 1$ I put in both the final term "$n + 1$ " and the term before it, which is "n". In that way, I could see the expression "$1 + 2 + 3 + \cdots + n$ " which is the left side of my induction assumption --- so I knew to begin by substituting. This trick is often useful in the induction step.

Example. Prove that for $n \ge 1$

$$14 + 25 + \cdots + (11 n + 3) = \dfrac{n (11 n + 17)}{2}.$$

The formula is true for $n = 1$ , since the left side is 14 and the right side is

$$\dfrac{1 \cdot (11 + 17)}{2} = 14.$$

Suppose the formula holds for n. This means that

$$14 + 25 + \cdots + (11 n + 3) = \dfrac{n (11 n + 17)}{2}.$$

I need to prove the formula for $n + 1$ .

On scratch paper, I write out the formula for $n + 1$ ; it is

$$14 + 25 + \cdots + (11 n + 3) + (11 n + 14) = \dfrac{(n + 1) (11 (n + 1) + 17)}{2} = \dfrac{(n + 1)(11 n + 28)}{2}.$$

Remember not to start with this equation --- start with the left side! Notice that on the left side I wrote out the final term ($11(n + 1) + 3 = 11 n + 14$ ), then wrote out the previous term ($11 n + 3$ ). This helps me recognize the left side of the induction assumption.)

Continuing with our proof, here's the proof of the formula for $n + 1$ . I won't write out justifications for steps this time, as most of it is basic algebra.

$$\eqalign{ 14 + 25 + \cdots + (11 n + 3) + (11 n + 14) & = \dfrac{n (11 n + 17)}{2} + (11 n + 14) \cr \noalign{\vskip2pt} & = \dfrac{n (11 n + 17)}{2} + \dfrac{2(11 n + 14)}{2} \cr \noalign{\vskip2pt} & = \dfrac{n (11 n + 17) + 2 (11 n + 14)}{2} \cr \noalign{\vskip2pt} & = \dfrac{(11 n^2 + 17 n) + (22 n + 28)}{2} \cr \noalign{\vskip2pt} & = \dfrac{11 n^2 + 39 n + 28}{2} \cr \noalign{\vskip2pt} & = \dfrac{(n + 1)(11 n + 28)}{2} \cr}$$

This proves the result for $n + 1$ , so the result is true for all $n \ge 1$ by induction.

Are you wondering how I made the final step?

$$\dfrac{11 n^2 + 39 n + 28}{2} = \dfrac{(n + 1)(11 n + 28)}{2}.$$

The idea is that I knew from my scratch work that the final answer had to be $\dfrac{(n + 1)(11 n + 28)}{2}$ . So I wrote it down, then checked that it worked by multiplying out $(n + 1)(11 n + 28)$ to see if I got $11 n^2 + 39 n + 28$ . Nobody "knows" how you got the final step --- the question is whether it's true!

Example. Let $x \in \real$ , $x \ne 1$ . Prove that

$$1 + x + x^2 + \cdots + x^n = \dfrac{1 - x^{n+1}}{1 - x} \quad\hbox{for}\quad n \ge 0.$$

You're allowed to "begin" an induction with $n = 0$ --- or any other integer --- if it's convenient to do so.

For $n = 0$ ,

$$1 + x + x^2 + \cdots + x^n = 1, \quad\hbox{while}\quad \dfrac{1 - x^{n+1}}{1 - x} = \dfrac{1 - x}{1 - x} = 1.$$

The result is true for $n = 0$ .

(For variety, I'll do this induction step by assuming the result for $n - 1$ and proving it for n. The amount of work is about the same as assuming it for n and proving it for $n + 1$ .)

Assume that $n > 0$ , and that the result holds for $n - 1$ :

$$1 + x + x^2 + \cdots + x^{n-1} = \dfrac{1 - x^n}{1 - x}.$$

I want to show that the result holds for n.

$$\matrix{ 1 + x + x^2 + \cdots + x^{n-1} + x^n & = & \dfrac{1 - x^n}{1 - x} + x^n \hfill & \hbox{Induction hypothesis} \cr & = & \dfrac{1 - x^n}{1 - x} + \dfrac{x^n - x^{n+1}}{1 - x} \hfill & \hbox{Algebra} \cr & = & \dfrac{1 - x^n + x^n + x^{n+1}}{1 - x} \hfill & \hbox{Algebra} \cr & = & \dfrac{1 - x^{n+1}}{1 - x} \hfill & \hbox{Algebra} \cr}$$

This proves the result for n, so the result is true for all $n \ge 0$ , by induction.

Example. Let $n \in \integer$ , $n \ge 1$ . Prove that

$$\dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \cdots + \dfrac{1}{n(n + 1)} = 1 - \dfrac{1}{n + 1}.$$

You may have seen this idea when you learned about infinite series; it's called telescoping:

$$\dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \cdots + \dfrac{1}{n(n + 1)} = \left(\dfrac{1}{1} - \dfrac{1}{2}\right) + \left(\dfrac{1}{2} - \dfrac{1}{3}\right) + \cdots + \left(\dfrac{1}{n} - \dfrac{1}{n + 1}\right).$$

The "argument" is that the terms cancel in pairs, leaving $1 - \dfrac{1}{n + 1}$ .

Arguments where you say "and so on" are often justified rigorously by induction. That's what I'll do here.

For $n = 1$ ,

$$\dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \cdots + \dfrac{1}{n(n + 1)} = \dfrac{1}{1\cdot 2} = \dfrac{1}{2}, \quad\hbox{while}\quad \dfrac{1}{n(n + 1)} = \dfrac{1}{2}.$$

The result is true for $n = 1$ .

Assume that the result is true for n:

$$\dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \cdots + \dfrac{1}{n (n + 1)} = 1 - \dfrac{1}{n + 1}.$$

I want to show that the result holds for $n + 1$ .

$$\eqalign{ \dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \cdots + \dfrac{1}{n(n + 1)} + \dfrac{1}{(n + 1)(n + 2)} & = 1 - \dfrac{1}{n + 1} + \dfrac{1}{(n + 1)(n + 2)} \cr \noalign{\vskip2pt} & = 1 - \dfrac{1}{n + 1} \left(1 - \dfrac{1}{n + 2}\right) \cr \noalign{\vskip2pt} & = 1 - \dfrac{1}{n + 1} \dfrac{(n + 2) - 1}{n + 2} \hfill \cr \noalign{\vskip2pt} & = 1 - \dfrac{1}{n + 1} \dfrac{n + 1}{n + 2} \hfill \cr \noalign{\vskip2pt} & = 1 - \dfrac{1}{n + 2} \hfill \cr}$$

This proves the result for $n + 1$ , so the result is true for all $n \ge 1$ , by induction.

In some situations, it's convenient to give an induction proof in the following form:

1. Prove $P_1$ .

2. Let $n > 1$ , and assume $P_k$ is true for all $k < n$ .

3. Using the assumption that $P_k$ is true for all $k < n$ , prove that $P_n$ must be true.

In other words, you can take as your induction hypothesis the truth of all the statements prior to the $n^{\rm th}$ statement, which you are trying to prove. This is sometimes called generalized induction or strong induction.

Example. Define a sequence of integers by

$$x_0 = 9, \quad x_1 = 18, \quad\hbox{and}\quad x_n = 5 x_{n-1} + 14 x_{n-2} \quad\hbox{for}\quad n \ge 2.$$

Prove that

$$x_n = 4 \cdot 7^n + 5 \cdot (-2)^n \quad\hbox{for}\quad n \ge 0.$$

To get the induction started, I have to verify the formula $x_n = 4 \cdot 7^n + 5 \cdot (-2)^n$ for both $n = 0$ and $n = 1$ . The reason is that the recursion formula doesn't kick in till $n = 2$ .

For $n = 0$ , the formula gives

$$4 \cdot 7^0 + 5 \cdot (-2)^0 = 9 = x_0.$$

For $n = 1$ , the formula gives

$$4 \cdot 7^1 + 5 \cdot (-2)^1 = 18 = x_1.$$

The formula holds for $n = 0$ and $n = 1$ .

Now assume that $n \ge 2$ and the formula holds for all $k < n$ , i.e. for all numbers less than n. In particular, since $n - 1$ and $n - 2$ are less than n, I have

$$x_{n - 1} = 4 \cdot 7^{n - 1} + 5 \cdot (-2)^{n - 1} \quad\hbox{and}\quad x_{n - 2} = 4 \cdot 7^{n - 2} + 5 \cdot (-2)^{n - 2}.$$

The fact that I need both of these formulas to do the induction step is why I'm using a generalized or strong induction. If I did a standard induction where I just assumed the result for $n - 1$ , I would not have it for $n - 2$ .

I have to show that the formula holds for n. I start with the recursion formula that defines $x_n$ , substitute the results for $x_{n - 1}$ and $x_{n - 2}$ , and do some algebra:

$$\eqalign{ x_n & = 5 x_{n - 1} + 14 x_{n - 2} \cr & = 5 \left(4 \cdot 7^{n - 1} + 5 \cdot (-2)^{n - 1}\right) + 14 \left(4 \cdot 7^{n - 2} + 5 \cdot (-2)^{n - 2}\right) \cr & = \left(20 \cdot 7^{n - 1} + 56 \cdot 7^{n - 2}\right) + \left(25 \cdot (-2)^{n - 1} + 70 \cdot (-2)^{n - 2}\right) \cr & = 4 \cdot 7^{n - 2} (5 \cdot 7 + 14) + 5 \cdot (-2)^{n - 2} (5 \cdot (-2) + 14) \cr & = 4 \cdot 7^{n - 2} \cdot 49 + 5 \cdot (-2)^{n - 2} \cdot 4 \cr & = 4 \cdot 7^{n - 2} \cdot 7^2 + 5 \cdot (-2)^{n - 2} \cdot (-2)^2 \cr & = 4 \cdot 7^n + 5 \cdot (-2)^n \cr}$$

This proves the result for n, so the result holds for all $n \ge 0$ by induction.

Here are some remarks about the algebra I did. My target expression $4 \cdot 7^n + 5 \cdot (-2)^n$ has a power of 7 and a power of -2. So I began by grouping terms into powers of 7 and powers of -2.

Next, to try to make what I had look like what I wanted, I factor out $4 \cdot 7^{n - 2}$ and $5 \cdot (-2)^{n - 2}$ . Then simplifying what was left produced the powers ($7^2$ and $(-2)^2$ ) that I needed to finish. Perhaps it looks like magic, but as we've seen in other proofs, if your steps are correct, it has to work --- you know what the final expression should be.

In the examples that follow, I use induction to prove inequalities and a divisibility result. The general setup for the inductions remains the same --- it's just the specific work that differs.

Example. Prove that

$$8^n \ge 6^n + 28 \quad\hbox{for}\quad n \ge 2.$$

For $n = 2$ ,

$$8^n = 8^2 = 64 \quad\hbox{while}\quad 6^n + 28 = 6^2 + 28 = 64.$$

The result holds for $n = 2$ .

Assume that the result holds for n:

$$8^n \ge 6^n + 28.$$

I'll prove it for $n + 1$ . To get the proof started, I make a "$8^n$ " term appear using algebra, so I can use the induction assumption.

$$\eqalign{ 8^{n + 1} & = 8 \cdot 8^n \cr & \ge 8 \cdot (6^n + 28) \cr & = 8 \cdot 6^n + 224 \cr & > 6 \cdot 6^n + 28 \cr & = 6^{n + 1} + 28 \cr}$$

(In the inequality which gave the second-to-the-last line, I used the facts that $8 > 6$ and $224 > 28$ to replace the existing terms so I could match the target.)

This proves the result for $n + 1$ , so the result is true for all $n \ge 2$ by induction.

Example. Prove that for $n \ge 6$ ,

$$3^n > 2 n^3.$$

In this case, the basis step is $n = 6$ , because the result is to be proved for $n \ge 6$ . (Try some numbers and you'll find the $2 n^3$ can be bigger than $3^n$ for some numbers smaller than 6 .)

For $n = 6$ ,

$$3^n = 3^6 = 729 \quad\hbox{while}\quad 2 n^3 = 2 \cdot 6^3 = 432.$$

The result is true for $n = 6$ .

Assume that the result holds for n:

$$3^n > 2 n^3.$$

I have to prove the result for $n + 1$ .

$$\eqalign{ 3^{n + 1} & = 3 \cdot 3^n \cr & > 3 \cdot 2 n^3 \cr & = 6 n^3 \cr}$$

Thus, I have

$$3^{n + 1} > 6 n^3.$$

On scratch paper, I see that my target inequality is

$$3^{n + 1} > 2 (n + 1)^3 = 2 n^3 + 6 n^2 + 6 n + 2.$$

So my strategy will be to break up the $6 n^3$ that I have so far into 4 pieces, each of which will be greater than or equal to one of the 4 pieces of $2 n^3 + 6 n^2 + 6 n + 2$ . I will do this in steps.

Since $n \ge 6$ and $3 > 2$ , I have

$$3 n^3 > 2 n^3. \eqno{(1)}$$

Again, since $n \ge 6$ , multiplying both sides by $n^2$ , I get

$$n^3 \ge 6 n^2. \eqno{(2)}$$

Since $n \ge 6 > 0$ , it follows that $n^2 \ge 6 n > n$ . So taking the last inequality and adding another term, I have

$$n^3 \ge 6 n^2 > 6 n. \eqno{(3)}$$

Finally, $n \ge 6$ gives

$$n^3 \ge 216 > 2. \eqno{(4)}$$

Adding the inequalities (1), (2), (3), and (4), I have

$$\eqalign{ 3 n^3 + n^3 + n^3 + n^3 & > 2 n^3 + 6 n^2 + 6 n + 2 \cr 6 n^3 & > 2 n^3 + 6 n^2 + 6 n + 2 \cr}$$

Combine this with the inequality I proved earlier:

$$\eqalign{ 3^{n + 1} & > 6 n^3 \cr & > 2 n^3 + 6 n^2 + 6 n + 2 \cr & = 2 (n^3 + 3 n^2 + 3 n + 1) \cr & = 2 (n + 1)^3 \cr}$$

This proves the result for $n + 1$ , so the result is true for all $n \ge 6$ by induction.

There are other ways to prove the key inequality $6 n^3 > 2 n^3 + 6 n^2 + 6 n + 2$ . For example, you could use calculus: After some algebra, you get the inequality $2 n^3 - 3 n^2 - 3 n - 1 > 0$ . Take $f(n) = 2 n^3 - 3 n^2 - 3 n - 1$ . Note that $f(6) > 0$ , and show that $f'(n) > 0$ for $n \ge 6$ , so the function increases.

This proof is a little involved, so for starters try to understand why each step is correct before trying to grasp the whole. Don't feel bad if you think that you wouldn't have figured this out by yourself! There are math problems that stump even the best mathematicians. The more experience you get, the more you will be able to do by yourself.

For the next example, remember that if m and n are integers, m divides n (in symbols, $m \mid n$ ) if $m k = n$ for some integer n.

Example. Prove that for $n \ge 0$ ,

$$6 \mid 5^{2 n} - 1.$$

You can do this proof directly, without induction. But I'll give an induction proof by way of example.

For $n = 0$ , I have

$$5^{2 n} - 1= 5^0 - 1 = 0.$$

Since $6 \mid 0$ , the result holds for $n = 0$ .

Assume that the result holds for n:

$$6 \mid 5^{2 n} - 1.$$

I can write this as $6 k = 5^{2 n} - 1$ for some integer k, or

$$5^{2 n} = 6 k + 1.$$

I must prove the result for $n + 1$ . As usual, the first thing I'll do is to work on the given expression to get (part of) the induction assumption to appear.

$$\eqalign{ 5^{2 (n + 1)} - 1 & = 5^{(2 n + 2)} - 1 \cr & = 5^{2 n} \cdot 5^2 - 1 \cr}$$

I have the "$5^{2 n}$ " which is part of the induction assumption. Now $6 \mid 5^{2 n} - 1$ means $6 k = 5^{2 n} - 1$ for some integer k, or

$$5^{2 n} = 6 k + 1.$$

Substituting this into the expression above, I get

$$\eqalign{ 5^{2 n} \cdot 5^2 - 1 & = (6 k + 1) \cdot 25 - 1 \cr & = 6 (25 k) + 25 - 1 \cr & = 6 (25 k) + 24 \cr & = 6 (25 k + 4) \cr}$$

All together,

$$5^{2 (n + 1)} - 1 = 6 (25 k + 4).$$

Therefore, $6 \mid 5^{2 (n + 1)} - 1$ . This proves the result for $n + 1$ , so the result holds for $n \ge 0$ by induction.

Here's a sketch of a direct proof: Write $5^{2 n} - 1 = (5^2)^n - 1 = 25^n - 1$ . Then use the formula

$$x^n - 1 = (x - 1)(x^{n - 1} + x^{n - 2} + \cdots + x + 1).$$

Lines and regions in the plane. This is an extended example which illustrates how you might "guess" a formula, then confirm it using induction.

Suppose we draw lines in the plane, one after another:

$$\hbox{\epsfysize=1.5in \epsffile{induction-2.eps}}$$

Each line that we draw should satisfy the following conditions:

1. It should not be parallel to any of the previous lines.

2. It should intersect all of the previous lines.

3. It should not pass through the intersection point of any two of the previous lines.

The lines in the picture above satisfy these conditions.

Question: Into how many regions do the lines divide the plane?

Before we even consider this question, we should be careful that we can actually do what we require. In particular, how do we know we can satisfy conditions 2 and 3?

$$\hbox{\epsfysize=1.5in \epsffile{induction-3.eps}}$$

Try it yourself (maybe with a drawing program on a computer). It starts to become a little tricky to get the next line to cross all of the previous lines. Imagine that you had 100 lines and you were trying to draw one more!

I'll prove this is possible by induction.

Proposition. Suppose there are n lines in the plane, each of which intersects all the others, and such that no three lines intersect. Then there is a line which intersects all n lines, and does not go through any of their intersections.

Proof. From geometry, two lines are parallel if and only if they have the same slope. So if two lines have different slopes, they aren't parallel, and they must intersect. We'll use this to give an induction proof.

We can get started and draw the first line wherever we want.

Then suppose we've draw lines $L_1$ , $L_2$ , and so on, all the way up to $L_n$ . We want to draw the $(n + 1)^{\rm st}$ line so that it intersects the n previous lines.

Suppose the slope of $L_1$ is $m_1$ , the slope of $L_2$ is $m_2$ , and so on. We have n slopes:

$$m_1, \quad m_2, \quad \ldots \quad m_n.$$

These are n different numbers (where a "number" could include the designation "undefined" if one of the lines is vertical). The numbers are different because these n lines intersect, and these numbers are their slopes.

Pick a number $m_{n + 1}$ which is different from all of these m's. To make the arguments that follow easier, I'll also assume $m_{n + 1}$ is not "undefined". I can pick such a number $m_{n + 1}$ because there are infinitely many real numbers, so there are real numbers different from the previous m's and "undefined".

Consider a line $L_{n + 1}$ with slope $m_{n + 1}$ . Since $m_{n + 1}$ is different from all the other m's, the line $L_{n + 1}$ must intersect the n previous lines.

How can we ensure that this new line does not go through the intersections of any of the previous lines? The n previous lines intersect in a finite number of points. Consider the lines with slope $m_{n + 1}$ which go through these intersection points.

$$\hbox{\epsfysize=1.5in \epsffile{induction-4.eps}}$$

In the picture above, the dots represent the intersection point of the previous lines, and the lines I've drawn show the lines with slope $m_{n + 1}$ which pass through them.

Each of those lines has a y-intercept, so there are finitely many such y-intercepts.

$$\hbox{\epsfysize=2in \epsffile{induction-5.eps}}$$

Let's say the y-intercepts are $b_1$ , $b_2$ , and so on. Because there are only finitely many b's, I can choose a number b different from all of them.

Consider the line $y = m_{n + 1} x + b$ . It has slope $m_{n + 1}$ , so it intersects all the previous lines. Its y-intercept is different from the y-intercepts of all the intersection point lines, so it does not pass through any of the intersection points.

This proves the result for n lines, so it's true for any number of lines, by induction.

At this point, we know our question makes sense, so we can think about answering it. Let's see if we can see a pattern.

$$\hbox{\epsfysize=1.5in \epsffile{induction-6.eps}}$$

We go from 2 regions to 4 regions, and $2 + 2 = 4$ . We go from 4 regions to 7 regions, and $4 + 3 = 7$ . If you draw a picture, you'll find that with 4 lines there are 11 regions, and $7 + 4 = 11$ . Let's set up some notation. Let $x_n$ be the number of regions made by n lines. It appears that

$$x_{n + 1} = x_n + (n + 1) \quad\hbox{for}\quad n \ge 1.$$

The formula seems to work for $n = 1, 2, 3$ .

Let's see if we can verify this with a picture. Suppose I have n lines. When I draw the $(n + 1)^{\rm st}$ line, it must cross each of the previous n lines. Schematically:

$$\hbox{\epsfysize=1.5in \epsffile{induction-7.eps}}$$

As the new line crosses $L_1$ , it splits the region on the left of $L_1$ , and one new region is added. As the new line crosses $L_2$ , it splits the region between $L_1$ and $L_2$ , and one new region is added. And so on. All together, $n + 1$ new regions are added. That is, $n + 1$ regions are added to $x_n$ to get $x_{n + 1}$ .

This recursion isn't bad, but it would be nice to have a "closed-form" expression which gives $x_n$ in terms of n. We'll show how to go from the recursion to such an expression in the next theorem.

Theorem. Suppose $n \ge 1$ , and a sequence is defined recursively by $x_1 = 2$ , and

$$x_{n + 1} = x_n + (n + 1) \quad\hbox{for}\quad n \ge 1.$$

Then for $n \ge 1$ ,

$$x_n = \dfrac{n (n + 1)}{2} + 1.$$

Proof. Method 1. This method doesn't use induction, but I'll point out afterward some details which it omits.

Write out the recursion $x_n = x_{n - 1} + n$ for $n = 2, 3, \ldots n$ , then add the equations:

$$\eqalign{ x_2 & = x_1 + 2 \cr x_3 & = x_2 + 3 \cr x_4 & = x_3 + 4 \cr & \vdots \cr x_n & = x_{n - 1} + n \cr \noalign{\vskip2pt \hrule \vskip2pt} x_2 + x_3 + x_4 + \cdots + x_n & = x_1 + x_2 + x_3 + \cdots + x_{n - 1} + (2 + 3 + 4 + \cdots + n) \cr}$$

I subtract $x_2 + x_3 + \cdots + x_{n - 1}$ from both sides:

$$x_n = x_1 + (2 + 3 + 4 + \cdots + n).$$

Now

$$1 + 2 + 3 + 4 + \cdots + n = \dfrac{n (n + 1)}{2}, \quad\hbox{so}\quad 2 + 3 + 4 + \cdots + n = \dfrac{n (n + 1)}{2} - 1.$$

Also, $x_1 = 2$ . Plugging these into the equation for $x_n$ , I get

$$x_n = 2 + \left(\dfrac{n (n + 1)}{2} - 1\right) = \dfrac{n (n + 1)}{2} + 1.$$

Method 2. For $n = 1$ , the formula gives

$$x_1 = \dfrac{1 \cdot 2}{2} + 1 = 2.$$

The result holds for $n = 1$ .

Assume that the result is true for n:

$$x_n = \dfrac{n (n + 1)}{2} + 1.$$

I will prove it for $n + 1$ :

$$\eqalign{ x_{n + 1} & = x_n + (n + 1) \cr \noalign{\vskip2pt} & = \left(\dfrac{n (n + 1)}{2} + 1\right) + (n + 1) \cr \noalign{\vskip2pt} & = \left(\dfrac{n (n + 1)}{2} + \dfrac{2 (n + 1)}{2}\right) + 1 \cr \noalign{\vskip2pt} & = \dfrac{n + 1}{2} \cdot (n + 2) + 1 \cr \noalign{\vskip2pt} & = \dfrac{(n + 1)(n + 2)}{2} + 1 \cr}$$

This proves the result for $n + 1$ , so the result is true for all $n \ge 1$ by induction.

The first method may seem pretty appealing --- you may have seen similar techniques used in computing values of infinite series ("telescoping"). Depending on what you're willing to assume, this may be adequate as a proof. Let's note a couple of things.

First, what does "$x_2 + x_3 + x_4 + \cdots + x_n$ " mean? Maybe it's obvious to you: It means "add up the numbers $x_2$ , $x_3$ , and so on up to $x_n$ . However, addition is a binary operation: It tells you how to add 2 numbers at a time, not 100 numbers or $n - 1$ numbers. Adding more than two numbers at a time actually requires a definition.

Well, you might say: Just add the numbers two at a time. And in fact, you can define a sum of more than 2 numbers recursively in this way: If you already know how to add n numbers, then to add $n + 1$ numbers, you can make the following definition:

$$x_1 + x_2 + \cdots + x_n + x_{n + 1} = (x_1 + x_2 + \cdots + x_n) + x_{n + 1}.$$

The right side is a sum of two numbers, so this works.

But a second issue arises, and that is that the definition above picks a particular way of grouping the numbers when you add. Now the associative law for addition tells you that you get the same thing when you group 3 numbers for addition in two different ways:

$$a + (b + c) = (a + b) + c.$$

However, when I write "$x_2 + x_3 + x_4 + \cdots + x_n$ " I'm implying that if I add any number of numbers, I get the same result regardless of how I group the additions. For example,

$$(a + b) + (c + (d + e)) = a + (b + (c + (d + e))).$$

Try deriving the last line using associativity for just three numbers. We're saying that the same thing works for any grouping, and any number of numbers. And it's true! How do you prove it? You use induction! I won't give the proof here, but you might try it yourself as a challenge.

In other math courses, you didn't worry about these issues, and things work the way you'd expect. But as you've already noticed, proving things is a lot harder than simply know or believing that they're true.

Contact information

Bruce Ikenaga's Home Page

Copyright 2019 by Bruce Ikenaga