AATA Mathematical Induction

Section 2.1 Mathematical Induction

Suppose we wish to show that

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

🔗

for any natural number

n .

This formula is easily verified for small numbers such as

n = 1,

2,

3,

4,

but it is impossible to verify for all natural numbers on a case-by-case basis. To prove the formula true in general, a more generic method is required.

🔗

Suppose we have verified the equation for the first

n

cases. We will attempt to show that we can generate the formula for the

(n + 1)

th case from this knowledge. The formula is true for

n = 1

since

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

🔗

If we have verified the first

n

cases, then

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

🔗

This is exactly the formula for the

(n + 1)

th case.

🔗

This method of proof is known as mathematical induction. Instead of attempting to verify a statement about some subset

S

of the positive integers

N

on a case-by-case basis, an impossible task if

S

is an infinite set, we give a specific proof for the smallest integer being considered, followed by a generic argument showing that if the statement holds for a given case, then it must also hold for the next case in the sequence. We summarize mathematical induction in the following axiom.

🔗

Principle 2.1. First Principle of Mathematical Induction.

🔗

Let

S (n)

be a statement about integers for

n \in N

and suppose

S (n_{0})

is true for some integer

n_{0} .

If for all integers

k

with

k \geq n_{0},

S (k)

implies that

S (k + 1)

is true, then

S (n)

is true for all integers

n

greater than or equal to

n_{0} .

🔗

Example 2.2.

🔗

For all integers

n \geq 3,

2^{n} > n + 4 .

Since

8 = 2^{3} > 3 + 4 = 7,

🔗

the statement is true for

n_{0} = 3 .

Assume that

2^{k} > k + 4

for

k \geq 3 .

Then

2^{k + 1} = 2 \cdot 2^{k} > 2 (k + 4) .

But

2 (k + 4) = 2 k + 8 > k + 5 = (k + 1) + 4

🔗

since

k

is positive. Hence, by induction, the statement holds for all integers

n \geq 3 .

🔗

Example 2.3.

🔗

Every integer

10^{n + 1} + 3 \cdot 10^{n} + 5

is divisible by

9

for

n \in N .

For

n = 1,

10^{1 + 1} + 3 \cdot 10 + 5 = 135 = 9 \cdot 15

🔗

is divisible by

9 .

Suppose that

10^{k + 1} + 3 \cdot 10^{k} + 5

is divisible by

9

for

k \geq 1 .

Then

\begin{aligned} 10^{(k + 1) + 1} + 3 \cdot 10^{k + 1} + 5 & = 10^{k + 2} + 3 \cdot 10^{k + 1} + 50 - 45 \\ = 10 (10^{k + 1} + 3 \cdot 10^{k} + 5) - 45 \end{aligned}

🔗

is divisible by

9 .

🔗

Example 2.4.

🔗

We will prove the binomial theorem using mathematical induction; that is,

(a + b)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n - k},

🔗

where

a

and

b

are real numbers,

n \in N,

and

(\binom{n}{k}) = \frac{n!}{k! (n - k)!}

🔗

is the binomial coefficient. We first show that

(\binom{n + 1}{k}) = (\binom{n}{k}) + (\binom{n}{k - 1}) .

🔗

This result follows from

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

🔗

n = 1,

the binomial theorem is easy to verify. Now assume that the result is true for

n

greater than or equal to

1 .

Then

\begin{aligned} (a + b)^{n + 1} & = (a + b) (a + b)^{n} \\ = (a + b) (\sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n - k}) \\ = \sum_{k = 0}^{n} (\binom{n}{k}) a^{k + 1} b^{n - k} + \sum_{k = 0}^{n} (\binom{n}{k}) a^{k} b^{n + 1 - k} \\ = a^{n + 1} + \sum_{k = 1}^{n} (\binom{n}{k - 1}) a^{k} b^{n + 1 - k} + \sum_{k = 1}^{n} (\binom{n}{k}) a^{k} b^{n + 1 - k} + b^{n + 1} \\ = a^{n + 1} + \sum_{k = 1}^{n} [(\binom{n}{k - 1}) + (\binom{n}{k})] a^{k} b^{n + 1 - k} + b^{n + 1} \\ = \sum_{k = 0}^{n + 1} (\binom{n + 1}{k}) a^{k} b^{n + 1 - k} . \end{aligned}

🔗

We have an equivalent statement of the Principle of Mathematical Induction that is often very useful.

🔗

Principle 2.5. Second Principle of Mathematical Induction.

🔗

Let

S (n)

be a statement about integers for

n \in N

and suppose

S (n_{0})

is true for some integer

n_{0} .

S (n_{0}), S (n_{0} + 1), \dots, S (k)

imply that

S (k + 1)

for

k \geq n_{0},

then the statement

S (n)

is true for all integers

n \geq n_{0} .

🔗

A nonempty subset

S

Z

is well-ordered if

S

contains a least element. Notice that the set

Z

is not well-ordered since it does not contain a smallest element. However, the natural numbers are well-ordered.

🔗

Principle 2.6. Principle of Well-Ordering.

🔗

Every nonempty subset of the natural numbers is well-ordered.

🔗

The Principle of Well-Ordering is equivalent to the Principle of Mathematical Induction.

🔗

Lemma 2.7.

🔗

The Principle of Mathematical Induction implies that

1

is the least positive natural number.

Proof.

Let

S = {n \in N : n \geq 1} .

Then

1 \in S .

Assume that

n \in S .

Since

0 < 1,

it must be the case that

n = n + 0 < n + 1 .

Therefore,

1 \leq n < n + 1 .

Consequently, if

n \in S,

then

n + 1

must also be in

S,

and by the Principle of Mathematical Induction, and we have

S = N .

🔗

Theorem 2.8.

🔗

The Principle of Mathematical Induction implies the Principle of Well-Ordering. That is, every nonempty subset of

N

contains a least element.

Proof.

We must show that if

S

is a nonempty subset of the natural numbers, then

S

contains a least element. If

S

contains 1, then the theorem is true by Lemma 2.7. Assume that if

S

contains an integer

k

such that

1 \leq k \leq n,

then

S

contains a least element. We will show that if a set

S

contains an integer less than or equal to

n + 1,

then

S

has a least element. If

S

does not contain an integer less than

n + 1,

then

n + 1

is the smallest integer in

S .

Otherwise, since

S

is nonempty,

S

must contain an integer less than or equal to

n .

In this case, by induction,

S

contains a least element.

🔗

Induction can also be very useful in formulating definitions. For instance, there are two ways to define

n!,

the factorial of a positive integer

n .

The explicit definition: $n! = 1 \cdot 2 \cdot 3 \dots (n - 1) \cdot n .$
The inductive or recursive definition: $1! = 1$ and $n! = n (n - 1)!$ for $n > 1 .$

🔗

Every good mathematician or computer scientist knows that looking at problems recursively, as opposed to explicitly, often results in better understanding of complex issues.

Prev Top Next