Skip to main content

Section 4.2 Other Forms of Mathematical Induction

Beginning Activity Beginning Activity 1: Exploring a Proposition about Factorials
A4US

Definition.

If \(n\) is a natural number, we define \(\boldsymbol{n}\) factorial, denoted by \(n!\) , to be the product of the first \(n\) natural numbers. In addition, we define \(0!\) to be equal to 1.

Using this definition, we see that

\begin{align*} 0! \amp = 1 \amp 3! \amp = 1 \cdot 2 \cdot 3 = 6\\ 1! \amp =1 \amp 4! \amp = 1 \cdot 2 \cdot 3 \cdot 4 = 24\\ 2! \amp = 1 \cdot 2 = 2 \amp 5! \amp = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120\text{.} \end{align*}

In general, we write \(n! = 1 \cdot 2 \cdot 3 \cdots \left( {n - 1} \right) \cdot n\) or \(n! = n \cdot \left( {n - 1} \right) \cdots 2 \cdot 1\text{.}\) Notice that for any natural number \(n\text{,}\) \(n! = n \cdot (n-1)!\text{.}\)

1.

Compute the values of \(2^n\) and \(n!\) for each natural number \(n\) with \(1 \leq n \leq 7\text{.}\)

Now let \(P(n)\) be the open sentence, “\(n! > 2^n\text{.}\)”

2.

Which of the statements \(P(1)\) through \(P(7)\) are true?

3.

Based on the evidence so far, does the following proposition appear to be true or false? For each natural number \(n\) with \(n \geq 4\text{,}\) \(n! > 2^n\text{.}\)

Let \(k\) be a natural number with \(k \geq 4\text{.}\) Suppose that we want to prove that if \(P(k)\) is true, then \(P(k+1)\) is true. (This could be the inductive step in an induction proof.) To do this, we would be assuming that \(k! > 2^k\) and would need to prove that \((k+1)! > 2^{k+1}\text{.}\) Notice that if we multiply both sides of the inequality \(k! > 2^k\) by \((k + 1)\text{,}\) we obtain

\begin{equation} (k + 1)\cdot k! > (k + 1) 2^k\text{.}\tag{27} \end{equation}

4.

In the inequality in (27), explain why \((k + 1) \cdot k! = (k + 1)!\text{.}\)

5.

Now look at the right side of the inequality in (27) Since we are assuming that \(k \geq 4\text{,}\) we can conclude that \((k+1) > 2\text{.}\) Use this to help explain why \((k + 1)2^k > 2^{k+1}\text{.}\)

6.

Now use the inequality in (1) and the work in Exercise 4 and Exercise 5 to explain why \((k+1)! > 2^{k+1}\text{.}\)

Beginning Activity Beginning Activity 2: Prime Factors of a Natural Number
A4US

Recall that a natural number \(p\) is a prime number provided that it is greater than 1 and the only natural numbers that divide \(p\) are 1 and \(p\text{.}\) A natural number other than 1 that is not a prime number is a composite number. The number 1 is neither prime nor composite.

1.

Give examples of four natural numbers that are prime and four natural numbers that are composite.

2.

Write each of the natural numbers 20, 40, 50, and 150 as a product of prime numbers.

3.

Do you think that any composite number can be written as a product of prime numbers?

4.

Write a useful description of what it means to say that a natural number is a composite number (other than saying that it is not prime).

5.

Based on your work in Exercise 2, do you think it would be possible to use induction to prove that any composite number can be written as a product of prime numbers?

Subsection The Domino Theory

Mathematical induction is frequently used to prove statements of the form

\begin{equation} \left( {\forall n \in \mathbb{N}} \right)\left( {P( n )} \right)\text{,}\tag{28} \end{equation}

where \(P( n )\) is an open sentence. This means that we are proving that every statement in the following infinite list is true.

\begin{equation} P( 1 ),P( 2 ),P( 3 ), \ldots\tag{29} \end{equation}

The inductive step in a proof by induction is to prove that if one statement in this infinite list of statements is true, then the next statement in the list must be true. Now imagine that each statement in equation (29) is a domino in a chain of dominoes. When we prove the inductive step, we are proving that if one domino is knocked over, then it will knock over the next one in the chain. Even if the dominoes are set up so that when one falls, the next one will fall, no dominoes will fall unless we start by knocking one over. This is why we need the basis step in an induction proof. The basis step guarantees that we knock over the first domino. The inductive step, then, guarantees that all dominoes after the first one will also fall.

Now think about what would happen if instead of knocking over the first domino, we knock over the sixth domino. If we also prove the inductive step, then we would know that every domino after the sixth domino would also fall. This is the idea of the Extended Principle of Mathematical Induction. It is not necessary for the basis step to be the proof that \(P( 1 )\) is true. We can make the basis step be the proof that \(P( M )\) is true, where \(M\) is some natural number. The Extended Principle of Mathematical Induction can be generalized somewhat by allowing \(M\) to be any integer. We are still only concerned with those integers that are greater than or equal to \(M\text{.}\)

The Extended Principle of Mathematical Induction.

Let \(M\) be an integer. If \(T\) is a subset of \(\mathbb{Z}\) such that

  1. \(M \in T\text{,}\) and

  2. For every \(k \in \mathbb{Z}\) with \(k \geq M\text{,}\) if \(k \in T\text{,}\) then \(\left( {k + 1} \right) \in T\text{,}\)

then \(T\) contains all integers greater than or equal to \(M\text{.}\) That is, \(\left\{ n \in \mathbb{Z} \mid n \geq M \right\} \subseteq T\text{.}\)

Subsection Using the Extended Principle of Mathematical Induction

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

\begin{equation*} \left( {\forall n \in \mathbb{Z},\text{ with } n \geq M} \right)\left( {P( n )} \right)\!\text{,} \end{equation*}

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\text{.}\) So to verify the hypothesis of the Extended Principle of Mathematical Induction, we must

  1. Prove that \(M \in T\text{.}\) That is, prove that \(P( M )\) is true.

  2. Prove that for every \(k \in \mathbb{Z}\) with \(k \geq M\text{,}\) if \(k \in T\text{,}\) then \(\left( {k + 1} \right) \in T\text{.}\) 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: \(\left( {\forall n \in \mathbb{Z} \text{ with } n \geq M} \right) \left( {P( n )} \right)\)

Basis step:

Prove \(P( M )\text{.}\)

Inductive step:

Prove that for every \(k \in \mathbb{Z}\) with \(k \geq M\text{,}\) if \(P( k )\) is true, then \(P( {k + 1} )\) is true.

We can then conclude that \(P( n )\) is true for all \(n \in \mathbb{Z}\) with \(n \geq M\text{.}\)

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 use the work from Beginning Activity 1 to illustrate such a proof.

Proof.

We will use a proof by mathematical induction. For this proof, we let \(P( n )\) be “\(n! > 2^n\text{.}\)” We first prove that \(P( 4 )\) is true. Using \(n = 4\text{,}\) we see that \(4! = 24\) and \(2^4 = 16\text{.}\) This means that \(4! > 2^4\) and, hence, \(P\left( 4 \right)\) is true.

For the inductive step, we prove that for all \(k \in \mathbb{N}\) with \(k \geq 4\text{,}\) 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

\begin{equation} k! > 2^k\text{.}\tag{30} \end{equation}

The goal is to prove that \(P( {k + 1} )\) is true or that \(\left( {k + 1} \right)! > 2^{k + 1}\text{.}\) Multiplying both sides of inequality (30) by \(k + 1\) gives

\begin{align} \left( k + 1 \right) \cdot k! \amp > \left( k + 1 \right) \cdot 2^k ,\text{ or }\notag\\ \left( k + 1 \right)! \amp > \left( k + 1 \right) \cdot 2^k\tag{31} \end{align}

Now, \(k \geq 4\text{.}\) Thus, \(k + 1 > 2\text{,}\) and hence \(\left( k + 1 \right) \cdot 2^k > 2 \cdot 2^k\text{.}\) This means that

\begin{equation} \left( k + 1 \right) \cdot 2^k > 2^{k + 1}\text{.}\tag{32} \end{equation}

Inequalities (31) and (32) show that

\begin{equation*} (k + 1)! > 2^{k + 1}\text{,} \end{equation*}

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 the Extended Principle of Mathematical Induction, \(n! > 2^n\) for each natural number \(n\) with \(n \geq 4\text{.}\)

Progress Check 4.10. Formulating Conjectures.

Formulate a conjecture (with an appropriate quantifier) that can be used as an answer to each of the following questions.

(a)

For which natural numbers \(n\) is \(3^n\) greater than \(1 + 2^n\text{?}\)

Solution.

For each natural number \(n\text{,}\) if \(n \geq 2\text{,}\) then \(3^n > 1 + 2^n\text{.}\)

(b)

For which natural numbers \(n\) is \(2^n\) greater than \(\left(n + 1 \right)^2\text{?}\)

Solution.

For each natural number \(n\text{,}\) if \(n \geq 6\text{,}\) then \(2^n > (n + 1 )^2\text{.}\)

(c)

For which natural numbers \(n\) is \(\left( 1 + \dfrac{1}{n} \right)^n\) greater than 2.5?

Solution.

For each natural number \(n\text{,}\) if \(n \geq 6\text{,}\) then \(\left( 1 + \dfrac{1}{n} \right)^n > 2.5\text{.}\)

Subsection The Second Principle of Mathematical Induction

Let \(P( n )\) be

\(n\) is a prime number or \(n\) is a product of prime numbers.
(This is related to the work in Beginning Activity 2.)

Suppose we would like to use induction to prove that \(P( n )\) is true for all natural numbers greater than 1. We have seen that the idea of the inductive step in a proof by induction is to prove that if one statement in an infinite list of statements is true, then the next statement must also be true. The problem here is that when we factor a composite number, we do not get to the previous case. For example, if assume that \(P(39)\) is true and we want to prove that \(P(40)\) is true, we could factor 40 as \(40 = 2 \cdot 20\text{.}\) However, the assumption that \(P(39)\) is true does not help us prove that \(P(40)\) is true.

This work is intended to show the need for another principle of induction. In the inductive step of a proof by induction, we assume one statement is true and prove the next one is true. The idea of this new principle is to assume that all of the previous statements are true and use this assumption to prove the next statement is true. This is stated formally in terms of subsets of natural numbers in the Second Principle of Mathematical Induction. Rather than stating this principle in two versions, we will state the extended version of the Second Principle. In many cases, we will use \(M = 1\) or \(M = 0\text{.}\)

The Second Principle of Mathematical Induction.

Let \(M\) be an integer. If \(T\) is a subset of \(\mathbb{Z}\) such that

  1. \(M \in T\text{,}\) and

  2. For every \(k \in \mathbb{Z}\) with \(k \geq M\text{,}\) if \(\left\{ {M, M + 1, \ldots ,k} \right\} \subseteq T\text{,}\) then \(\left( {k + 1} \right) \in T\text{,}\)

then \(T\) contains all integers greater than or equal to \(M\text{.}\) That is, \(\left\{ { {n \in \mathbb{Z} } \mid n \geq M} \right\} \subseteq T\text{.}\)

Subsection Using the Second Principle of Mathematical Induction

The primary use of mathematical induction is to prove statements of the form

\begin{equation*} \left( {\forall n \in \mathbb{Z},\text{ with } n \geq M} \right)\left( {P( n )} \right)\text{,} \end{equation*}

where \(M\) is an integer and \(P( n )\) is some predicate. 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\text{.}\) To use the Second Principle of Mathematical Induction, we must

  1. Prove that \(M \in T\text{.}\) That is, prove that \(P( M )\) is true.

  2. Prove that for every \(k \in \mathbb{N}\text{,}\) if \(k \geq M\) and \(\left\{ {M,M + 1, \ldots ,k} \right\} \subseteq T\text{,}\) then \(\left( {k + 1} \right) \in T\text{.}\) That is, prove that if \(P( M ),P( {M + 1} ), \ldots ,P( k )\) are 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 Second Principle of Mathematical Induction will have the following form:

Using the Second Principle of Mathematical Induction.

Let \(M\) be an integer. To prove: \(\left( {\forall n \in \mathbb{Z} \text{ with } n \geq M} \right) \left( {P( n )} \right)\)

Basis step:

Prove \(P( M )\text{.}\)

Inductive step:

Let \(k \in \mathbb{Z}\) with \(k \geq M\text{.}\) Prove that if \(P( M ),P( {M + 1} ), \ldots ,P( k )\) are true, then \(P( {k + 1} )\) is true.

We can then conclude that \(P( n )\) is true for all \(n \in \mathbb{Z}\) with \(n \geq M\text{.}\)

We will use this procedure to prove the proposition suggested in Beginning Activity 2.

Proof.

We will use the Second Principle of Mathematical Induction. We let \(P( n )\) be \(n\) is a prime number or \(n\) is a product of prime numbers.

For the basis step, \(P ( 2 )\) is true since 2 is a prime number.

To prove the inductive step, we let \(k\) be a natural number with \(k \geq 2\text{.}\) We assume that \(P( 2 ),P( 3 ), \ldots ,P( k )\) are true. That is, we assume that each of the natural numbers \(2,3, \ldots ,k\) is a prime number or a product of prime numbers. The goal is to prove that \(P( {k + 1} )\) is true or that \((k + 1)\) is a prime number or a product of prime numbers.

Case 1: If \(\left( {k + 1} \right)\) is a prime number, then \(P( {k + 1} )\) is true.

Case 2: If \(\left( {k + 1} \right)\) is not a prime number, then \(\left( {k + 1} \right)\) can be factored into a product of natural numbers with each one being less than \(\left( {k + 1} \right)\text{.}\) That is, there exist natural numbers \(a\) and \(b\) with

\begin{equation*} k + 1 = a \cdot b, \text{ and } 1 \lt a \leq k \text{ and } 1 \lt b \leq k\text{.} \end{equation*}

Using the inductive assumption, this means that \(P( a )\) and \(P( b )\) are both true. Consequently, \(a\) and \(b\) are prime numbers or are products of prime numbers. Since \(k + 1 = a \cdot b\text{,}\) we conclude that \(\left( {k + 1} \right)\) is a product of prime numbers. That is, we conclude that \(P\left( {k + 1} \right)\) is true. This proves the inductive step.

Hence, by the Second Principle of Mathematical Induction, we conclude that \(P( n )\) is true for all \(n \in \mathbb{N}\) with \(n \geq 2\text{,}\) and this means that each natural number greater than 1 is either a prime number or is a product of prime numbers.

We will conclude this section with a progress check that is really more of an activity. We do this rather than including the activity at the end of the exercises since this activity illustrates a use of the Second Principle of Mathematical Induction in which it is convenient to have the basis step consist of the proof of more than one statement.

Progress Check 4.12. Using the Second Principle of Induction.

Consider the following question:

For which natural numbers \(n\) do there exist nonnegative integers \(x\) and \(y\) such that \(n = 3x + 5y\text{?}\)
To help answer this question, we will let \(\mathbb{Z}^* = \left\{ {x \in \mathbb{Z} \mid x \geq 0} \right\}\text{,}\) and let \(P \left( n \right)\) be There exist \(x,y \in \mathbb{Z}^*\) such that \(n = 3x + 5y\text{.}\) Notice that \(P(1)\) is false since if both \(x\) and \(y\) are zero, then \(3x + 5y = 0\) and if either \(x > 0\) or \(y > 0\text{,}\) then \(3x + 5y \geq 3\text{.}\) Also notice that \(P(6)\) is true since \(6 = 3 \cdot 2 + 5 \cdot 0\) and \(P(8)\) is true since \(8 = 3 \cdot 1 + 5 \cdot 1\text{.}\)

(a)

Explain why \(P(2)\text{,}\) \(P(4)\text{,}\) and \(P(7)\) are false and why \(P(3)\) and \(P(5)\) are true.

(b)

Explain why \(P(9)\text{,}\) \(P(10)\text{,}\) \(P(11)\text{,}\) and \(P(12)\) are true.

Solution.

Construct the following table and use it to answer the first two questions. The table shows that \(P\left( 3 \right)\text{,}\) \(P\left( 5 \right)\text{,}\) and \(P\left( 6 \right)\) are true. We can also see that \(P(2)\text{,}\) \(P(4)\text{,}\) and \(P(7)\) are false. It also appears that if \(n \in \mathbb{N}\) and \(n \geq 8\text{,}\) then \(P\left( n \right)\) is true.

\(x\) 0 1 2 3 4 0 1 2 0 1 1
\(y\) 0 0 0 0 0 1 1 1 2 3 3
\(3x + 5y\) 0 3 6 9 12 5 8 11 10 13 18

(c)

We could continue trying to determine other values of \(n\) for which \(P(n)\) is true. However, let us see if we can use the work in part (2) to determine if \(P(13)\) is true. Notice that \(13 = 3 + 10\) and we know that \(P(10)\) is true. We should be able to use this to prove that \(P(13)\) is true. This is formalized in the next part.

Let \(k \in \mathbb{N}\) with \(k \geq 10\text{.}\) Prove that if \(P( 8 )\text{,}\) \(P ( 9 )\text{,}\) \(\ldots\text{,}\) \(P( k )\) are true, then \(P( {k+1} )\) is true.

Hint.

\(k + 1 = 3 + \left( {k - 2} \right)\text{.}\)

(d)

Prove the following proposition using mathematical induction. Use the Second Principle of Induction and have the basis step be a proof that \(P(8)\text{,}\) \(P(9)\text{,}\) and \(P(10)\) are true. (The inductive step is Task 4.12.c.)

Solution.

The following proposition provides answers for Problems (3) and (4).

Proposition: For all natural numbers \(n\) with \(n \geq 8\text{,}\) there exist non-negative integers \(x\) and \(y\) such that \(n = 3x + 5y\text{.}\)

Proof.

(by mathematical induction) Let \(\mathbb{Z}^* = \left\{ {x \in \mathbb{Z}\left. \right| x \geq 0} \right\}\text{,}\) and for each natural number \(n\text{,}\) let \(P\left( n \right)\) be, “there exist \(x, y \in \mathbb{Z}^*\) such that \(n = 3x + 5y\text{.}\)”

Basis Step: Using the table above, we see that \(P\left( 8 \right)\text{,}\) \(P\left( 9 \right)\text{,}\) and \(P\left( {10} \right)\) are true.

Inductive Step: Let \(k \in \mathbb{N}\) with \(k \geq 10\text{.}\) Assume that \(P\left( 8 \right)\text{,}\) \(P\left( 9 \right)\text{,}\) … , \(P\left( k \right)\) are true. Now, notice that

\begin{equation*} k + 1 = 3 + \left( {k - 2} \right)\text{.} \end{equation*}

Since \(k \geq 10\text{,}\) we can conclude that \(k - 2 \geq 8\) and hence \(P\left( {k - 2} \right)\) is true. Therefore, there exist non-negative integers \(u\) and \(v\) such that \(k - 2 = \left( {3u + 5v} \right)\text{.}\) Using this equation, we see that

\begin{align*} k + 1 \amp = 3 + \left( {3u + 5v} \right)\\ \amp = 3\left( {1 + u} \right) + 5v\text{.} \end{align*}

Hence, we can conclude that \(P\left( {k + 1} \right)\) is true. This proves that if \(P\left( 8 \right)\text{,}\) \(P\left( 9 \right)\text{,}\) … , \(P\left( k \right)\) are true, then \(P\left( {k + 1} \right)\) is true. Hence, by the Second Principle of Mathematical Induction, for all natural numbers \(n\) with \(n \geq 8\text{,}\) there exist nonnegative integers \(x\) and \(y\) such that \(n = 3x + 5y\text{.}\)

Exercises Exercises

1.

Use mathematical induction to prove each of the following:

(a)

For each natural number \(n\) with \(n \geq 2\text{,}\) \(3^n > 1 + 2^n\text{.}\)

Answer.

Let \(P \left( n \right)\) be, “\(3^n > 1 + 2^n\text{.}\)” \(P \left( 2 \right)\) is true since \(3^2 = 9\text{,}\) \(1 + 2^2 = 5\text{,}\) and \(9 > 5\text{.}\) For the inductive step, we assume that \(P \left( k \right)\) is true and so

\begin{equation} 3^k > 1 + 2^k\text{.}\tag{33} \end{equation}

To prove that \(P(k+1)\) is true, we must prove that \(3^{k+1} > 1 + 2^{k+1}\text{.}\) Multiplying both sides inequality (33) by 3 gives

\begin{equation*} 3^{k + 1} > 3 + 3 \cdot 2^k\text{.} \end{equation*}

Now, since \(3 > 1\) and \(3 \cdot 2^k > 2^{k + 1}\text{,}\) we see that \(3 + 3 \cdot 2^k > 1 + 2^{k+1}\) and hence, \(3^{k + 1} > 1 + 2^{k+1}\text{.}\) Thus, if \(P \left( k \right)\) is true, then \(P \left( k +1 \right)\) is true. This proves the inductive step.

(b)

For each natural number \(n\) with \(n \geq 6\text{,}\) \(2^n > \left( n + 1 \right)^2\text{.}\)

(c)

For each natural number \(n\) with \(n \geq 3\text{,}\) \(\left( {1 + \dfrac{1}{n}} \right)^n \lt n\text{.}\)

2.

For which natural numbers \(n\) is \(n^2 \lt 2^n\text{?}\) Justify your conclusion.

Answer.

If \(n \geq 5\text{,}\) then \(n^2 \lt 2^n\text{.}\) To prove this, we let \(P(n)\) be \(n^2 \lt 2^n\text{.}\) For the basis step, when \(n = 5\text{,}\) \(n^2 = 25\text{,}\) \(2^n = 32\text{,}\) and \(25 \lt 32\text{.}\) For the inductive step, we assume that \(k \geq 5\) and that \(P(k)\) is true or that \(k^2 \lt 2^k\text{.}\) With these assumptions, we need to prove that \(P(k+1)\) is true or that \((k+1)^2 \lt 2^{k+1}\text{.}\) We first note that

\begin{equation} ( k + 1 )^2 = k^2 + 2k + 1 \lt 2^k + 2k + 1\text{.}\tag{34} \end{equation}

Since \(k \geq 5\text{,}\) we see that \(5k \lt k^2\) and so \(2k + 3k \lt k^2\text{.}\) However, \(3k > 1\) and so \(2k + 1 \lt 2k + 3k \lt k^2\text{.}\) Combinining this with inequality (34), we obtain \((k+1)^2 \lt 2^k+ k^2\text{.}\) Using the assumption that \(P(k)\) is true \(\left(k^2 \lt 2^k\right)\text{,}\) we obtain

\begin{align*} (k+1)^2 \amp \lt 2^k + 2^k = 2 \cdot 2^k\\ (k+1)^2 \amp \lt 2^{k+1} \end{align*}

This proves that if \(P(k)\) is true, then \(P(k+1)\) is true.

3.

For which natural numbers \(n\) is \(n! > 3^n\text{?}\) Justify your conclusion.

4.

Complete the following.

(a)

Verify that \(\left( {1 - \dfrac{1}{4}} \right) = \dfrac{3} {4}\) and that \(\left( {1 - \dfrac{1}{4}} \right)\left( {1 - \dfrac{1}{9}} \right) = \dfrac{4} {6}\text{.}\)

(b)

Verify that \(\left( {1 - \dfrac{1}{4}} \right)\left( {1 - \dfrac{1}{9}} \right) \left( {1 - \dfrac{1}{{16}}} \right) = \dfrac{5}{8}\) and that \(\left( {1 - \dfrac{1}{4}} \right)\left( {1 - \dfrac{1}{9}} \right) \left( {1 - \dfrac{1}{{16}}} \right)\left( {1 - \dfrac{1}{{25}}} \right) = \dfrac{6}{{10}}\text{.}\)

(c)

For \(n \in \mathbb{N}\) with \(n \geq 2\text{,}\) make a conjecture about a formula for the product \(\left( {1 - \dfrac{1}{4}} \right) \left( {1 - \dfrac{1}{9}} \right) \left( {1 - \dfrac{1}{{16}}} \right) \cdots \left( {1 - \dfrac{1}{{n^2 }}} \right)\text{.}\)

(d)

Based on your work in Part Task 4.a and Task 4.b, state a proposition and then use the Extended Principle of Mathematical Induction to prove your proposition.

5.

Is the following proposition true or false? Justify your conclusion.

For each nonnegative integer \(n\text{,}\) \(8^n \mid \left( {4n} \right)!\text{.}\)

Answer.

Let \(P( n )\) be the predicate, “\(8^n \mid ( 4n )!\text{.}\)” Verify that \(P( 0 ), P( 1 ), P( 2 )\text{,}\) and \(P( 3 )\) are true. For the inductive step, the following fact about factorials may be useful:

\begin{align*} [4 (k + 1) ]! \amp = ( 4k + 4 )!\\ \amp = (4k + 4)(4k + 3)(4k + 2)(4k + 1) ( 4k )!\text{.} \end{align*}

6.

Let \(y = \ln x\text{.}\)

(a)

Determine \(\dfrac{{dy}}{{dx}}\text{,}\) \(\dfrac{{d^2 y}}{{dx^2 }}\text{,}\) \(\dfrac{{d^3 y}}{{dx^3 }}\text{,}\) and \(\dfrac{{d^4 y}}{{dx^4 }}\text{.}\)

(b)

Let \(n\) be a natural number. Formulate a conjecture for a formula for \(\dfrac{{d^n y}}{{dx^n }}\text{.}\) Then use mathematical induction to prove your conjecture.

7.

For which natural numbers \(n\) do there exist nonnegative integers \(x\) and \(y\) such that \(n = 4x + 5y\text{?}\) Justify your conclusion.

8.

Can each natural number greater than or equal to 4 be written as the sum of at least two natural numbers, each of which is a 2 or a 3? Justify your conclusion. For example, \(7 = 2 + 2 + 3\text{,}\) and \(17 = 2 + 2 + 2 + 2 + 3 + 3 + 3\text{.}\)

Answer.

Let \(P( n )\) be, “The natural number \(n\) can be written as a sum of natural numbers, each of which is a 2 or a 3.” Verify that \(P( 4 ), P( 5 ), P( 6 )\text{,}\) and \(P( 7 )\) are true. To use the Second Principle of Mathematical Induction, assume that \(k \in \mathbb{N}, k \geq 5\) and that \(P( 4 ), P( 5 ), \ldots , P( k )\) are true. Then notice that

\begin{equation*} k + 1 = ( {k - 1} ) + 2\text{.} \end{equation*}

Since \(k - 1 \geq 4\text{,}\) we have assumed that \(P( {k - 1} )\) is true. This means that \((k-1)\) can be written as a sum of natural numbers, each of which is a 2 or a 3. Since \(k + 1 = (k - 1) + 2\text{,}\) we can conclude that \((k+1)\) can be written as a sum of natural numbers, each of which is a 2 or a 3. This completes the proof of the inductive step.

9.

Can each natural number greater than or equal to 6 be written as the sum of at least two natural numbers, each of which is a 2 or a 5? Justify your conclusion. For example, \(6 = 2 + 2 + 2\text{,}\) \(9 = 2 + 2 + 5\text{,}\) and \(17 = 2 + 5 + 5 + 5\text{.}\)

10.

Use mathematical induction to prove the following proposition:

Let \(x\) be a real number with \(x > 0\text{.}\) Then for each natural number \(n\) with \(n \geq 2\text{,}\) \(\left( {1 + x} \right)^n > 1 + nx\text{.}\)
Explain where the assumption that \(x > 0\) was used in the proof.

11.

Prove that for each odd natural number \(n\) with \(n \geq 3\text{,}\)

\begin{equation*} \left( {1 + \frac{1}{2}} \right) \left( {1 - \frac{1}{3}} \right) \left( {1 + \frac{1}{4}} \right) \cdots \left( {1 + \frac{{\left( { - 1} \right)^n }}{n}} \right) = 1\text{.} \end{equation*}

12.

Prove that for each natural number \(n\text{,}\) any set with \(n\) elements has \(\dfrac{n \left( {n-1} \right)}{2}\) two-element subsets.

Answer.

Let \(P ( n )\) be, “Any set with \(n\) elements has \(\dfrac{n ( n - 1 )}{2}\) 2-element subsets.” \(P ( 1 )\) is true since any set with only one element has no 2-element subsets. Let \(k \in \mathbb{N}\) and assume that \(P ( k )\) is true. This means that any set with \(k\) elements has \(\dfrac{k ( k - 1 )}{2}\) 2-element subsets. Let \(A\) be a set with \(k + 1\) elements, and let \(x \in A\text{.}\) Now use the inductive hypothesis on the set \(A - \left\{ x \right\}\text{,}\) and determine how the 2-element subsets of \(A\) are related to the set \(A - \left\{ x \right\}\text{.}\)

13.

Prove or disprove each of the following propositions:

(a)

For each \(n \in \N\text{,}\) \(\dfrac{1}{1 \cdot 2} + \dfrac{1}{2 \cdot 3} + \cdots + \dfrac{1}{n (n + 1 )} = \dfrac{n}{n+1}\text{.}\)

(b)

For each natural number \(n\) with \(n \geq 3\text{,}\)

\begin{equation*} \frac{1}{3 \cdot 4} + \frac{1}{4 \cdot 5} + \cdots + \frac{1}{n (n + 1 )} = \frac{n-2}{3n + 3}\text{.} \end{equation*}
(c)

For each \(n \in \N\text{,}\) \(1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \cdots + n (n + 1 ) = \dfrac{n (n + 1 ) (n + 2 )}{3}\text{.}\)

14.

Is the following proposition true or false? Justify your conclusion.

For each natural number \(n\text{,}\) \(\left( \dfrac{n^3}{3} + \dfrac{n^2}{2} + \dfrac{7n}{6} \right)\) is a natural number.

15.

Is the following proposition true or false? Justify your conclusion.

For each natural number \(n\text{,}\) \(\left( \dfrac{n^5}{5} + \dfrac{n^4}{2} + \dfrac{n^3}{3} - \dfrac{n}{30} \right)\) is an integer.

16.

Complete the following.

(a)

Prove that if \(n \in \N\text{,}\) then there exists an odd natural number \(m\) and a nonnegative integer \(k\) such that \(n = 2^k m\text{.}\)

Hint.

Use Theorem 4.11.

(b)

For each \(n \in \N\text{,}\) prove that there is only one way to write \(n\) in the form described in Task 16.a. To do this, assume that \(n = 2^k m\) and \(n = 2^q p\) where \(m\) and \(p\) are odd natural numbers and \(k\) and \(q\) are nonnegative integers. Then prove that \(k = q\) and \(m = p\text{.}\)

Hint.

Assume \(k \ne q\) and consider two cases: (i) \(k \lt q\text{;}\) (ii) \(k > q\text{.}\)

17. Evaluation of Proofs.

See the instructions for Exercise 19 from Section 3.1.

(a)
Proposition

For each natural number \(n\) with \(n \geq 2\text{,}\) \(2^n > 1 + n\text{.}\)

Proof

We let \(k\) be a natural number and assume that \(2^k > 1 + k\text{.}\) Multiplying both sides of this inequality by 2, we see that \(2^{k+1} > 2 + 2k\text{.}\) However, \(2 + 2k > 2 + k\) and, hence,

\begin{equation*} 2^{k+1} > 1 + \left(k + 1 \right)\!\text{.} \end{equation*}

By mathematical induction, we conclude that \(2^n > 1 + n\text{.}\)

(b)
Proposition

Each natural number greater than or equal to 6 can be written as the sum of natural numbers, each of which is a 2 or a 5.

Proof

We will use a proof by induction. For each natural number \(n\text{,}\) we let \(P( n )\) be, “There exist nonnegative integers \(x\) and \(y\) such that \(n = 2x + 5y\text{.}\)” Since

\begin{align*} 6 \amp = 3 \cdot 2 + 0 \cdot 5 \amp 7 \amp = 2 + 5\\ 8 \amp = 4 \cdot 2 + 0 \cdot 5 \amp 9 \amp = 2 \cdot 2 + 1 \cdot 5 \end{align*}

we see that \(P(6 ), P(7 ), P(8 )\text{,}\) and \(P( 9 )\) are true.

We now suppose that for some natural number \(k\) with \(k \geq 10\) that \(P(6 ), P (7 ), \ldots, P (k )\) are true. Now

\begin{equation*} k + 1 = \left(k - 4 \right) + 5\text{.} \end{equation*}

Since \(k \geq 10\text{,}\) we see that \(k - 4 \geq 6\) and, hence, \(P(k - 4 )\) is true. So \(k - 4 = 2x + 5y\) and, hence,

\begin{align*} k + 1 \amp = \left(2x + 5y \right) + 5\\ \amp = 2x + 5 \left(y + 1 \right)\! \end{align*}

This proves that \(P(k + 1 )\) is true, and hence, by the Second Principle of Mathematical Induction, we have proved that for each natural number \(n\) with \(n \geq 6\text{,}\) there exist nonnegative integers \(x\) and \(y\) such that \(n = 2x + 5y\text{.}\)

Activity 23. The Sum of the Angles of a Convex Quadrilateral.

There is a famous theorem in Euclidean geometry that states that the sum of the interior angles of a triangle is \(180^\circ\text{.}\)

(a)

Use the theorem about triangles to determine the sum of the angles of a convex quadrilateral.

Hint.

Draw a convex quadrilateral and draw a diagonal.

(b)

Use the result in Task 23.a to determine the sum of the angles of a convex pentagon.

(c)

Use the result in Task 23.b to determine the sum of the angles of a convex hexagon.

(d)

Let \(n\) be a natural number with \(n \geq 3\text{.}\) Make a conjecture about the sum of the angles of a convex polygon with \(n\) sides and use mathematical induction to prove your conjecture.

Activity 24. De Moivre's Theorem.

One of the most interesting results in trigonometry is De Moivre's Theorem, which relates the complex number \(i\) to the trigonometric functions. Recall that the number \(i\) is a complex number whose square is \(-1\text{,}\) that is, \(i^2 = -1\text{.}\) One version of the theorem can be stated as follows:

If \(x\) is a real number, then for each nonnegative integer \(n\text{,}\) \(\left[ {\cos x + i(\sin x)} \right]^n = \cos (nx) + i( {\sin (nx)} )\!\text{.}\)
This theorem is named after Abraham de Moivre (1667 — 1754), a French mathematician.

(a)

The proof of De Moivre's Theorem requires the use of the trigonometric identities for the sine and cosine of the sum of two angles. Use the Internet or a book to find identities for \(\sin( \alpha + \beta)\) and \(\cos (\alpha + \beta)\text{.}\)

(b)

To get a sense of how things work, expand \(\left[ {\cos x + i(\sin x)} \right]^2\) and write the result in the form \(a + bi\text{.}\) Then use the identities from Task 24.a to prove that \(\left[ {\cos x + i(\sin x)} \right]^2 = \cos (2x) + i( {\sin (2x)} )\text{.}\)

(c)

Use mathematical induction to prove De Moivre's Theorem.