EF Principle of Mathematical Induction

Section 7.1 Principle of Mathematical Induction

Axiom 7.1.1. Principle of Mathematical Induction.

Suppose

P (n)

is a predicate where the variable

n

has domain the positive, whole numbers. If

🔗
$P (1)$ is true, and
🔗
$(\forall k) (P (k) \to P (k + 1))$ is true,

🔗

then

(\forall n) P (n)

is true.

🔗

It is usual to take the principle of mathematical induction as an axiom; that is, we assume that mathematical induction is valid without proving it.

🔗

Below is an outline of the idea behind why it is reasonable to assume that mathematical induction is valid. However, this outline does not constitute a proof since it technically uses mathematical induction implicitly.

🔗

Idea.

🔗

Suppose

n

is fixed. We have a sequence of valid arguments:

P (1) \to P (2)

P (1)

P (2)

P (2) \to P (3)

P (2)

P (3)

🔗

\dots

P (n - 1) \to P (n)

P (n - 1)

P (n)

🔗

Each is valid (modus ponens). So if we make the two assumptions stated in the principles (i.e. that

P (1)

is true and that

P (k) \to P (k + 1)

is always true) we can trace the flow of truth from premises to conclusion in each argument in turn:

First argument: 🔗
Premises true so conclusion is true.
Second argument: 🔗
Premises true (using conclusion of the first argument) so conclusion is true.
Third argument: 🔗
…
${(n - 1)}^{th}$ argument: 🔗
Premises true (using conclusion of the ${(n - 2)}^{th}$ argument) so conclusion is true.

🔗

The conclusion of

{(n - 1)}^{th}

argument is

P (n),

P (n)

is true.

🔗

Now, here is some specific terminology associated to proofs by induction.

base case: 🔗
the statement $P (1)$ in a proof by mathematical induction
induction step: 🔗
the portion of a proof by mathematical induction that establishes the statement $(\forall k) (P (k) \to P (k + 1))$
induction hypothesis: 🔗
the assumption $P (k)$ made as the first step in the induction step of a proof by mathematical induction

🔗

Procedure 7.1.2. Proof by induction.

🔗

To prove a universal statement indexed by whole numbers:

🔗

Base case.

🔗

Start by proving the statement obtained from the universally quantified predicate for the base case

n = 1 .

🔗

Induction step.

🔗

Next, assume that

k

is a fixed number such that

k \geq 1,

and that the statement obtained from the universally quantified predicate is true for

n = k .

Based on this assumption, try to prove that the next case,

n = k + 1,

is also true.

🔗

Worked Example 7.1.3.

🔗

Prove that the sum of the first

n

positive integers is

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

Solution.

We want to prove

(\forall n) P (n),

where

P (n)

is as follows.

\begin{matrix} P (1) : 1 = \frac{1 \cdot 2}{2}, P (2) : 1 + 2 = \frac{2 \cdot 3}{2}, P (3) : 1 + 2 + 3 = \frac{3 \cdot 4}{2}, \\ \dots, P (n) : 1 + 2 + \dots + n = \frac{n (n + 1)}{2}, \dots \end{matrix}

We will prove this by induction.

Base case.

1 = (1 \cdot 2) / 2

is obviously true.

Induction step.

Assume the statement is true for

n = k;

i.e. assume that

1 + 2 + \dots + k = k (k + 1) / 2 .

We want to show that this implies the statement is true for

n = k + 1;

i.e. show

1 + 2 + \dots + k + (k + 1) = (k + 1) (k + 2) / 2 .

We have

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

🔗

Worked Example 7.1.4.

🔗

Prove that

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

is always divisible by

9

for every

n \geq 1 .

Solution.

We want to prove

(\forall n) P (n),

where

P (n)

is as follows.

\begin{aligned} P (1) & : 1^{3} + 2^{3} + 3^{3} is divisible by 9 \\ P (2) & : 2^{3} + 3^{3} + 4^{3} is divisible by 9 \\ P (3) & : 3^{3} + 4^{3} + 5^{3} is divisible by 9 \\ ⋮ \\ P (n) & : n^{3} + (n + 1)^{3} + (n + 2)^{3} is divisible by 9 \\ ⋮ \end{aligned}

We will prove this by induction.

Base case.

For

n = 1,

n^{3} + (n + 1)^{3} + (n + 2)^{3} = 36 = 9 \cdot 4 .

Induction step.

Assume

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

is divisible by

9 .

This means that there exists some whole number

m

so that

k^{3} + (k + 1)^{3} + (k + 2)^{3} = 9 m .

We want to show that

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

is also divisible by

9 .

To make the connection between this sum of cubes and the “previous case” sum of cubes above, we can add in (and simultaneously subtract out) a

k^{3}

term:

\begin{aligned} (k + 1)^{3} + (k + 2)^{3} + (k + 3)^{3} & = (k^{3} + (k + 1)^{3} + (k + 2)^{3}) + (k + 3)^{3} - k^{3} \\ = 9 m + (k + 3)^{3} - k^{3} \\ = 9 m + (k^{3} + 9 k^{2} + 27 k + 27) - k^{3} \\ = 9 (m + k^{2} + 3 k + 3) . \end{aligned}

Since we have factored our sum of cubes into a product involving

9,

that sum of cubes is divisible by

9 .

🔗

Worked Example 7.1.5.

🔗

Prove that

3^{3 n} + 1

is divisible by

7

whenever

n

is odd.

Solution.

We do not want to use

n

as our induction index, since it jumps by twos. But

n

odd means that

n = 2 m - 1

for some

m \geq 1,

so we want to prove

(\forall m) P (m),

where

P (m)

is as follows.

\begin{aligned} P (1) & : 3^{3} + 1 is divisible by 7 \\ P (2) & : 3^{9} + 1 is divisible by 7 \\ P (3) & : 3^{15} + 1 is divisible by 7 \\ ⋮ \\ P (m) & : 3^{6 m - 3} + 1 is divisible by 7 \\ ⋮ \end{aligned}

We will prove this by induction.

Base case.

For

m = 1,

3^{3} + 1 = 28 = 7 \cdot 4 .

Induction step.

Assume

3^{6 k - 3} + 1

is divisible by

7 .

This means that there exists some whole number

ℓ

so that

3^{6 k - 3} + 1 = 7 ℓ .

We want to show

3^{6 (k + 1) - 3} + 1

is divisible by

7 .

We have

\begin{aligned} 3^{6 (k + 1) - 3} + 1 & = (3^{6 k - 3}) (3^{6}) + 1 \\ = (3^{6 k - 3} + 1 - 1) (3^{6}) + 1 \\ = (3^{6 k - 3} + 1) (3^{6}) - 3^{6} + 1 \\ = (7 ℓ) (3^{6}) - 728 \\ = 7 (3^{6} ℓ - 104) . \end{aligned}

Since we have our expression factored into a product involving

7,

our expression is divisible by

7

as desired.

🔗

Remark 7.1.6.

🔗

Indexing of statements does not have to start at

1 .

🔗

Worked Example 7.1.7.

🔗

Prove

2^{n} < n!

whenever

n \geq 4 .

Solution.

Base case.

For

n = 4,

2^{4} = 16

and

4! = 24 .

Induction step.

Assume

2^{k} < k!

for some

k \geq 4 .

We want to show

2^{k + 1} < (k + 1)! .

We have

2^{k + 1} = 2 (2^{k}) < 2 (k!) < (k + 1) (k!) = (k + 1)! .

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 7.1 Principle of Mathematical Induction

Axiom 7.1.1. Principle of Mathematical Induction.

Idea.

Procedure 7.1.2. Proof by induction.

Base case.

Induction step.

Worked Example 7.1.3.

Base case.

Induction step.

Worked Example 7.1.4.

Base case.

Induction step.

Worked Example 7.1.5.

Base case.

Induction step.

Remark 7.1.6.

Worked Example 7.1.7.

Base case.

Induction step.