Precalculus by Richard Wright

Are you not my student and
has this helped you?

This book is available
to download as an epub.

My flesh and my heart may fail, but God is the strength of my heart and my portion forever. Psalms‬ ‭73‬:‭26‬ ‭NIV‬‬‬

# 10-05 Mathematical Induction

Summary: In this section, you will:

• Write a proof for a sum formula using mathematical induction.
• Prove other mathematical statements using mathematical induction.

SDA NAD Content Standards (2018): PC.7.2

Note: This assignment is long and should take two days.

The derivations for the sum of an arithmetic series and geometric series are given in lessons 10-03 and 10-04, but how do we know other sum formulas are correct? This lesson shows how to prove sum formulas and a few other mathematical statements.

Mathematical induction is a method of proving mathematical statements by showing that the statement works for the first value and then works for the next value. As long as the next value works, all the values will work and the statement is proven.

###### Mathematical Induction

To prove a formula using mathematical induction

1. Show the formula works for n = 1.
2. Assume the formula works for $$n = k$$.
3. Show the formula works for $$n = k + 1$$.

Specifically for sum formulas

1. Show $$S_1 = a_1$$.
2. Assume $$S_k$$.
3. Show $$S_{k + 1} = S_k + a_{k + 1}$$.

#### Example 1: Prove a Sum Formula

Prove $$5 + 9 + 13 + 17 + \cdots + (4n + 1) = n(2n + 3)$$.

###### Solution

The left side of the equation is terms; the right side is the sum formula.

$$\begin{matrix} 5 & + & 9 & + & 13 & + & 17 & + & \cdots & + & (4n + 1) & = & n(2n + 3) \\ a_1 & , & a_2 & , & a_3 & , & a_4 & , & & & a_n & = & S_n \end{matrix}$$

Show the formula works for n = 1 by plugging in a 1 for n. In other words, show that $$S_1 = a_1$$.

$$S_1 = 1\left(2(1)+3\right) = 5 = a_1$$

Assume the formula works for $$n = k$$. So, plug in a k for n in the sum formula.

$$S_k = k(2k + 3)$$

Show the formula works for $$S_{k + 1}$$. For sum formulas that means to show that $$S_{k + 1} = S_k + a_{k + 1}$$. This means that the sum through the next term equals the sum through the current term plus the next term.

$$\color{blue}{S_{k + 1}} = \color{purple}{S_k} + \color{red}{a_{k + 1}}$$

$$\color{blue}{(k + 1)(2(k + 1) + 3)} = \color{purple}{k(2k + 3)} + \color{red}{4(k + 1) + 1}$$

Simplify both sides and show that they are equal.

$$(k + 1)(2k + 2 + 3) = 2k^2 + 3k + 4k + 4 + 1$$

$$(k + 1)(2k + 5) = 2k^2 + 7k + 5$$

$$2k^2 + 7k + 5 = 2k^2 + 7k + 5$$

Since the formula works for the next term (k + 1), it will work for all the terms and the proof is complete.

#### Example 2: Prove a Sum Formula

Prove $$3 + 9 + 19 + 33 + \cdots + (2n^2 + 1) = \frac{n(2n^2 + 3n + 4)}{3}$$.

###### Solution

The left side of the equation is terms; the right side is the sum formula.

$$\begin{matrix} 3 & + & 9 & + & 19 & + & 33 & + & \cdots & + & (2n^2 + 1) & = & \frac{n(2n^2 + 3n + 4)}{3} \\ a_1 & , & a_2 & , & a_3 & , & a_4 & , & & & a_n & = & S_n \end{matrix}$$

Show the formula works for n = 1 by plugging in a 1 for n. In other words, show that $$S_1 = a_1$$.

$$S_1 = \frac{1\left(2(1)^2 + 3(1) + 4\right)}{3} = 3 = a_1$$

Assume the formula works for $$n = k$$. So, plug in a k for n in the sum formula.

$$S_k = \frac{k(2k^2 + 3k + 4)}{3}$$

Show the formula works for $$S_{k + 1}$$. For sum formulas that means to show that $$S_{k + 1} = S_k + a_{k + 1}$$. This means that the sum through the next term equals the sum through the current term plus the next term.

$$\color{blue}{S_{k + 1}} = \color{purple}{S_k} + \color{red}{a_{k + 1}}$$

$$\color{blue}{\frac{(k + 1)(2(k + 1)^2 + 3(k + 1) + 4)}{3}} = \color{purple}{\frac{k(2k^2 + 3k + 4)}{3} + \color{red}{2(k + 1)^2 + 1}}$$

Simplify both sides and show that they are equal.

$$\frac{(k + 1)(2(k^2 + 2k + 1) + 3(k + 1) + 4)}{3} = \frac{2k^3 + 3k^2 + 4k}{3} + 2(k^2 + 2k + 1) + 1$$

$$\frac{(k + 1)(2k^2 + 4k + 2 + 3k + 3 + 4)}{3} = \frac{2k^3 + 3k^2 + 4k}{3} + 2k^2 + 4k + 3$$

$$\frac{(k + 1)(2k^2 + 7k + 9)}{3} = \frac{2k^3 + 3k^2 + 4k}{3} + \frac{6k^2 + 12k + 9}{3}$$

$$\frac{2k^3 + 9k^2 + 16k + 9}{3} = \frac{2k^3 + 9k^2 + 16k + 9}{3}$$

Since the formula works for the next term (k + 1), it will work for all the terms and the proof is complete.

##### Try It 1

Prove $$2 + 6 + 12 + 20 + \cdots + n(n + 1) = \frac{n(n^2 + 3n + 2)}{3}$$.

###### Solution

Show your work. The final step should end with $$\frac{k^3 + 6k^2 + 11k + 6}{3}$$.

#### Example 3: Prove a Mathematical Statement

Prove $$n! ≥ 2^n$$ where $$n ≥ 4$$.

###### Solution

Start by checking $$n = 4$$ because that is the lowest value of n.

$$4! ≥ 2^4$$

$$24 ≥ 16$$

Assume the formula is valid for $$n = k$$.

$$k! ≥ 2^k$$

Show it works when $$n = k + 1$$. Do this by plugging in k + 1. Then simplify both sides so that the 2nd step is in each side. Finally compare the two sides.

$$(k + 1)! ≥ 2^{k + 1}$$

$$(k + 1)k(k - 1)(k - 2)… ≥ 2^k·2^1$$

$$(k + 1)\color{blue}{k! ≥ 2^k} · 2$$

The blue part is the assumption and is true. The black part is always true when k ≥ 4. Thus, the proof is complete.

##### Try It 2

Prove $$n^2 < 3^n$$ where $$n > 2$$.

###### Answer

$$2^2 < 3^2 \rightarrow 4 < 9$$

$$\text{Assume } k^2 < 3^k$$

$$(k + 1)^2 < 3^{k + 1}$$

$$\color{blue}{k^2} + 2k + 1 < \color{blue}{3^k} · 3^1$$

#### Example 4: Prove a Factor

Prove that 2 is a factor of $$3^n - 1$$.

###### Solution

Show that it is true when $$n = 1$$.

$$3^1 - 1 = 2$$

Assume 2 is a factor when $$n = k$$.

$$3^k - 1$$

Show that it works when $$n = k + 1$$.

$$3^{k + 1} - 1$$

The trick is to subtract and add $$3^k$$.

$$3^{k + 1} - 3^k + 3^k - 1$$

$$\left(3^{k + 1} - 3^k\right) + \left(3^k - 1\right)$$

$$\left(3^k·3^1 - 3^k\right) + \left(3^k - 1\right)$$

$$3^k \left(3 - 1\right) + \left(3^k - 1\right)$$

$$\color{blue}{2·3^k} + \color{red}{\left(3^k - 1\right)}$$

2 is a factor of the blue part and 2 is a factor of the red part from the assumption, thus 2 is a factor of the whole thing.

##### Try It 3

Prove that 3 is a factor of $$4^n - 1$$.

###### Answer

$$4^1 - 1 = 3$$

$$\text{Assume 3 is a factor of} 4^k - 1$$

$$4^{k + 1} - 1$$

$$4^{k + 1} - 4^k + 4^k - 1$$

$$\left(4^{k + 1} - 4^k\right) + \left(4^k - 1\right)$$

$$\left(4^k·4^1 - 4^k\right) + \left(4^k - 1\right)$$

$$4^k \left(4 - 1\right) + \left(4^k - 1\right)$$

$$\color{blue}{3·4^k} + \color{red}{\left(4^k - 1\right)}$$

3 is a factor of the blue part and 3 is a factor of the red part from the assumption, thus 3 is a factor of the whole thing.

##### Lesson Summary

###### Mathematical Induction

To prove a formula using mathematical induction

1. Show the formula works for n = 1.
2. Assume the formula works for $$n = k$$.
3. Show the formula works for $$n = k + 1$$.

Specifically for sum formulas

1. Show $$S_1 = a_1$$.
2. Assume $$S_k$$.
3. Show $$S_{k + 1} = S_k + a_{k + 1}$$.

Helpful videos about this lesson.

## Practice Exercises

Substitute $$k + 1$$ into the expression and simplify.

1. $$\frac{n}{n + 3}$$
2. $$\frac{n(n + 1)}{4}$$
3. Prove the sum formulas using mathematical induction.

4. $$2 + 4 + 6 + 8 + \cdots + 2n = n(n+1)$$
5. $$2 + 7 + 12 + 17 + \cdots + (5n-3) = \frac{n}{2}(5n - 1)$$
6. $$1 + 2 + 4 + 8 + \cdots + 2^{n-1} = 2^n - 1$$
7. $$1 + 2 + 3 + 4 + \cdots + n = \frac{n(n+1)}{2}$$
8. $$\displaystyle \sum_{i=1}^n i(i+1) = \frac{n(n+1)(n+2)}{3}$$
9. Prove the inequality using mathematical induction.

10. $$2^n ≥ 2n \text{ where } n ≥ 2$$
11. $$n! > 2^n \text{ where } n ≥ 4$$
12. Prove the property using mathematical induction.

13. $$(ab)^n = a^n b^n$$
14. 3 is a factor of $$n^3 + 3n^2 + 2n$$
15. 5 is a factor of $$6^n - 1$$
16. Mixed Review

17. (10-04) Is $$3(2)^{n-1}$$ geometric, arithmetic, or neither?
18. (10-04) Write the rule for the nth term of 3, 9, 27, 81, …
19. (10-03) Evaluate $$3 + 6 + 9 + 12 + 15 + \cdots + 39$$.

### Answers

1. $$\frac{k+1}{k+4}$$
2. $$\frac{k^2+3k+2}{4}$$
3. Show work and final step should have $$k^2 + 3k + 2$$
4. Show work and final step should have $$\frac{5k^2+9k+4}{2}$$
5. Show work and final step should have $$2^{k+1}-1$$
6. Show work and final step should have $$\frac{k^2+3k+2}{2}$$
7. Show work and final step should have $$\frac{k^3+6k^2+11k+6}{3}$$
8. Show work
9. Show work
10. Show work
11. Show work
12. Show work
13. geometric because it is exponential
14. $$a_n = 3^n$$
15. 273