EF Strong form of Mathematical Induction

Section 7.3 Strong form of Mathematical Induction

Axiom 7.3.1. Principle of Mathematical Induction (Strong Form).

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 (1) \land P (2) \land \dots \land P (k)) \to P (k + 1))$ is true,

🔗

then

(\forall n) P (n)

is true.

🔗

Idea.

🔗

The idea here is the same as for regular mathematical induction. However, in the strong form, we allow ourselves more than just the immediately preceding case to justify the current case.

🔗

If the first case

P (1)

is true, and

P (1) \to P (2),

then

P (2)

must be true as well. Now, if

P (1) \land P (2) \to P (3),

and we already have

P (1)

and

P (2)

both true, then

P (3)

must be true as well. Furthermore, if

P (1) \land P (2) \land P (3) \to P (4),

and we already have

P (1),

P (2),

and

P (3)

all true, then

P (4)

must be true as well. And so on, until we have reached

P (n),

for

n

whatever value we wish.

🔗

Procedure 7.3.2. Proof by strong induction.

🔗

Base case.

🔗

Start by proving the statement 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 is true for all

n \leq k .

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

n = k + 1,

is also true.

🔗

Worked Example 7.3.3.

🔗

Prove that each whole number greater than

1

can be factored into a product of (one or more) primes.

Solution.

Base case.

The first number greater than

1

n = 2,

and it is prime. So it can be considered a product of one prime.

Induction step.

Let

k

represent a whole number that is greater than

1 .

Assume that

2, 3, 4, \dots, k

can each be factored into primes. We want to show

k + 1

can also be factored into primes.

Break into cases.

Case $k + 1$ prime.

In this case

k + 1

is already a product of a single prime, itself.

Case $k + 1$ not prime.

k + 1

is not prime, then it has nontrivial divisors. So there exist integers

m_{1}, m_{2},

with

2 \leq m_{1}, m_{2} \leq k,

such that

k + 1 = m_{1} m_{2} .

By our induction hypothesis, each of

m_{1}, m_{2}

can be factored into a product of primes, so their product

k + 1

can as well.

🔗

Warning 7.3.4.

🔗

If your proof of the induction step requires knowing a very specific number of previous cases are true, you may need to use a variant of the strong form of mathematical induction where several base cases are first proved. For example, if, in the induction step, proving that

P (k + 1)

is true relies specifically on knowing that both

P (k - 1)

and

P (k)

are true, then this argument does not prove that

P (1) \to P (2),

and so you must prove both base cases of

P (1)

and

P (2)

explicitly.

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 7.3 Strong form of Mathematical Induction

Axiom 7.3.1. Principle of Mathematical Induction (Strong Form).

Idea.

Procedure 7.3.2. Proof by strong induction.

Base case.

Induction step.

Worked Example 7.3.3.

Base case.

Induction step.

Case $k + 1$ prime.

Case $k + 1$ not prime.

Warning 7.3.4.

Section 7.3 Strong form of Mathematical Induction

Axiom 7.3.1. Principle of Mathematical Induction (Strong Form).

Idea.

Procedure 7.3.2. Proof by strong induction.

Base case.

Induction step.

Worked Example 7.3.3.

Base case.

Induction step.

Case k+1 prime.

Case k+1 not prime.

Warning 7.3.4.

Case $k + 1$ prime.

Case $k + 1$ not prime.