Precalculus by Richard Wright

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

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.

To prove a formula using mathematical induction

- Show the formula works for
*n*= 1. - Assume the formula works for \(n = k\).
- Show the formula works for \(n = k + 1\).

Specifically for sum formulas

- Show \(S_1 = a_1\).
- Assume \(S_k\).
- Show \(S_{k + 1} = S_k + a_{k + 1}\).

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

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.

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

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.

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

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

Prove \(n! ≥ 2^n\) where \(n ≥ 4\).

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.

Prove \(n^2 < 3^n\) where \(n > 2\).

$$ 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 $$

Prove that 2 is a factor of \(3^n - 1\).

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.

Prove that 3 is a factor of \(4^n - 1\).

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

To prove a formula using mathematical induction

- Show the formula works for
*n*= 1. - Assume the formula works for \(n = k\).
- Show the formula works for \(n = k + 1\).

Specifically for sum formulas

- Show \(S_1 = a_1\).
- Assume \(S_k\).
- Show \(S_{k + 1} = S_k + a_{k + 1}\).

Helpful videos about this lesson.

- \(\frac{n}{n + 3}\)
- \(\frac{n(n + 1)}{4}\)
- \(2 + 4 + 6 + 8 + \cdots + 2n = n(n+1)\)
- \(2 + 7 + 12 + 17 + \cdots + (5n-3) = \frac{n}{2}(5n - 1)\)
- \(1 + 2 + 4 + 8 + \cdots + 2^{n-1} = 2^n - 1\)
- \(1 + 2 + 3 + 4 + \cdots + n = \frac{n(n+1)}{2}\)
- \(\displaystyle \sum_{i=1}^n i(i+1) = \frac{n(n+1)(n+2)}{3}\)
- \(2^n ≥ 2n \text{ where } n ≥ 2\)
- \(n! > 2^n \text{ where } n ≥ 4\)
- \((ab)^n = a^n b^n\)
- 3 is a factor of \(n^3 + 3n^2 + 2n\)
- 5 is a factor of \(6^n - 1\)
- (10-04) Is \(3(2)^{n-1}\) geometric, arithmetic, or neither?
- (10-04) Write the rule for the
*n*^{th}term of 3, 9, 27, 81, … - (10-03) Evaluate \(3 + 6 + 9 + 12 + 15 + \cdots + 39\).

Substitute \(k + 1\) into the expression and simplify.

Prove the sum formulas using mathematical induction.

Prove the inequality using mathematical induction.

Prove the property using mathematical induction.

Mixed Review

- \(\frac{k+1}{k+4}\)
- \(\frac{k^2+3k+2}{4}\)
- Show work and final step should have \(k^2 + 3k + 2\)
- Show work and final step should have \(\frac{5k^2+9k+4}{2}\)
- Show work and final step should have \(2^{k+1}-1\)
- Show work and final step should have \(\frac{k^2+3k+2}{2}\)
- Show work and final step should have \(\frac{k^3+6k^2+11k+6}{3}\)
- Show work
- Show work
- Show work
- Show work
- Show work
- geometric because it is exponential
- \(a_n = 3^n\)
- 273