Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

11.4 Mathematical Induction

Prove infinite sequences of statements using mathematical induction.

In this section, we learn to prove a sequence of mathematical statements using a procedure called mathematical induction.

Proving Infinite Sequences of Statements

Infinite sequences of statements occur often in mathematics. In an infinite sequence of statements, there is a statement for each natural number. For example, consider the sequence of statements represented by the following:

“The sum of the first n positive odd integers is $n^{2}$ $n^{2}$ ,” or $1 + 3 + 5 + \dots + (2 n - 1) = n^{2}$ $1 + 3 + 5 + \dots + (2 n - 1) = n^{2}$ .

Let’s think of this as $S (n)$ $S (n)$ , or $S_{n}$ $S_{n}$ . Substituting natural numbers for n gives a sequence of statements. We list the first four:

$S_{1} : 1 = 1^{2};$ $S_{1} : 1 = 1^{2};$
$S_{2} : 1 + 3 = 4 = 2^{2};$ $S_{2} : 1 + 3 = 4 = 2^{2};$
$S_{3} : 1 + 3 + 5 = 9 = 3^{2};$ $S_{3} : 1 + 3 + 5 = 9 = 3^{2};$
$S_{4} : 1 + 3 + 5 + 7 = 16 = 4^{2} .$ $S_{4} : 1 + 3 + 5 + 7 = 16 = 4^{2} .$

The fact that the statement is true for $n = 1, 2, 3$ $n = 1, 2, 3$ , and 4 might tempt us to conclude that the statement is true for any natural number n, but we cannot be sure that this is the case. We can, however, use the principle of mathematical induction to prove that the statement is true for all natural numbers.

Mathematical induction is analogous to lining up a sequence of dominoes. The induction step tells us that if any one domino is knocked over, then the one next to it will be hit and knocked over. The basis step tells us that the first domino can indeed be knocked over. Note that in order for all dominoes to fall, both conditions must be satisfied.

Example 1

Prove: For every natural number n,

1 + 3 + 5 + \dots + (2 n - 1) = n^{2} .

$1 + 3 + 5 + \dots + (2 n - 1) = n^{2} .$

Proof. We first write out $S_{n}, S_{1}, S_{k}$ $S_{n}, S_{1}, S_{k}$ , and $S_{k + 1}$ $S_{k + 1}$ .

$S_{n} :$ $S_{n} :$	$1 + 3 + 5 + \dots + (2 n - 1) = n^{2}$ $1 + 3 + 5 + \dots + (2 n - 1) = n^{2}$
$S_{1} :$ $S_{1} :$	$1 = 1^{2}$ $1 = 1^{2}$
$S_{k} :$ $S_{k} :$	$1 + 3 + 5 + \dots + (2 k - 1) = k^{2}$ $1 + 3 + 5 + \dots + (2 k - 1) = k^{2}$
$S_{k + 1} :$ $S_{k + 1} :$	$1 + 3 + 5 + \dots + (2 k - 1) + [2 (k + 1) - 1] = {(k + 1)}^{2}$ $1 + 3 + 5 + \dots + (2 k - 1) + [2 (k + 1) - 1] = {(k + 1)}^{2}$

Basis step. $S_{1}$ $S_{1}$ , as listed, is true since $1 = 1^{2}$ $1 = 1^{2}$ , or $1 = 1$ $1 = 1$ .
Induction step. We let k be any natural number. We assume $S_{k}$ $S_{k}$ to be true and try to show that it implies that $S_{k + 1}$ $S_{k + 1}$ is true. Now $S_{k}$ $S_{k}$ is

$1 + 3 + 5 + \dots + (2 k - 1) = k^{2} .$ $1 + 3 + 5 + \dots + (2 k - 1) = k^{2} .$

Starting with the left side of $S_{k + 1}$ $S_{k + 1}$ and substituting $k^{2}$ $k^{2}$ for $1 + 3 +$ $1 + 3 +$ $5 + \dots + (2 k - 1)$ $5 + \dots + (2 k - 1)$ , we have

We have shown that for all natural numbers k, $S_{k} \to S_{k + 1}$ $S_{k} \to S_{k + 1}$ . This completes the induction step. It and the basis step tell us that the proof is complete.

Now Try Exercise 5.

Example 2

Prove: For every natural number n,

\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{2^{n}} = \frac{2^{n} - 1}{2^{n}} .

$\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{2^{n}} = \frac{2^{n} - 1}{2^{n}} .$

Proof.

We first list $S_{n}, S_{1}, S_{k}$ $S_{n}, S_{1}, S_{k}$ , and $S_{k + 1}$ $S_{k + 1}$ .

$S_{n} :$ $S_{n} :$	$\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{2^{n}} = \frac{2^{n} - 1}{2^{n}}$ $\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{2^{n}} = \frac{2^{n} - 1}{2^{n}}$
$S_{1} :$ $S_{1} :$	$\frac{1}{2^{1}} = \frac{2^{1} - 1}{2^{1}}$ $\frac{1}{2^{1}} = \frac{2^{1} - 1}{2^{1}}$
$S_{k} :$ $S_{k} :$	$\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{2^{k}} = \frac{2^{k} - 1}{2^{k}}$ $\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{2^{k}} = \frac{2^{k} - 1}{2^{k}}$
$S_{k + 1} :$ $S_{k + 1} :$	$\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{2^{k}} + \frac{1}{2^{k + 1}} = \frac{2^{k + 1} - 1}{2^{k + 1}}$ $\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{2^{k}} + \frac{1}{2^{k + 1}} = \frac{2^{k + 1} - 1}{2^{k + 1}}$

Basis step. We show $S_{1}$ $S_{1}$ to be true as follows:

$\frac{2^{1} - 1}{2^{1}} = \frac{2 - 1}{2} = \frac{1}{2} .$ $\frac{2^{1} - 1}{2^{1}} = \frac{2 - 1}{2} = \frac{1}{2} .$
Induction step. We let k be any natural number. We assume $S_{k}$ $S_{k}$ to be true and try to show that it implies that $S_{k + 1}$ $S_{k + 1}$ is true. Now $S_{k}$ $S_{k}$ is

$\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{2^{k}} = \frac{2^{k} - 1}{2^{k}} .$ $\frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{2^{k}} = \frac{2^{k} - 1}{2^{k}} .$

We start with the left side of $S_{k + 1}$ $S_{k + 1}$ . Since we assume that $S_{k}$ $S_{k}$ is true, we can substitute

$\frac{2^{k} - 1}{2^{k}} for \frac{1}{2} + \frac{1}{4} + \dots + 12^{k} .$ $\frac{2^{k} - 1}{2^{k}} for \frac{1}{2} + \frac{1}{4} + \dots + 12^{k} .$

We have

We have shown that for all natural numbers k, $S_{k} \to S_{k + 1}$ $S_{k} \to S_{k + 1}$ . This completes the induction step. It and the basis step tell us that the proof is complete.

Now Try Exercise 15.

Example 3

Prove: For every natural number n, $n < 2^{n}$ $n < 2^{n}$ .

Proof. We first list $S_{n}, S_{1}, S_{k}$ $S_{n}, S_{1}, S_{k}$ , and $S_{k + 1}$ $S_{k + 1}$ .

$S_{n} :$ $S_{n} :$	$n < 2^{n}$ $n < 2^{n}$
$S_{1} :$ $S_{1} :$	$1 < 2^{1}$ $1 < 2^{1}$
$S_{k} :$ $S_{k} :$	$k < 2^{k}$ $k < 2^{k}$
$S_{k + 1} :$ $S_{k + 1} :$	$k + 1 < 2^{k + 1}$ $k + 1 < 2^{k + 1}$

Basis step. $S_{1}$ $S_{1}$ , as listed, is true since $2^{1} = 2$ $2^{1} = 2$ and $1 < 2$ $1 < 2$ .
Induction step. We let k be any natural number. We assume $S_{k}$ $S_{k}$ to be true and try to show that it implies that $S_{k + 1}$ $S_{k + 1}$ is true. Now

$\begin{array}{rcll} k & < & 2^{k} & This is S_{k} . \\ 2 k & < & 2 \cdot 2^{k} & Multiplying by 2 on both sides \\ 2 k & < & 2^{k + 1} & Adding exponents on the right \\ k + k & < & 2^{k + 1} . & Rewriting 2 k as k + k \end{array}$ $\begin{array}{rcll} k & < & 2^{k} & This is S_{k} . \\ 2 k & < & 2 \cdot 2^{k} & Multiplying by 2 on both sides \\ 2 k & < & 2^{k + 1} & Adding exponents on the right \\ k + k & < & 2^{k + 1} . & Rewriting 2 k as k + k \end{array}$

Since k is any natural number, we know that $1 \leq k$ $1 \leq k$ . Thus,

$\begin{array}{l} k + 1 \leq k + k . & Adding k on both sides of 1 \leq k \end{array}$ $\begin{array}{l} k + 1 \leq k + k . & Adding k on both sides of 1 \leq k \end{array}$

Putting the results $k + 1 \leq k + k$ $k + 1 \leq k + k$ and $k + k < 2^{k + 1}$ $k + k < 2^{k + 1}$ together gives us

$\begin{array}{l} k + 1 < 2^{k + 1} . & This is S_{k + 1} . \end{array}$ $\begin{array}{l} k + 1 < 2^{k + 1} . & This is S_{k + 1} . \end{array}$

We have shown that for all natural numbers $k, S_{k} \to S_{k + 1}$ $k, S_{k} \to S_{k + 1}$ . This completes the induction step. It and the basis step tell us that the proof is complete.

Now Try Exercise 11.

11.4 Exercise Set

List the first five statements in the sequence that can be obtained from each of the following. Determine whether each of the five statements is true or false.

1. $n^{2} < n^{3}$ $n^{2} < n^{3}$
2. $n^{2} - n + 41$ $n^{2} - n + 41$ is prime. Find a value for n for which the statement is false.
3. A polygon of n sides has $[n (n - 3)] / 2$ $[n (n - 3)] / 2$ diagonals.
4. The sum of the angles of a polygon of n sides is $(n - 2) \cdot 180 °$ $(n - 2) \cdot 180 °$ .

Use mathematical induction to prove each of the following.

5. $2 + 4 + 6 + \dots + 2 n = n (n + 1)$ $2 + 4 + 6 + \dots + 2 n = n (n + 1)$
6. $4 + 8 + 12 + \dots + 4 n = 2 n (n + 1)$ $4 + 8 + 12 + \dots + 4 n = 2 n (n + 1)$
7. $1 + 5 + 9 + \dots + (4 n - 3) = n (2 n - 1)$ $1 + 5 + 9 + \dots + (4 n - 3) = n (2 n - 1)$
11. $3 + 6 + 9 + \dots + 3 n = \frac{3 n (n + 1)}{2}$ $3 + 6 + 9 + \dots + 3 n = \frac{3 n (n + 1)}{2}$
9. $2 + 4 + 8 + \dots + 2^{n} = 2 (2^{n} - 1)$ $2 + 4 + 8 + \dots + 2^{n} = 2 (2^{n} - 1)$
10. $2 \leq 2^{n}$ $2 \leq 2^{n}$
11. $n < n + 1$ $n < n + 1$
12. $3^{n} < 3^{n + 1}$ $3^{n} < 3^{n + 1}$
13. $2 n \leq 2^{n}$ $2 n \leq 2^{n}$
14. $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \dots + \frac{1}{n (n + 1)} = \frac{n}{n + 1}$ $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \dots + \frac{1}{n (n + 1)} = \frac{n}{n + 1}$
15. $\frac{1}{1 \cdot 2 \cdot 3} + \frac{1}{2 \cdot 3 \cdot 4} + \frac{1}{3 \cdot 4 \cdot 5} + \dots + \frac{1}{n (n + 1) (n + 2)} = \frac{n (n + 3)}{4 (n + 1) (n + 2)}$ $\frac{1}{1 \cdot 2 \cdot 3} + \frac{1}{2 \cdot 3 \cdot 4} + \frac{1}{3 \cdot 4 \cdot 5} + \dots + \frac{1}{n (n + 1) (n + 2)} = \frac{n (n + 3)}{4 (n + 1) (n + 2)}$
16. If x is any real number greater than 1, then for any natural number $n, x \leq x^{n}$ $n, x \leq x^{n}$ .

The following formulas can be used to find sums of powers of natural numbers. Use mathematical induction to prove each formula.

17. $1 + 2 + 3 + \dots + n = \frac{n (n + 1)}{2}$ $1 + 2 + 3 + \dots + n = \frac{n (n + 1)}{2}$
18. $1^{2} + 2^{2} + 3^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6}$ $1^{2} + 2^{2} + 3^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6}$
19. $1^{3} + 2^{3} + 3^{3} + \dots + n^{3} = \frac{n^{2} {(n + 1)}^{2}}{4}$ $1^{3} + 2^{3} + 3^{3} + \dots + n^{3} = \frac{n^{2} {(n + 1)}^{2}}{4}$
20. $\begin{array}{l} 1^{4} + 2^{4} + 3^{4} + \dots + n^{4} = \frac{n (n + 1) (2 n + 1) (3 n^{2} + 3 n - 1)}{30} \end{array}$ $\begin{array}{l} 1^{4} + 2^{4} + 3^{4} + \dots + n^{4} = \frac{n (n + 1) (2 n + 1) (3 n^{2} + 3 n - 1)}{30} \end{array}$

Use mathematical induction to prove each of the following.

21. $\sum_{i = 1}^{n} i (i + 1) = \frac{n (n + 1) (n + 2)}{3}$ $\sum_{i = 1}^{n} i (i + 1) = \frac{n (n + 1) (n + 2)}{3}$
22. $(1 + \frac{1}{1}) (1 + \frac{1}{2}) (1 + \frac{1}{3}) \dots (1 + \frac{1}{n}) = n + 1$ $(1 + \frac{1}{1}) (1 + \frac{1}{2}) (1 + \frac{1}{3}) \dots (1 + \frac{1}{n}) = n + 1$
23. The sum of n terms of an arithmetic sequence:

$\begin{array}{l} a_{1} + (a_{1} + d) + (a_{1} + 2 d) + \dots + [a_{1} + (n - 1) d] = \frac{n}{2} [2 a_{1} + (n - 1) d] \end{array}$ $\begin{array}{l} a_{1} + (a_{1} + d) + (a_{1} + 2 d) + \dots + [a_{1} + (n - 1) d] = \frac{n}{2} [2 a_{1} + (n - 1) d] \end{array}$

Skill Maintenance

Solve.

24. $\begin{array}{l} 2 x - 3 y = 1, \\ 3 x - 4 y = 3 \end{array}$ $\begin{array}{l} 2 x - 3 y = 1, \\ 3 x - 4 y = 3 \end{array}$ [9.1], [9.3], [9.5], [9.6]
25. Investment. Clarise received $104 in simple interest one year from three investments. Part is invested at 1.5%, part at 2%, and part at 3%. The amount invested at 2% is twice the amount invested at 1.5%. There is $400 more invested at 3% than at 2%. Find the amount invested at each rate. [9.2], [9.3], [9.5], [9.6]

Synthesis

Use mathematical induction to prove each of the following.

26. The sum of n terms of a geometric sequence:

$a_{1} + a_{1} r + a_{1} r^{2} + \dots + a_{1} r^{n - 1} = \frac{a_{1} - a_{1} r^{n}}{1 - r}$ $a_{1} + a_{1} r + a_{1} r^{2} + \dots + a_{1} r^{n - 1} = \frac{a_{1} - a_{1} r^{n}}{1 - r}$
27. $x + y$ $x + y$ is a factor of $x^{2 n} - y^{2 n}$ $x^{2 n} - y^{2 n}$ .

Prove each of the following using mathematical induction. Do the basis step for $n = 2$ $n = 2$ .

28. For every natural number $n \geq 2$ $n \geq 2$ ,

$2 n + 1 < 3^{n} .$ $2 n + 1 < 3^{n} .$
29. For every natural number $n \geq 2$ $n \geq 2$ ,

$\begin{array}{l} \log_{a} (b_{1} b_{2} \dots b_{n}) = \log_{a} b_{1} + \log_{a} b_{2} + \dots + \log_{a} b_{n} . \end{array}$ $\begin{array}{l} \log_{a} (b_{1} b_{2} \dots b_{n}) = \log_{a} b_{1} + \log_{a} b_{2} + \dots + \log_{a} b_{n} . \end{array}$

Prove each of the following for any complex numbers $z_{1}$ $z_{1}$ , $z_{2}, \dots, z_{n}$ $z_{2}, \dots, z_{n}$ , where $i^{2} = - 1$ $i^{2} = - 1$ and $\bar{z}$ $\bar{z}$ is the conjugate of z.

30. $\bar{z^{n}} = {\bar{z}}^{n}$ $\bar{z^{n}} = {\bar{z}}^{n}$
31. $\bar{z_{1} + z_{2} + \dots + z_{n}} = \bar{z_{1}} + \bar{z_{2}} + \dots + \bar{z_{n}}$ $\bar{z_{1} + z_{2} + \dots + z_{n}} = \bar{z_{1}} + \bar{z_{2}} + \dots + \bar{z_{n}}$
32. The Tower of Hanoi Problem. There are three pegs on a board. On one peg are n disks, each smaller than the one on which it rests. The problem is to move this pile of disks to another peg. The final order must be the same, but you can move only one disk at a time and can never place a larger disk on a smaller one.
1. What is the fewest number of moves needed to move 3 disks? 4 disks? 2 disks? 1 disk?
2. Conjecture a formula for the fewest number of moves needed to move n disks. Prove it by mathematical induction.

Mid-Chapter Mixed Review

Determine whether the statement is true or false.

The general term of the sequence 1, −2, 3, −4, … can be expressed as $a_{n} = n$ $a_{n} = n$ . [11.1]
To find the common difference of an arithmetic sequence, choose any term except the first and then subtract the preceding term from it. [11.2]
The sequence 7, 3, −1, −5,… is geometric. [11.2], [11.3]
If we can show that $S_{k} \to S_{k + 1}$ $S_{k} \to S_{k + 1}$ for some natural number k, then we know that $S_{n}$ $S_{n}$ is true for all natural numbers n. [11.4]

In each of the following, the nth term of a sequence is given. Find the first 4 terms, $a_{9}$ $a_{9}$ , and $a_{14}$ $a_{14}$ . [11.1]

$a_{n} = 3 n + 5$ $a_{n} = 3 n + 5$
$a_{n} = {(- 1)}^{n + 1} (n - 1)$ $a_{n} = {(- 1)}^{n + 1} (n - 1)$

Predict the general term, or nth term, $a_{n}$ $a_{n}$ , of the sequence. Answers may vary. [11.1]

3, 6, 9, 12, 15, …
−1, 4, −9, 16, −25,…
Find the partial sum $S_{4}$ $S_{4}$ for the sequence $1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16} \dots$ $1, \frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16} \dots$ . [11.1]
Find and evaluate the sum $\sum_{k = 1}^{5} k (k + 1)$ $\sum_{k = 1}^{5} k (k + 1)$ . [11.1]
Write sigma notation for the sum $- 4 + 8 - 12 + 16 - 20 + \dots$ $- 4 + 8 - 12 + 16 - 20 + \dots$ . [11.1]
Find the first 4 terms of the sequence defined by $a_{1} = 2, a_{n + 1} = 4 a_{n} - 2$ $a_{1} = 2, a_{n + 1} = 4 a_{n} - 2$ . [11.1]
Find the common difference of the arithmetic sequence 12, 7, 2, −3, …. [11.2]
Find the 10th term of the arithmetic sequence 4, 6, 8, 10, …. [11.2]
In the sequence in Exercise 14, what term is the number 44? [11.2]
Find the sum of the first 16 terms of the arithmetic series $6 + 11 + 16 + 21 + \dots$ $6 + 11 + 16 + 21 + \dots$ . [11.2]
Find the common ratio of the geometric sequence 16, −8, 4, −2, 1,…. [11.3]
Find (a) the 8th term and (b) the sum of the first 10 terms of the geometric sequence $\frac{1}{16}, \frac{1}{8}, \frac{1}{4}, \frac{1}{2}, 1, \dots$ $\frac{1}{16}, \frac{1}{8}, \frac{1}{4}, \frac{1}{2}, 1, \dots$ . [11.3]

Find the sum, if it exists. [11.3]

$- 8 + 4 - 2 + 1 - \dots$ $- 8 + 4 - 2 + 1 - \dots$
$\sum_{k = 0}^{\infty} 5^{k}$ $\sum_{k = 0}^{\infty} 5^{k}$
Landscaping. A landscaper is planting a triangular flower bed with 36 plants in the first row, 30 plants in the second row, 24 in the third row, and so on, for a total of 6 rows. How many plants will be planted in all? [11.2]
Amount of an Annuity. To save money for adding a bedroom to their home, at the end of each of 4 years the Davidsons deposit $1500 in an account that pays 4% interest, compounded annually. Find the total amount of the annuity. [11.3]
Prove: For every natural number n,

$1 + 4 + 7 + \dots + (3 n - 2) = \frac{1}{2} n (3 n - 1)$ $1 + 4 + 7 + \dots + (3 n - 2) = \frac{1}{2} n (3 n - 1)$ . [11.4]

Collaborative Discussion and Writing

The sum of the first n terms of an arithmetic sequence can be given by

$S_{n} = \frac{n}{2} [2 a_{1} + (n - 1) d] .$ $S_{n} = \frac{n}{2} [2 a_{1} + (n - 1) d] .$

Compare this formula to

$S_{n} = \frac{n}{2} (a_{1} + a_{n}) .$ $S_{n} = \frac{n}{2} (a_{1} + a_{n}) .$

Discuss the reasons for the use of one formula over the other. [11.2]
It is said that as a young child, the mathematician Karl F. Gauss (1777–1855) was able to compute the sum $1 + 2 + 3 + \dots + 100$ $1 + 2 + 3 + \dots + 100$ very quickly in his head to the amazement of a teacher. Explain how Gauss might have done this had he possessed some knowledge of arithmetic sequences and series. Then give a formula for the sum of the first n natural numbers. [11.2]
Write a problem for a classmate to solve. Devise the problem so that a geometric series is involved and the solution is “The total amount in the bank is $900 {(1.08)}^{40}$ $900 {(1.08)}^{40}$ , or about $19,552.” [11.3]
Write an explanation of the idea behind mathematical induction for a fellow student. [11.4]

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 11.4 Mathematical Induction

Create new playlist

Sign In

Sign Up

Table of Contents for
11.4 Mathematical Induction