Skip to main content

Section 6.2 The Extended Principle of Mathematical Induction

A little exploration shows that the following proposition appears to be true.

Proposition.

For each integer n with n4, n!>n4.

We would like to use mathematical induction to prove this, but the proposition has the added assumption that n4. So to do this, we use a slight modification of the Principle of Mathematical Induction called the Extended Principle of Mathematical Induction.

The Extended Principle of Mathematical Induction.

Let M be an integer. If T is a subset of Z such that

  • MT, and

  • For every kZ with kM, if kT, then (k+1)T,

then T contains all integers greater than or equal to M. That is, {nZ|nM}T.

The primary use of the Principle of Mathematical Induction is to prove statements of the form

(nZ, with nM)(P(n)),

where M is an integer and P(n) is some open sentence. (In most induction proofs, we will use a value of M that is greater than or equal to zero.) So our goal is to prove that the truth set T of the predicate P(n) contains all integers greater than or equal to M. So to verify the hypothesis of the Extended Principle of Mathematical Induction, we must

  1. Prove that MT. That is, prove that P(M) is true.

  2. Prove that for every kZ with kM, if kT, then (k+1)T. That is, prove that if P(k) is true, then P(k+1) is true.

As before, the first step is called the basis step or the initial step, and the second step is called the inductive step. This means that a proof using the Extended Principle of Mathematical Induction will have the following form:

Using the Extended Principle of Mathematical Induction.

Let M be an integer. To prove: (nZ, with nM)(P(n))

Basis step

Prove P(M).

Inductive step

Prove that for every kZ with kM, if P(k) is true, then P(k+1) is true.

We can then conclude that P(n) is true for all nZ with nM.

This is basically the same procedure as the one for using the Principle of Mathematical Induction. The only difference is that the basis step uses an integer M other than 1. For this reason, when we write a proof that uses the Extended Principle of Mathematical Induction, we often simply say we are going to use a proof by mathematical induction. We will prove Proposition 6.2 using the Extended Principle of Mathematical Induction.

Proof.

We will use a proof by mathematical induction. For this proof, we let

P(n) be “n!>2n.
We first prove that P(4) is true. Using n=4, we see that 4!=24 and 24=16. This means that 4!>24 and, hence, P(4) is true.

For the inductive step, we prove that for all kN with k4, if P(k) is true, then P(k+1) is true. So let k be a natural number greater than or equal to 4, and assume that P(k) is true. That is, assume that

(8)k!>2k.

The goal is to prove that P(k+1)/ is true or that (k+1)!>2k+1 . Multiplying both sides of inequality (8) by k+1 gives

(k+1)!>(k+1)2k, or(9)(k+1)!>(k+1)2k.

Now, k4. Thus, k+1>2, and hence (k+1)2k>22k. This means that

(10)(k+1)2k>2k+1

Inequalities (9) and (10) show that

(k+1)!>2k+1,

and this proves that if P(k) is true, then P(k+1) is true. Thus, the inductive step has been established, and so by mathematical induction, we have proved that n!>2n for each natural number n with n4.