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

Section 8.4 Mathematical Induction

Before Starting this Section, Review

1 Natural numbers (Section P.1 , page 3)
2 Inequalities (Section 1.6 , page 144)
3 Exponents (Section P.2 , page 20)
4 Series (Section 8.1 , page 723)

Objective

1 Prove statements by mathematical induction.

Jumping to Conclusions; Good Induction Versus Bad Induction

A scientist had two large jars before him on the laboratory table. The jar on his left contained a hundred fleas; the jar on his right was empty. The scientist carefully lifted a flea from the jar on the left; placed the flea on the table between the two jars; stepped back; and said in a loud voice, “Jump!” The flea jumped and was put into the jar on the right. A second flea was carefully lifted from the jar on the left and placed on the table between the two jars. Again, the scientist stepped back and said in a loud voice, “Jump!” The flea jumped and was put into the jar on the right. In the same manner, the scientist treated each of the hundred fleas in the jar on the left, and each flea jumped as ordered. The two jars were then interchanged, and the experiment was continued with a slight difference. This time the scientist carefully lifted a flea from the jar on the left; yanked off its hind legs; placed the flea on the table between the jars; stepped back; and said in a loud voice, “Jump!” The flea did not jump and was put into the jar on the right. A second flea was carefully lifted from the jar on the left, its hind legs were yanked off, and then it was placed on the table between the two jars. Again, the scientist stepped back and said in a loud voice, “Jump!” The flea did not jump and was put into the jar on the right. In this manner, the scientist treated each of the hundred fleas in the jar on the left, and in no case did a flea jump when ordered. So the scientist recorded the following inductive statement in his notebook: “A flea, if its hind legs are yanked off, cannot hear.”

(Source: Modified from Howard Eves, Mathematical Circles.)

This, of course, is an example of truly bad reasoning. The principle of mathematical induction, demonstrated in Example 2, is the gold standard for reasoning in proving that statements about natural numbers are true.

Mathematical Induction

1 Prove statements by mathematical induction.

Suppose your boss wants you to verify that each of a thousand bags contains two specific gold coins. There is only one way to be absolutely sure: You must check every bag. That would take a very long time, but you can eventually finish the job. However, consider the problem of verifying that a statement about the natural numbers such as

12 + 22 + 32 + \dots + n 2 = n ( n + 1 ) ( 2 n + 1 ) 6

$1^{2} + 2^{2} + 3^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6}$

is true for all natural numbers n. Let’s first test the statement for several values of n by comparing the value of 12+22+32+⋯+n2 $1^{2} + 2^{2} + 3^{2} + \dots + n^{2}$ in the second column of Table 8.1 with the value of n(n+1)(2n+1)6 $\frac{n (n + 1) (2 n + 1)}{6}$ in the third column.

Table 8.1

`n`	12+22+32+⋯+n2 $1^{2} + 2^{2} + 3^{2} + \dots + n^{2}$	n(n+1)(2n+1)6 $\frac{n (n + 1) (2 n + 1)}{6}$	Equal?
1	12=1 $1^{2} = 1$	1(1+1)[2(1)+1]6=1 $\frac{1 (1 + 1) [2 (1) + 1]}{6} = 1$	Yes
2	12+22=5 $1^{2} + 2^{2} = 5$	2(2+1)[2(2)+1]6=5 $\frac{2 (2 + 1) [2 (2) + 1]}{6} = 5$	Yes
3	12+22+32=14 $1^{2} + 2^{2} + 3^{2} = 14$	3(3+1)[2(3)+1]6=14 $\frac{3 (3 + 1) [2 (3) + 1]}{6} = 14$	Yes
4	12+22+32+42=30 $1^{2} + 2^{2} + 3^{2} + 4^{2} = 30$	4(4+1)[2(4)+1]6=30 $\frac{4 (4 + 1) [2 (4) + 1]}{6} = 30$	Yes
5	12+22+32+42+52=55 $1^{2} + 2^{2} + 3^{2} + 4^{2} + 5^{2} = 55$	5(5+1)[2(5)+1]6=55 $\frac{5 (5 + 1) [2 (5) + 1]}{6} = 55$	Yes

We see that the statement is correct for the natural numbers 1, 2, 3, 4, and 5; furthermore, you can continue to verify that the statement is correct for any particular natural number n you try. But is it always correct? Clearly, we can’t check every natural number!

The principle of mathematical induction provides a method for proving that statements about natural numbers are true for all natural numbers. The principle is based on the fact that after any natural number n, there is a next-larger natural number n+1 $n + 1$ and that any specified natural number can be reached by a finite number of such steps, starting from the natural number 1.

A common physical interpretation is helpful in understanding why this principle works. Imagine an unending line of dominoes, as shown in Figure 8.6. Suppose the dominoes are arranged so that if any domino is knocked down, it will knock down the next domino behind it as well. What will happen if the first domino is knocked down? All of the dominoes will fall because

knocking down the first domino causes the second domino to be knocked down;
when the second domino is knocked down, it knocks down the third domino, and so on.

Determining the Statement Pk+1 $P_{k + 1}$ from the Statement Pk $P_{k}$

To successfully use the Principle of Mathematical Induction, you must be able to determine the statement Pk+1 $P_{k + 1}$ from a given statement Pk. $P_{k} .$ Suppose the given statement is

P k : k \geq 1;

$P_{k} : k \geq 1;$

then we have

P k + 1 : k + 1 \geq 1 Replace k with k + 1 in P k .

$\begin{aligned} P_{k + 1} : k + 1 \geq 1 & Replace k with k + 1 in P_{k} . \end{aligned}$

It is important to recognize that because Pk $P_{k}$ says “k is greater than or equal to 1,” the statement Pk+1 $P_{k + 1}$ says, “k+1 $k + 1$ is greater than or equal to 1.” That is, Pk+1 $P_{k + 1}$ asserts the same property for k+1 $k + 1$ that Pk $P_{k}$ asserts for k.

Example 1 Determining Pk+1 $P_{k + 1}$ from Pk $P_{k}$

Find the statement Pk+1 $P_{k + 1}$ from the given statement Pk. $P_{k} .$

Pk: k<2k $P_{k} : k < 2^{k}$
Pk: Sk=3k2+9 $P_{k} : S_{k} = 3 k^{2} + 9$
Pk: 1+2+22+23+⋯+2k−1=2k−1 $P_{k} : 1 + 2 + 2^{2} + 2^{3} + \dots + 2^{k - 1} = 2^{k} - 1$
Pk: 3+6+9+12+⋯+3k=3k(k+1)2 $P_{k} : 3 + 6 + 9 + 12 + \dots + 3 k = \frac{3 k (k + 1)}{2}$

Solution

Pk: k<2k, Pk+1:k+1<2k+1Replace k with k+1. $\begin{array}{l} P_{k} : k < 2^{k}, P_{k + 1} : k + 1 < 2^{k + 1} & Replace k with k + 1 . \end{array}$
Pk:Sk=3k2+9, Pk+1: Sk+1=3(k+1)2+9Replace k with k+1. $\begin{array}{l} P_{k} : S_{k} = 3 k^{2} + 9, P_{k + 1} : S_{k + 1} = 3 {(k + 1)}^{2} + 9 & Replace k with k + 1 . \end{array}$
Pk:1+2+22+23+⋯+2k−1=2k−1,Pk+1:1+2+22+23+⋯+2(k+1)−1=2k+1−1Replace k with k+1. $\begin{array}{l} P_{k} : 1 + 2 + 2^{2} + 2^{3} + \dots + 2^{k - 1} = 2^{k} - 1, \\ P_{k + 1} : 1 + 2 + 2^{2} + 2^{3} + \dots + 2^{(k + 1) - 1} = 2^{k + 1} - 1 & Replace k with k + 1 . \end{array}$
Pk:3+6+9+12+⋯+3k=3k(k+1)2,Pk+1:3+6+9+12+⋯+3(k+1)=3(k+1)[(k+1)+1]2Replace kwith k+1. $\begin{array}{l} P_{k} : 3 + 6 + 9 + 12 + \dots + 3 k = \frac{3 k (k + 1)}{2}, \\ P_{k + 1} : 3 + 6 + 9 + 12 + \dots + 3 (k + 1) = \frac{3 (k + 1) [(k + 1) + 1]}{2} & \begin{array}{l} Replace k \\ with k + 1 . \end{array} \end{array}$

Practice Problem 1

Find Pk+1 $P_{k + 1}$ for Pk: (k+3)2>k2+9. $P_{k} : {(k + 3)}^{2} > k^{2} + 9 .$

Example 2 Using Mathematical Induction

Use mathematical induction to prove that for all natural numbers n,

2 + 4 + 6 + \dots + 2 n = n (n + 1) .

$2 + 4 + 6 + \dots + 2 n = n (n + 1) .$

Solution

First, we verify that this statement is true for n=1. $n = 1 .$

Check: 2(1)2==1(1+1)2✓Replace n with 1 in the original statement. $\begin{array}{rcll} 2 (1) & = & 1 (1 + 1) & Replace n with 1 in the original statement . \\ 2 & = & 2 ✓ \end{array}$

The given statement is true for n=1, $n = 1,$ so the first condition for the principle of mathematical induction holds.

The second condition for the principle of mathematical induction requires two steps.

Step 1 Assume that the formula is true for some unspecified natural number k:

$P k : 2 + 4 + 6 + \dots + 2 k = k (k + 1) Assumed true$ $\begin{array}{l} P_{k} : 2 + 4 + 6 + \dots + 2 k = k (k + 1) & Assumed true \end{array}$
Step 2 On the basis of the assumption that Pk $P_{k}$ is true, show that Pk+1 $P_{k + 1}$ is true, which is the same as showing that

$P k + 1 : 2 + 4 + 6 + \dots + 2 (k + 1) = (k + 1) [(k + 1) + 1] Replace k with k + 1 in P k .$ $\begin{array}{l} P_{k + 1} : 2 + 4 + 6 + \dots + 2 (k + 1) = (k + 1) [(k + 1) + 1] & Replace k with \\ k + 1 in P_{k} . \end{array}$

Begin by using Pk, $P_{k},$ the statement assumed to be true. Add 2(k+1) $2 (k + 1)$ to both sides of Pk $P_{k}$ in Step 1, which again results in a true statement.

This last equation says that Pk+1 $P_{k + 1}$ is true if Pk $P_{k}$ is assumed to be true. Therefore, by the principle of mathematical induction, the statement

2 + 4 + 6 + \dots + 2 n = n (n + 1)

$2 + 4 + 6 + \dots + 2 n = n (n + 1)$

is true for every natural number n.

Practice Problem 2

Use mathematical induction to prove that for all natural numbers n,

$1 + 2 + 3 + \dots + n = n ( n + 1 ) 2 .$ $1 + 2 + 3 + \dots + n = \frac{n (n + 1)}{2} .$

Example 3 Using Mathematical Induction

Use mathematical induction to prove that

2 n > n

$2^{n} > n$

for all natural numbers n.

Solution

First, we show that the given statement is true for n=1. $n = 1 .$

21 > 1 Replace n with 1 in the original statement .

$\begin{array}{l} 2^{1} > 1 & Replace n with 1 in the original statement . \end{array}$

The inequality is true for n=1. $n = 1 .$

Next, we assume that for some unspecified natural number k,

P k : 2 k > k is true .

$P_{k} : 2^{k} > k is true .$

Then we must use Pk $P_{k}$ to prove that Pk+1 $P_{k + 1}$ is true; that is,

P k + 1 : 2 k + 1 > k + 1 .

$P_{k + 1} : 2^{k + 1} > k + 1 .$

Now by the product rule of exponents, 2k+1=2k⋅21=2k⋅2; $2^{k + 1} = 2^{k} \cdot 2^{1} = 2^{k} \cdot 2;$ so we can get some information about 2k+1 $2^{k + 1}$ by multiplying both sides of Pk: 2k>k $P_{k} : 2^{k} > k$ by 2.

2 k 2 k \cdot 2 2 k + 1 = 2 k \cdot 2 > > > k 2 \cdot k 2 k = k + k \geq k + 1 P k is assumed true . Multiply both sides by 2 . Because k \geq 1, k + k \geq k + 1 .

$\begin{array}{rcll} 2^{k} & > & k & P_{k} is assumed true . \\ 2^{k} \cdot 2 & > & 2 \cdot k & Multiply both sides by 2 . \\ 2^{k + 1} = 2^{k} \cdot 2 & > & 2 k = k + k \geq k + 1 & Because k \geq 1, k + k \geq k + 1 . \end{array}$

So, 2k+1>k+1 $2^{k + 1} > k + 1$ is true.

By the principle of mathematical induction, the statement

2 n > n

$2^{n} > n$

is true for every natural number n.

Practice Problem 3

Use mathematical induction to prove that 3n>2n $3^{n} > 2 n$ for all natural numbers n.

Section 8.4 Exercises

Concepts and Vocabulary

Mathematical induction can only be used to prove statements about the .
The first step in a mathematical induction proof that a statement Pn $P_{n}$ is true for all natural numbers n is that .
The second step in a mathematical induction proof is to assume that Pk $P_{k}$ is true for a natural number k and then show that .
The first step when using mathematical induction to prove that ∑k=1n6⋅7k=7(7k−1) $\sum_{k = 1}^{n} 6 \cdot 7^{k} = 7 (7^{k} - 1)$ is to prove .
True or False. If Pn $P_{n}$ is a statement about natural numbers and there is exactly one natural number, r for which Pr $P_{r}$ is false, then Pn $P_{n}$ is false.
True or False. The statement S about all natural numbers n, n≥4 $n \geq 4$ , can be proved true by showing that the statement Pn=Sn+3 $P_{n} = S_{n + 3}$ is true for all n≥1 $n \geq 1$ .
True or False. The statement en≥n $e^{n} \geq n$ cannot be proved by mathematical induction because e is not a natural number.
True or False. The first step in proving that 2n≠n $2 n \neq n$ for all natural numbers n is to note that 2≠1. $2 \neq 1 .$

Building Skills

In Exercises 9–12, find Pk+1 $P_{k + 1}$ from the given statement Pk. $P_{k} .$

Pk: (k+1)2−2k=k2+1 $P_{k} : {(k + 1)}^{2} - 2 k = k^{2} + 1$
Pk: (1+k)(1−k)=1−k2 $P_{k} : (1 + k) (1 - k) = 1 - k^{2}$
Pk: 2k>5k $P_{k} : 2^{k} > 5 k$
Pk: 1+3+5+⋯+(2k−1)=k2 $P_{k} : 1 + 3 + 5 + \dots + (2 k - 1) = k^{2}$

In Exercises 13–44, use mathematical induction to prove that each statement is true for all natural numbers n.

2+4+6+⋯+2n=n2+n $2 + 4 + 6 + \dots + 2 n = n^{2} + n$
1+3+5+⋯+(2n−1)=n2 $1 + 3 + 5 + \dots + (2 n - 1) = n^{2}$
4+8+12+⋯+4n=2n(n+1) $4 + 8 + 12 + \dots + 4 n = 2 n (n + 1)$
3+6+9+⋯+3n=3n(n+1)2 $3 + 6 + 9 + \dots + 3 n = \frac{3 n (n + 1)}{2}$
1+5+9+⋯+(4n−3)=n(2n−1) $1 + 5 + 9 + \dots + (4 n - 3) = n (2 n - 1)$
3+8+13+⋯+(5n−2)=n(5n+1)2 $3 + 8 + 13 + \dots + (5 n - 2) = \frac{n (5 n + 1)}{2}$
3+9+27+⋯+3n=3(3n−1)2 $3 + 9 + 27 + \dots + 3^{n} = \frac{3 (3^{n} - 1)}{2}$
5+25+125+⋯+5n=5(5n−1)4 $5 + 25 + 125 + \dots + 5^{n} = \frac{5 (5^{n} - 1)}{4}$
1⋅2+3⋅4+5⋅6+⋯+ (2n−1)(2n)=13n(n+1)(4n−1) $1 \cdot 2 + 3 \cdot 4 + 5 \cdot 6 + \dots + (2 n - 1) (2 n) = \frac{1}{3} n (n + 1) (4 n - 1)$
1⋅3+2⋅4+3⋅5+⋯+(n)(n+2)=16n(n+1)(2n+7) $1 \cdot 3 + 2 \cdot 4 + 3 \cdot 5 + \dots + (n) (n + 2) = \frac{1}{6} n (n + 1) (2 n + 7)$
11⋅2+12⋅3+13⋅4+⋯+1n(n+1)=nn+1 $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + \dots + \frac{1}{n (n + 1)} = \frac{n}{n + 1}$
12⋅4+14⋅6+16⋅8+⋯+12n(2n+2)=n4(n+1) $\frac{1}{2 \cdot 4} + \frac{1}{4 \cdot 6} + \frac{1}{6 \cdot 8} + \dots + \frac{1}{2 n (2 n + 2)} = \frac{n}{4 (n + 1)}$
2≤2n $2 \leq 2^{n}$
2n+1≤3n $2 n + 1 \leq 3^{n}$
n(n+2)<(n+1)2 $n (n + 2) < {(n + 1)}^{2}$
n≤n2 $n \leq n^{2}$
n!n=(n−1)! $\frac{n!}{n} = (n - 1)!$
n!(n+1)!=1n+1 $\frac{n!}{(n + 1)!} = \frac{1}{n + 1}$
12+22+32+⋯+n2=n(n+1)(2n+1)6 $1^{2} + 2^{2} + 3^{2} + \dots + n^{2} = \frac{n (n + 1) (2 n + 1)}{6}$
13+23+33+⋯+n3=n2(n+1)24 $1^{3} + 2^{3} + 3^{3} + \dots + n^{3} = \frac{n^{2} {(n + 1)}^{2}}{4}$
2 is a factor of n2+n. $n^{2} + n .$
2 is a factor of n3+5n. $n^{3} + 5 n .$
6 is a factor of n(n+1)(n+2). $n (n + 1) (n + 2) .$
3 is a factor of n(n+1)(n−1). $n (n + 1) (n - 1) .$
(1+a)n≥na, a>1 ${(1 + a)}^{n} \geq n a, a > 1$
(1+a)n≥1+na, a>0 ${(1 + a)}^{n} \geq 1 + n a, a > 0$
∑i=1n3⋅4i=4(4n−1) $\sum_{i = 1}^{n} 3 \cdot 4^{i} = 4 (4^{n} - 1)$
∑i=1n8⋅9i=9(9n−1) $\sum_{i = 1}^{n} 8 \cdot 9^{i} = 9 (9^{n} - 1)$
(1+11)(1+12)(1+13)(1+1n)=n+1 $(1 + \frac{1}{1}) (1 + \frac{1}{2}) (1 + \frac{1}{3}) (1 + \frac{1}{n}) = n + 1$
11–√+12–√+13–√+⋯+1n−−√≥n−−√ $\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \frac{1}{\sqrt{3}} + \dots + \frac{1}{\sqrt{n}} \geq \sqrt{n}$
(ab)n=anbn ${(a b)}^{n} = a^{n} b^{n}$
(ab)n=anbn ${(\frac{a}{b})}^{n} = \frac{a^{n}}{b^{n}}$

Applying the Concepts

Counting hugs. At a family reunion of n people (n≥2). $(n \geq 2) .$ each person hugs everyone else. Use mathematical induction to show that the number of hugs is n2−n2. $\frac{n^{2} - n}{2} .$
Winning prizes. In a contest in which n prizes are possible, a contestant can win any number of prizes (from 0 to n). Use mathematical induction to show that there are 2n $2^{n}$ possible outcomes for the sets of prizes the contestant might win.

[Hint: If n=1, $n = 1,$ there are 2(=21) $2 (= 2^{1})$ outcomes: winning 0 prizes or winning the one prize.]
Koch’s snowflake. A geometric shape called the Koch snowflake can be formed by starting with an equilateral triangle, as in the figure. Assume that each side of the triangle has length 1. On the middle part of each side, construct an equilateral triangle with sides of length 13 $\frac{1}{3}$ and erase the side of the smaller triangle that is on the side of the original triangle. Repeat this procedure for each of the smaller triangles. This process produces a figure that resembles a snowflake.
1. Find a formula for the number of sides of the nth figure. Use mathematical induction to prove that this formula is correct.
2. Find a formula for the perimeter of the nth figure. Use mathematical induction to prove that this formula is correct.
Sierpinski’s triangle. A geometric figure known as Sierpinski’s triangle is constructed by starting with an equilateral triangle as in the figure. Assume that each side of the triangle has length 1. Inside the original triangle, draw a second triangle by connecting the midpoints of the sides of the original triangle. This divides the original triangle into four identical equilateral triangles. Repeat the process by constructing equilateral triangles inside each of the three smaller blue triangles, again using the midpoints of the sides of the triangle as vertices. Continuing this process with each group of smaller triangles produces Sierpinski’s triangle. Coloring each set of smaller triangles helps in following the construction. (Be sure to count blue as well as white triangles.)
1. When a process is repeated over and over, each repetition is called an iteration. How many triangles will the fourth iteration have?
2. How many triangles will the fifth iteration have?
3. Find a formula for the number of triangles in the nth iteration. Use mathematical induction to prove that this formula is correct.
Towers of Hanoi. Three pegs are attached vertically to a horizontal board, as shown in the figure. One peg has n rings stacked on it, each ring smaller than the one below it. In a game known as the Tower of Hanoi puzzle, all of the rings must be moved to a different peg, with only one ring moved at a time, and no ring can be moved on top of a smaller ring. Determine the least number of moves that will accomplish this transfer. Use mathematical induction to prove that your answer is correct.
Exam answer sheets. An exam in which each question is answered with either “True” or “False” has n questions.
1. If every question is answered, how many answer sheets are possible
  1. If n=1 $n = 1$ ?
  2. If n=2 $n = 2$ ?
2. Find a formula for the number of possible answer sheets for an exam with n questions (for any natural number n) and use mathematical induction to prove that the formula is correct.

Beyond the Basics

In Exercises 51–59, use mathematical induction to prove each statement for all natural numbers n.

5 is a factor of 8n−3n. $8^{n} - 3^{n} .$
24 is a factor of 52n−1. $5^{2 n} - 1 .$
64 is a factor of 32n+2−8n−9. $3^{2 n + 2} - 8 n - 9 .$
64 is a factor of 9n−8n−1. $9^{n} - 8 n - 1 .$
3 is a factor of 22n+1+1. $2^{2 n + 1} + 1 .$
5 is a factor of 24n−1. $2^{4 n} - 1 .$
a−b $a - b$ is a factor of an−bn. $a^{n} - b^{n} .$

[Hint: ak+1−bk+1=a(ak−bk)+bk(a−b). $a^{k + 1} - b^{k + 1} = a (a^{k} - b^{k}) + b^{k} (a - b) .$ ]
If a=1, $a = 1,$ then 1+a+a2+⋯+an−1=an−1a−1. $1 + a + a^{2} + \dots + a^{n - 1} = \frac{a^{n} - 1}{a - 1} .$
∑k=1n+11n+k≤56 $\sum_{k = 1}^{n + 1} \frac{1}{n + k} \leq \frac{5}{6}$

Critical Thinking / Discussion / Writing

Consider the statement “2 is a factor of 4n−1 $4 n - 1$ for all natural numbers n.” Then Pk: 2 $P_{k} : 2$ is a factor of 4k−1. $4 k - 1 .$

Assume that Pk $P_{k}$ is true so that 4k−1=2m $4 k - 1 = 2 m$ for some integer m. Then

$P k + 1 = = = = = 4 (k + 1) - 1 4 k + 4 - 1 (4 k - 1) + 4 2 m + 4 2 (m + 2)$ $\begin{array}{rcl} P_{k + 1} & = & 4 (k + 1) - 1 \\ = & 4 k + 4 - 1 \\ = & (4 k - 1) + 4 \\ = & 2 m + 4 \\ = & 2 (m + 2) \end{array}$

Thus, if Pk $P_{k}$ is true, then Pk+1 $P_{k + 1}$ is also true. However, 2 is never a factor of 4n−1 $4 n - 1$ because 4n−1 $4 n - 1$ is always an odd integer. Explain why this “proof” is not valid.

Extended principle of mathematical induction. This principle states that if a statement Pn $P_{n}$ about natural numbers satisfies the two conditions

Pm $P_{m}$ is true for some natural number m,
Pk $P_{k}$ is true implies that Pk+1 $P_{k + 1}$ is also true, Then Pn $P_{n}$ is true for all natural numbers n, with n≥m. $n \geq m .$

In Exercises 61 and 62, use the extended principle of mathematical induction to prove the statement.

Prove that 2n>n2 $2^{n} > n^{2}$ for all natural numbers n, n>4. $n > 4 .$
Prove that n!>n3 $n! > n^{3}$ for all natural numbers n, n≥6. $n \geq 6 .$

Getting Ready for the Next Section

In Exercises 63–66, verify each product by using the product rules.

(x+y)2=(x+y)(x +y)=x2+2xy+y2 ${(x + y)}^{2} = (x + y) (x + y) = x^{2} + 2 x y + y^{2}$
(x+y)3=(x+y)(x +y)2=x3+3x2y+3xy2+y3 ${(x + y)}^{3} = (x + y) {(x + y)}^{2} = x^{3} + 3 x^{2} y + 3 x y^{2} + y^{3}$
(x+y)4=(x+y)(x +y)3=x4+4x3y+6x2y2+4xy3+y4 $\begin{array}{l} {(x + y)}^{4} = (x + y) {(x + y)}^{3} \\ = x^{4} + 4 x^{3} y + 6 x^{2} y^{2} + 4 x y^{3} + y^{4} \end{array}$
(x+y)5=(x+y)(x +y)4=x5+5x4y+10x3y2+10x2y3+5xy4+y5 $\begin{array}{l} {(x + y)}^{5} = (x + y) {(x + y)}^{4} \\ = x^{5} + 5 x^{4} y + 10 x^{3} y^{2} + 10 x^{2} y^{3} + 5 x y^{4} + y^{5} \end{array}$
In Exercises 63–66, what is the pattern on the exponents of x?
In Exercises 63–66, what is the pattern on the exponents of y?

From the pattern of expansions in Exercises 63–66, if we expand (x+y)n ${(x + y)}^{n}$ for a positive integer n, what is your answer to each of the following?

The sum of the exponents on x and y in each term
The number of terms in the expansion

..................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 Section 8.4 Mathematical Induction

Create new playlist

Sign In

Sign Up

Table of Contents for
Section 8.4 Mathematical Induction