$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 4.2: Other Forms of Mathematical Induction

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

Preview Activity $$\PageIndex{1}$$: Exploring a Proposition about Factorials

Definition

If n is a natural number, we define $$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{array} {lllrll} {0!} &= & {1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } {3!} &= & {1 \cdot 2 \cdot 3 = 6} \\ {1!} &= & {1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } {4!} &= & {1 \cdot 2 \cdot 3 \cdot 4 = 24} \\ {2!} &= & {1 \cdot 2 = 2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ } {5!} &= & {1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120}.\end{array}$

In general, we write $$n! = 1 \cdot 2 \cdot 3 \cdot\cdot\cdot (n - 1) \cdot n$$ or $$n! = n \cdot (n - 1) \cdot\cdot\cdot 2 \cdot 1$$. Notice that for any natural number $$n$$, $$n! = n \cdot (n - 1)!$$.

1. Compute the values of $$2^n$$ and $$n!$$ for each natural number $$n$$ with $$1 \le n \le 7$$.

Now let $$P(n$$ be the open sentence, "$$n! > 2^n$$."

2. Which of the statements $$P(1)$$ through $$P(1)$$ 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 \ge 4$$, $$n! > 2^n$$.

Let $$k$$ be a natural number with $$k \ge 4$$. 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}$$. Notice that if we multiply both sides of the inequality $$k! > 2^k$$ by $$(k + 1)$$, we obtain

$(k + 1) \cdot k! > (k + 1) 2^k.$

4. In the inequality in (4.2.2), explain why $$(k + 1) \cdot k! = (k + 1)!$$.

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

6. Now use the inequality in (4.2.2) and the work in steps (4) and (5) to explain why $$(k + 1)! > 2^{k + 1}$$.

PREVIEW ACTIVITY $$\PageIndex{1}$$: Prime Factors of a Natural Number

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$$. 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 Part (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?

## The Domino Theory

Mathematical induction is frequently used to prove statements of the form

$(\forall n \in \mathbb{N})(P(n)).$

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

$P(1), P(2), P(3), ...$

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 \ref{4.2.4} 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$$.

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$$, and
2. For every $$k \in \mathbb{Z}$$ with $$k \ge M$$, if $$k \in T$$, then $$(k + 1) \in T$$,

Then $$T$$ contains all integers greater than or equal to $$M$$. That is $$\{n \in \mathbb{Z} | n \ge M\} \subseteq T$$.

## Using the Extended Principle of Mathematical Induction

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

$$(\forall n \in \mathbb{Z},\ \text{with} n \ge M)(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 $$M \in T$$, That is, prove that $$P(M)$$ is true.
2. Prove that for every $$k \in \mathbb{Z}$$ with $$k \ge M$$, if $$k \in T$$, then $$(k + 1) \in T$$.Thatis, 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: $$(\forall n \in \mathbb{Z},\ \text{with} n \ge M)(P(n)).$$

Basis step: Prove $$P(M)$$.

Inductive step: Prove that for every $$k \in \mathbb{Z}$$ with $$k \ge M$$, 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},\ \text{with} n \ge M)(P(n)).$$

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 Preview Activity $$\PageIndex{1}$$ to illustrate such a proof.

Proposition 4.7

For each natural number $$n$$ with $$n \ge 4$$, $$n! > 2^n$$.

Proof

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

$$P(n)$$ be "$$n! > 2^n$$."

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

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

$k! > 2^k.$

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

$\begin{array} {rcl} {(k + 1) \cdot k!} &> & {(k + 1) \cdot 2^k, \text{ or}} \\ {(k + 1)!} &> & {(k + 1) \cdot 2^k}.\end{array}$

Now $$k \ge 4$$. Thus, $$k + 1 > 2$$, and hence $$(k + 1) \cdot 2^k > 2 \cdot 2^k$$. This means that

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

Inequalities (4.2.6) and (4.2.7) show that

$$(k + 1)! > 2^{k + 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 the Extended Principle of Mathematical Induction, $$n! > 2^n$$ for each natural number $$n$$ with $$n \ge 4$$.

Progress Check 4.8: Formulating Conjectures

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

1. For which natural numbers $$n$$ is $$3^n$$ greater than $$1 + 2^n$$?
2. For which natural numbers $$n$$ is $$2^n$$ greater than $$(n + 1)^2)? 3. For which natural numbers \(n$$ is $$(1 + \dfrac{1}{n})^n$$ less than $$n$$ ?

Add texts here. Do not delete this text first.

## 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 Preview Activity $$\PageIndex{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$$. 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$$.

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$$, and
2. For every $$k \in \mathbb{Z}$$ with $$k \ge M$$, if $$\{M, M + 1, ..., k\} \subseteq T$$, then $$(k + 1) \in T$$.

Then $$T$$ contains all integers greater than or equal to $$M$$. That is $$\{n \in \mathbb{Z} | n \ge M\} \subseteq T$$.

## Using the Second Principle of Mathematical Induction

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

$$(\forall n \in \mathbb{Z},\ \text{with} n \ge M)(P(n)),$$

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$$. To use the Second Principle of Mathematical Induction, we must

1. Prove that $$M \in T$$, That is, prove that $$P(M)$$ is true.
2. Prove that for every $$k \in \mathbb{N}$$, if $$k \ge M$$ and $$\{M, M + 1, ..., k\} \subseteq T$$, then $$(k + 1) \in T$$. That is, prove that if $$P(M)$$, $$P(M + 1)$$, ..., $$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: $$\forall n \in \mathbb{Z} \text{with} n \ge M) (P(n))$$

Basis step: Prove $$P(M)$$.

Inductive step: Let $$k \in \mathbb{Z}$$ with $$k \ge M$$. Prove that if $$P(M)$$, $$P(M + 1)$$, ..., $$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 \ge M$$.

We will use this procedure to prove the proposition suggested in Preview Activity $$\PageIndex{2}$$.

Theorem 4.9

Each natural number greater than 1 is either a prime number or is a product of prime numbers.

Proof

We will use the Second Principle of Mathematical Induction. We let $$P(n)$$ be

$$n$$ is either 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 \ge 2$$. We assume that $$P(2)$$, $$P(3)$$, ..., $$P(k)$$ are true. That is, we assume that each of the natural numbers 2, 3, ..., $$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 $$(k + 1)$$ is a prime number, then $$P(k + 1)$$ is true.

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

$$k + 1 = a \cdot b,$$ and $$1< a \le k$$ and $$1 < b \le k$$.

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$$, we conclude that $$(k + 1)$$ is a product of prime numbers. That is, we conclude that $$P(k + 1)$$ 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 \ge 2$$, 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.10 (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$$?

To help answer this question, we will let $$\mathbb{Z}^{\ast} = \{x \in \mathbb{Z} | x \ge 0\}$$, and let $$P(n)$$ be

There exist $$x, y \in \mathbb{Z}^{\ast}$$ such that $$n = 3x + 5y$$.

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$$, then $$3x + 5y \ge 3$$. 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$$.

1. Explain why $$P(2)$$, $$P(4)$$, and $$P(7)$$ are false and why $$P(3)$$ and $$P(5)$$ are true.
2. Explain why $$P(9)$$, $$P(10)$$, $$P(11)$$, and $$P(12)$$ are true.

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.

3. Let $$k \in \mathbb{N}$$. Prove that if $$P(8)$$, $$P(9)$$, ..., $$P(k)$$ are true, then $$P(k + 1)$$ is true. Hint: $$k + 1 = 3 + (k - 2)$$.

4. Prove the following proposition using mathematical induction. Use the Sec- ond Principle of Induction and have the basis step be a proof that $$P(8)$$, $$P(9)$$, and $$P(10)$$ are true. (The inductive step is part (3).)

Proposition 4.11.

For each $$n \in \mathbb{N}$$ with $$n \ge 8$$, there exist nonnegative integers $$x$$ and $$y$$ such that $$n = 3x + 5y$$.

Add texts here. Do not delete this text first.

Exercises for Section 4.2

1. Use mathematical induction to prove each of the following:

(a) For each natural number $$n$$ with $$n \ge 2$$, $$3^n > 1 + 2^n$$.
(b) For each natural number $$n$$ with $$n \ge 6$$, $$2^n > (n + 1)^2$$.
(c) For each natural number $$n$$ with $$n \ge 3$$, $$(1 + \dfrac{1}{n})^n < n$$.

2. For each natural number $$n$$ with $$n^2 < 2^n$$? Justify your conclusion.

3. For each natural number $$n$$ with $$n! > 3^n$$? Justify your conclusion.

4. (a) Verify that $$(1 - \dfrac{1}{4}) = \dfrac{3}{4}$$ and that $$(1 - \dfrac{1}{4})(1 - \dfrac{1}{9}) = \dfrac{4}{6}.$$
(b) Verify that $$(1 - \dfrac{1}{4})(1 - \dfrac{1}{9})(1 - \dfrac{1}{16}) = \dfrac{5}{8}$$ and that $$(1 - \dfrac{1}{4})(1 - \dfrac{1}{9})(1 - \dfrac{1}{16})(1 - \dfrac{1}{25}) = \dfrac{6}{10}$$.
(c) For $$n \in \mathbb{N}$$ with $$n \ge 2$$, make a conjecture about a formula for the product $$(1 - \dfrac{1}{4})(1 - \dfrac{1}{9})(1 - \dfrac{1}{16}) \cdot\cdot\cdot (1 - \dfrac{1}{n^2})$$.
(d) Based on your work in Parts (4a) and (4b), 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$$, $$8^n | (4n)!$$:

6. Let $$y = ln x$$.

(a) Determine $$\dfrac{dy}{dx}, \dfrac{d^2 y}{dx^2}, \dfrac{d^3 y}{dx^3}$$, and $$\dfrac{d^4 y}{dx^4}$$.
(b) Let $$n$$ be a natural number. Formulate a conjecture for a formula for $$\dfrac{d^n y}{dx^n}$$. 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$$? 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$$, and $$17 = 2 + 2 + 2 + 2 + 3 + 3 + 3$$.

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$$, $$9 = 2 + 2 + 5$$, and $$17 = 2 + 5 + 5 + 5$$.

10. Use mathematical induction to prove the following proposition:

Let $$x$$ be a real number with $$x > 0$$. Then for each natural number $$n$$ with $$n \ge 2$$, $$(1 + x)^n > 1 + nx$$.

Explain where the assumption that $$x > 0$$ was used in the proof.

11. Prove that for each odd natural number $$n$$ with $$n \ge 3$$,
$(1 + \dfrac{1}{2})(1 - \dfrac{1}{3})(1 + \dfrac{1}{4}) \cdot\cdot\cdot (1 + \dfrac{(-1)^n}{n}) = 1.$

12. Prove that for each natural number $$n$$,

any set. with $$n$$ elements has $$\dfrac{n(n - 1)}{2}$$ two-element subsets.

13. Prove or disprove each of the following propositions:

(a) For each $$n \in \mathbb{N}$$, $$\dfrac{1}{1 \cdot 2}. + \dfrac{1}{2 \cdot 3} + \cdot\cdot\cdot + \dfrac{1}{n(n + 1)} = \dfrac{n}{n + 1}$$.
(b) For each natural number $$n$$ with $$n \ge 3$$,
$\dfrac{1}{3 \cdot 4} + \dfrac{1}{4 \cdot 5} + \cdot\cdot\cdot + \dfrac{1}{n(n + 1)} = \dfrac{n - 2}{3n + 3}$.
(c) For each $$n \in \mathbb{N}$$, $$1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \cdot\cdot\cdot + n(n + 1) = \dfrac{n(n + 1) (n + 2)}{3}$$.

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

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

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

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

16. (a) Prove that if $$n \in \mathbb{N}$$, then there exists an odd natural number $$m$$ and a nonnegative integer $$k$$ such that $$n = 2^k m$$.
(b) For each $$n \in \mathbb{N}$$, prove that there is only one way to write n in the form described in Part (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$$.

17. Evaluation of proofs
See the instructions for Exercise (19) on page 100 from Section 3.1.

(a)

For each natural number $$n$$ with $$n \ge 2$$, $$2^n > 1 + n$$.

Proof

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

$$2^{k + 1} > 1 + (k + 1)$$.

By mathematical induction, we conclude that $$2^n > 1 + n$$.

(b)

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$$, we let $$P(n)$$ be, “There exist nonnegative integers $$x$$ and $$y$$ such that $$n = 2x + 5y$$.” Since

$\begin{array} {rclcl}{6} &= & {3 \cdot 2 + 0 \cdot 5\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 7} &= & {2+5} \\ {8} &= & {4 \cdot 2 + 0 \cdot 5\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 9} &= & {2 \cdot 2 + 1 \cdot 5} \end{array}$

We see that $$P(6)$$, $$P(7)$$, $$P(8)$$, and $$P(9)$$ are true.

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

$$k + 1 = (k - 4) + 5.$$

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

$\begin{array} {rcl} {k + 1} &= & {(2x + 5y) + 5} \\ {} &= & {2x + 5(y + 1).} \end{array}$

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 \ge 6$$, there exist nonnegative integers $$x$$ and $$y$$ such that $$n = 2x + 5y$$.

Explorations and Activities

18. 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}$$.

(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 Part (1) to determine the sum of the angles of a convex pentagon.
(c) Use the result in Part (2) to determine the sum of the angles of a convex hexagon.
(d) Let $$n$$ be a natural number with $$n \ge 3$$. Make a conjecture about the sum of the angles of a convex polygon with n sides and use mathematical induction to prove your conjecture.

19. 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 the complex number whose square is 1, that is, $$i^2 = -1$$. One version of the theorem can be stated as follows:
If $$x$$ is a real number, then for each nonnegative integer $$n$$.
$[cos x + i(sin x)]^n = cos(nx) + i(sin(nx)).$
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)$$.
(b) To get a sense of how things work, expand $$[cos x + i(sin x)]^2$$ and write the result in the form $$a + bi$$. Then use the identities from part (1) to prove that $$[cos x + i(sin x)]^2 = cos (2x) + i(sin(2x))$$.

20. (c) Use mathematical induction to prove De Moivre’s Theorem.