ads Mathematical Induction

Section 3.7 Mathematical Induction

Subsection 3.7.1 Introduction, First Example

In this section, we will examine mathematical induction, a technique for proving propositions over the positive integers. Mathematical induction reduces the proof that all of the positive integers belong to a truth set to a finite number of steps.

Example 3.7.1. Formula for Triangular Numbers.

Consider the following proposition over the positive integers, which we will label

p (n) :

The sum of the positive integers from 1 to

n

\frac{n (n + 1)}{2} .

This is a well-known formula that is quite simple to verify for a given value of

n .

For example,

p (5)

is: The sum of the positive integers from 1 to 5 is

\frac{5 (5 + 1)}{2} .

Indeed,

1 + 2 + 3 + 4 + 5 = 15 = \frac{5 (5 + 1)}{2} .

However, this doesn’t serve as a proof that

p (n)

is a tautology. All that we’ve established is that

5

is in the truth set of

p .

Since the positive integers are infinite, we certainly can’t use this approach to prove the formula.

🔗

An Analogy: A proof by mathematical induction is similar to knocking over a row of closely spaced dominos that are standing on end. To knock over the dominos in Figure 3.7.2, all you need to do is push the first domino over. To be assured that they all will be knocked over, some work must be done ahead of time. The dominos must be positioned so that if any domino is pushed is knocked over, it will push the next domino in the line.

A line of dominos in the process of being knocked over. — 🔗
Figure 3.7.2. An analogy for Mathematical Induction, Creative Commons photo by Ranveig Thattai

🔗

Returning to Example 3.7.1 imagine the propositions

p (1), p (2), p (3), \dots

to be an infinite line of dominos. Let’s see if these propositions are in the same formation as the dominos were. First, we will focus on one specific point of the line:

p (99)

and

p (100) .

We are not going to prove that either of these propositions is true, just that the truth of

p (99)

implies the truth of

p (100) .

In terms of our analogy, if

p (99)

is knocked over, it will knock over

p (100) .

🔗

In proving

p (99) \Rightarrow p (100),

we will use

p (99)

as our premise. We must prove: The sum of the positive integers from 1 to 100 is

\frac{100 (100 + 1)}{2} .

We start by observing that the sum of the positive integers from 1 to 100 is

(1 + 2 + \dots + 99) + 100 .

That is, the sum of the positive integers from 1 to 100 equals the sum of the first ninety-nine plus the final number, 100. We can now apply our premise,

p (99),

to the sum

1 + 2 + \dots + 99 .

After rearranging our numbers, we obtain the desired expression for

1 + 2 + \dots + 100 :

\begin{aligned} 1 + 2 + \dots + 99 + 100 & = (1 + 2 + \dots + 99) + 100 \\ = \frac{99 \cdot (99 + 1)}{2} + 100 by our assumption of p (99) \\ = \frac{99 \cdot 100}{2} + \frac{2 \cdot 100}{2} \\ = \frac{100 \cdot 101}{2} \\ = \frac{100 \cdot (100 + 1)}{2} \end{aligned} .

🔗

What we’ve just done is analogous to checking two dominos in a line and finding that they are properly positioned. Since we are dealing with an infinite line, we must check all pairs at once. This is accomplished by proving that

p (n) \Rightarrow p (n + 1)

for all

n \geq 1 :

\begin{aligned} 1 + 2 + \dots + n + (n + 1) & = (1 + 2 + \dots + n) + (n + 1) \\ = \frac{n (n + 1)}{2} + (n + 1) by p (n) \\ = \frac{n (n + 1)}{2} + \frac{2 (n + 1)}{2} \\ = \frac{(n + 1) (n + 2)}{2} \\ = \frac{(n + 1) ((n + 1) + 1)}{2} \end{aligned} .

🔗

They are all lined up! Now look at

p (1) :

The sum of the positive integers from 1 to 1 is

\frac{1 \cdot (1 + 1)}{2} .

Clearly,

p (1)

is true. This sets off a chain reaction. Since

p (1) \Rightarrow p (2),

p (2)

is true. Since

p (2) \Rightarrow p (3),

p (3)

is true; and so on.

◼

🔗

Theorem 3.7.3. The Principle of Mathematical Induction.

🔗

Let

p (n)

be a proposition over the positive integers. If

$p (1)$ is true, and
for all $n \geq 1,$ $p (n) \Rightarrow p (n + 1),$

🔗

then

p (n)

is a tautology.

🔗

Note: The truth of

p (1)

is called the basis for the induction proof. The premise that

p (n)

is true in the second part is called the induction hypothesis. The proof that

p (n)

implies

p (n + 1)

is called the induction step of the proof. Despite our analogy, the basis is usually done first in an induction proof. However, order doesn’t really matter.

🔗

Subsection 3.7.2 More Examples

Example 3.7.4. Generalized Detachment.

Consider the implication over the positive integers.

p (n) : q_{0} \to q_{1}, q_{1} \to q_{2}, \dots, q_{n - 1} \to q_{n}, q_{0} \Rightarrow q_{n}

A proof that

p (n)

is a tautology follows. Basis:

p (1)

q_{0} \to q_{1}, q_{0} \Rightarrow q_{1} .

This is the logical law of detachment which we know is true. If you haven’t done so yet, write out the truth table of

((q_{0} \to q_{1}) \land q_{0}) \to q_{1}

to verify this step.

Induction: Assume that

p (n)

is true for some

n \geq 1 .

We want to prove that

p (n + 1)

must be true. That is:

q_{0} \to q_{1}, q_{1} \to q_{2}, \dots, q_{n - 1} \to q_{n}, q_{n} \to q_{n + 1}, q_{0} \Rightarrow q_{n + 1}

Here is a direct proof of

p (n + 1) :

Table 3.7.5.

Step	Proposition	Justification
$1 - (n + 1)$	$q_{0} \to q_{1}, q_{1} \to q_{2}, \dots, q_{n - 1} \to q_{n}, q_{0}$	Premises
$n + 2$	$q_{n}$	$(1) - (n + 1),$ $p (n)$
$n + 3$	$q_{n} \to q_{n + 1}$	Premise
$n + 4$	$q_{n + 1}$	$(n + 2), (n + 3), detachment ◻$

Example 3.7.6. An example from Number Theory.

For all

n \geq 1,

n^{3} + 2 n

is a multiple of 3. An inductive proof follows:

Basis:

1^{3} + 2 (1) = 3

is a multiple of 3. The basis is almost always this easy!

Induction: Assume that

n \geq 1

and

n^{3} + 2 n

is a multiple of 3. Consider

(n + 1)^{3} + 2 (n + 1) .

Is it a multiple of 3?

\begin{aligned} (n + 1)^{3} + 2 (n + 1) & = n^{3} + 3 n^{2} + 3 n + 1 + (2 n + 2) \\ = n^{3} + 2 n + 3 n^{2} + 3 n + 3 \\ = (n^{3} + 2 n) + 3 (n^{2} + n + 1) \end{aligned} .

Yes,

(n + 1)^{3} + 2 (n + 1)

is the sum of two multiples of 3; therefore, it is also a multiple of 3.

◻

🔗

Now we will discuss some of the variations of the principle of mathematical induction. The first simply allows for universes that are similar to

P

such as

{- 2, - 1, 0, 1, \dots}

{5, 6, 7, 8, \dots} .

🔗

Theorem 3.7.7. Principle of Mathematical Induction (Generalized).

🔗

p (n)

is a proposition over

{k_{0}, k_{0} + 1, k_{0} + 2, \dots},

where

k_{0}

is any integer, then

p (n)

is a tautology if

🔗

$p (k_{0})$ is true, and
for all $n \geq k_{0},$ $p (n) \Rightarrow p (n + 1) .$

Example 3.7.8. A proof of the permutations formula.

In Chapter 2, we stated that the number of different permutations of

k

elements taken from an

n

element set,

P (n; k),

can be computed with the formula

\frac{n!}{(n - k)!} .

We can prove this statement by induction on

n .

For

n \geq 0,

let

q (n)

be the proposition

P (n; k) = \frac{n!}{(n - k)!} for all k, 0 \leq k \leq n .

Basis:

q (0)

states that

P (0; 0)

if is the number of ways that

0

elements can be selected from the empty set and arranged in order, then

P (0; 0) = \frac{0!}{0!} = 1 .

This is true. A general law in combinatorics is that there is exactly one way of doing nothing.

Induction: Assume that

q (n)

is true for some natural number

n .

It is left for us to prove that this assumption implies that

q (n + 1)

is true. Suppose that we have a set of cardinality

n + 1

and want to select and arrange

k

of its elements. There are two cases to consider, the first of which is easy. If

k = 0,

then there is one way of selecting zero elements from the set; hence

P (n + 1; 0) = 1 = \frac{(n + 1)!}{(n + 1 + 0)!}

and the formula works in this case.

The more challenging case is to verify the formula when

k

is positive and less than or equal to

n + 1 .

Here we count the value of

P (n + 1; k)

by counting the number of ways that the first element in the arrangement can be filled and then counting the number of ways that the remaining

k - 1

elements can be filled in using the induction hypothesis.

There are

n + 1

possible choices for the first element. Since that leaves

n

elements to fill in the remaining

k - 1

positions, there are

P (n; k - 1)

ways of completing the arrangement. By the rule of products,

\begin{aligned} P (n + 1; k) & = (n + 1) P (n; k - 1) \\ = (n + 1) \frac{n!}{(n - (k - 1))!} \\ = \frac{(n + 1) n!}{(n - k + 1)!} \\ = \frac{(n + 1)!}{((n + 1) - k)!} \end{aligned}

◼

🔗

Subsection 3.7.3 Course of Values Induction

🔗

A second variation allows for the expansion of the induction hypothesis. The course-of-values principle includes the previous generalization. It is also sometimes called strong induction.

🔗

Theorem 3.7.9. The Course-of-Values Principle of Mathematical Induction.

🔗

p (n)

is a proposition over

{k_{0}, k_{0} + 1, k_{0} + 2, \dots},

where

k_{0}

is any integer, then

p (n)

is a tautology if

🔗

$p (k_{0})$ is true, and
for all $n \geq k_{0},$ $p (k_{0}), p (k_{0} + 1), . . ., p (n) \Rightarrow p (n + 1) .$

🔗

A prime number is defined as a positive integer that has exactly two positive divisors, 1 and itself. There are an infinite number of primes. The list of primes starts with

2, 3, 5, 7, 11, \dots .

🔗

The proposition over

{2, 3, 4, . . .}

that we will prove here is

p (n) :

n

can be written as the product of one or more primes. In most texts, the assertion that

p (n)

is a tautology would appear as

🔗

Theorem 3.7.10. Existence of Prime Factorizations.

🔗

Every positive integer greater than or equal to 2 has a prime decomposition.

Proof.

If you were to encounter this theorem outside the context of a discussion of mathematical induction, it might not be obvious that the proof can be done by induction. Recognizing when an induction proof is appropriate is mostly a matter of experience. Now on to the proof!

Basis: Since 2 is a prime, it is already decomposed into primes (one of them).

Induction: Suppose that for some

n \geq 2

all of the integers

2, 3, . . ., n

have a prime decomposition. Notice the course-of-value hypothesis. Consider

n + 1 .

Either

n + 1

is prime or it isn’t. If

n + 1

is prime, it is already decomposed into primes. If not, then

n + 1

has a divisor,

d,

other than 1 and

n + 1 .

Hence,

n + 1 = c d

where both

c

and

d

are between 2 and

n .

By the induction hypothesis,

c

and

d

have prime decompositions,

c_{1} c_{2} \dots c_{s}

and

d_{1} d_{2} \dots d_{t}

, respectively. Therefore,

n + 1

has the prime decomposition

c_{1} c_{2} \dots c_{s} d_{1} d_{2} \dots d_{t} .

🔗

Axiom 3.7.11. Peano Postulates.

🔗

The system of positive integers consists of a nonempty set,

P;

a least element of

P,

denoted 1; and a “successor function,” s, with the properties

🔗

If $k \in P$ , then there is an element of $P$ called the successor of $k,$ denoted $s (k) .$
No two elements of $P$ have the same successor.
No element of $P$ has $1$ as its successor.
If $S \subseteq P,$ $1 \in S,$ and $k \in S \Rightarrow s (k) \in S,$ then $S = P .$

🔗

Notes:

🔗

You might recognize $s (k)$ as simply being $k + 1 .$
Axiom 4 is the one that makes mathematical induction possible. In an induction proof, we simply apply that axiom to the truth set of a proposition.

🔗

Exercises 3.7.4 Exercises

🔗

1.

🔗

Prove that the sum of the first

n

odd integers equals

n^{2}

Answer.

We wish to prove that

P (n) : 1 + 3 + 5 + \dots + (2 n - 1) = n^{2}

is true for

n ⩾ 1 .

Recall that the

n

th odd positive integer is

2 n - 1 .

Basis: for

n = 1,

P (n)

1 = 1^{2},

which is true

Induction: Assume that for some

n ⩾ 1,

P (n)

is true. Then we infer that

P (n + 1)

follows:

\begin{aligned} 1 + 3 + \dots + (2 (n + 1) - 1) & = (1 + 3 + \dots + (2 n - 1)) + (2 (n + 1) - 1) \\ = n^{2} + (2 n + 1) by P (n) and basic algebra \\ = (n + 1)^{2} ◼ \end{aligned}

🔗

2.

🔗

Prove that if

n \geq 1,

then

1 (1!) + 2 (2!) + \dots + n (n!) = (n + 1)! - 1 .

🔗

3.

🔗

Prove that for

n \geq 1 :

\sum_{k = 1}^{n} k^{2} = \frac{1}{6} n (n + 1) (2 n + 1) .

Answer.

Proof:

Basis: We note that the proposition is true when $n = 1 :$ $\sum_{k = 1}^{1} k^{2} = 1 = \frac{1 (2) (3)}{6} .$
Induction: Assume that the proposition is true for some $n \geq 1 .$ This is the induction hypothesis.

$\begin{aligned} \sum_{k = 1}^{n + 1} k^{2} & = \sum_{k = 1}^{n} k^{2} + (n + 1)^{2} \\ = \frac{n (n + 1) (2 n + 1)}{6} + (n + 1)^{2} by the induction hypothesis \\ = \frac{(n + 1) (2 n^{2} + 7 n + 6)}{6} \\ = \frac{(n + 1) (n + 2) (2 n + 3)}{6} ◼ \end{aligned}$

Therefore, the truth of the proposition for $n$ implies the truth of the proposition for $n + 1 .$

🔗

4.

🔗

Prove that for

n \geq 0 :

\sum_{k = 0}^{n} 2^{k} = 2^{n + 1} - 1 .

🔗

5.

🔗

Use mathematical induction to show that for

n \geq 1,

\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \dots + \frac{1}{n (n + 1)} = \frac{n}{n + 1} .

Solution.

Basis: For

n = 1,

we observe that

\frac{1}{(1 \cdot 2)} = \frac{1}{(1 + 1)}

Induction: Assume that for some

n ⩾ 1,

the formula is true.

Then:

\begin{aligned} \frac{1}{(1 \cdot 2)} + \dots + \frac{1}{n (n + 1)} + \frac{1}{(n + 1) (n + 2)} & = \frac{n}{n + 1} + \frac{1}{(n + 1) (n + 2)} \\ = \frac{(n + 2) n}{(n + 1) (n + 2)} + \frac{1}{(n + 1) (n + 2)} \\ = \frac{(n + 1)^{2}}{(n + 1) (n + 2)} \\ = \frac{n + 1}{n + 2} ◼ \end{aligned}

🔗

6.

🔗

Prove that if

n \geq 2,

the generalized DeMorgan’s Law is true:

\neg (p_{1} \land p_{2} \land ... \land p_{n}) \Leftrightarrow (\neg p_{1}) \lor (\neg p_{2}) \lor \dots \lor (\neg p_{n}) .

🔗

7.

🔗

The number of strings of

n

zeros and ones that contain an even number of ones is

2^{n - 1} .

Prove this fact by induction for

n \geq 1 .

Answer.

Let

A_{n}

be the set of strings of zeros and ones of length

n

(we assume that

| A_{n} | = 2^{n}

is known). Let

E_{n}

be the set of the “even” strings, and

E_{n}^{c} =

the odd strings. The problem is to prove that for

n ⩾ 1,

| E_{n} | = 2^{n - 1} .

Clearly,

| E_{1} | = 1,

and, if for some

n ⩾ 1, | E_{n} | = 2^{n - 1},

it follows that

| E_{n + 1} | = 2^{n}

by the following reasoning.

We partition

E_{n + 1}

according to the first bit:

E_{n + 1} = {1 s ∣ s \in E_{n}^{c}} \cup {0 s ∣ s \in E_{n}}

Since

{1 s ∣ s \in E_{n}^{c}}

and

{0 s ∣ s \in E_{n}}

are disjoint, we can apply the addition law. Therefore,

\begin{aligned} | E_{n + 1} | & = | E_{n}^{c} | + | E_{n} | \\ = 2^{n - 1} + (2^{n} - 2^{n - 1}) = 2^{n} . ◼ \end{aligned}

🔗

8.

🔗

Let

p (n)

8^{n} - 3^{n}

is a multiple of 5. Prove that

p (n)

is a tautology over

N .

🔗

9.

🔗

Suppose that there are

n

people in a room,

n \geq 1,

and that they all shake hands with one another. Prove that

\frac{n (n - 1)}{2}

handshakes will have occurred.

Solution.

Assume that for

n

persons

(n ⩾ 1), \frac{(n - 1) n}{2}

handshakes take place. If one more person enters the room, he or she will shake hands with

n

people,

\begin{aligned} \frac{(n - 1) n}{2} + n & = \frac{n^{2} - n + 2 n}{2} \\ = \frac{n^{2} + n}{2} = \frac{n (n + 1)}{2} \\ = \frac{((n + 1) - 1) (n + 1)}{2} ◼ \end{aligned}

Also, for

n = 1,

there are no handshakes, which matches the conjectured formula:

\frac{(1 - 1) (1)}{2} = 0 ◼ .

🔗

10.

🔗

Prove that it is possible to make up any postage of eight cents or more using only three- and five-cent stamps.

🔗

11.

🔗

Generalized associativity. It is well known that if

a_{1},

a_{2},

and

a_{3}

are numbers, then no matter what order the sums in the expression

a_{1} + a_{2} + a_{3}

are taken, the result is always the same. Call this fact

p (3) .

Prove using course-of-values induction that if

a_{1},

a_{2},

\dots,

and

a_{n}

are numbers, then no matter what order the sums in the expression

a_{1} + a_{2} + \dots + a_{n}

are taken, the result is always the same.

Solution.

Let

p (n)

be “

a_{1} + a_{2} + \dots + a_{n}

has the same value no matter how it is evaluated.”

Basis:

a_{1} + a_{2} + a_{3}

may be evaluated only two ways. Since + is associative,

(a_{1} + a_{2}) + a_{3} = a_{1} + (a_{2} + a_{3}) .

Hence,

p (3)

is true.

Induction: Assume that for some

n \geq 3,

p (3), p (4), \dots, p (n)

are all true. Now consider the sum

a_{1} + a_{2} + \dots + a_{n} + a_{n + 1} .

Any of the

n

additions in this expression can be applied last. If the

j

th addition is applied last, we have

c_{j} = (a_{1} + a_{2} + \dots + a_{j}) + (a_{j + 1} + \dots + a_{n + 1}) .

No matter how the expression to the left and right of the

j^{th}

addition are evaluated, the result will always be the same by the induction hypothesis, specifically

p (j)

and

p (n + 1 - j) .

We now can prove that

c_{1} = c_{2} = \dots = c_{n} .

i < j,

\begin{aligned} c_{i} & = (a_{1} + a_{2} + \dots + a_{i}) + (a_{i + 1} + \dots + a_{n + 1}) \\ = (a_{1} + a_{2} + \dots + a_{i}) + (a_{i + 1} + \dots + a_{j}) + (a_{j + 1} + \dots + a_{n + 1}) \\ = ((a_{1} + a_{2} + \dots + a_{i}) + (a_{i + 1} + \dots + a_{j})) + (a_{j + 1} + \dots + a_{n + 1}) \\ = (a_{1} + a_{2} + \dots + a_{j}) + (a_{j + 1} + \dots + a_{n + 1}) \\ = c_{j} ◼ \end{aligned}

🔗

12.

🔗

Let

S

be the set of all numbers that can be produced by applying any of the rules below in any order a finite number of times.

Rule 1: $\frac{1}{2} \in S$
Rule 2: $1 \in S$
Rule 3: If $a$ and $b$ have been produced by the rules, then $a b \in S .$
Rule 4: If $a$ and $b$ have been produced by the rules, then $\frac{a + b}{2} \in S .$

🔗

Prove that

a \in S \Rightarrow 0 \leq a \leq 1 .

Hint.

The number of times the rules are applied should be the integer that you do the induction on.

🔗

13.

🔗

Proofs involving objects that are defined recursively are often inductive. A recursive definition is similar to an inductive proof. It consists of a basis, usually the simple part of the definition, and the recursion, which defines complex objects in terms of simpler ones. For example, if

x

is a real number and

n

is a positive integer, we can define

x^{n}

as follows:

Basis: $x^{1} = x .$
Recursion: if $n \geq 2,$ $x^{n} = x^{n - 1} x .$

🔗

For example,

x^{3} = x^{2} x

(x^{1} x) x = (x x) x .

🔗

Prove that if

n, m \in P,

x^{m + n} = x^{m} x^{n} .

There is much more on recursion in Chapter 8.

Hint.

Let

p (m)

be the proposition that

x^{m + n} = x^{m} x^{n}

for all

n \geq 1 .

Solution.

For

m ⩾ 1,

let

p (m) be x^{n + m} = x^{n} x^{m}

for all

n ⩾ 1 .

The basis for this proof follows directly from the basis for the definition of exponentiation.

Induction: Assume that for some

m \geq 1,

p (m)

is true. Then

\begin{aligned} x^{n + (m + 1)} & = x^{(n + m) + 1} by associativity of integer addition \\ = x^{n + m} x^{1} by recursive definition \\ = x^{n} x^{m} x^{1} induction hypothesis \\ = x^{n} x^{m + 1} recursive definition ◼ \end{aligned}

You have attempted of activities on this page.

Prev Top Next