Mathematical Induction Notes

9.4 Mathematical Induction

Learning Targets

• Use mathematical induction to prove statements involving a positive integer $n$.

Extended Principle of Mathematical Induction

• A statement involving natural numbers might not be true for the first $k - 1$ positive integers but true for all values $n \geq k$.

• In such cases, use a variation of the Principle of Mathematical Induction, verifying $P(k)$ instead of $P(1)$.

• Pay attention to the domain given in the problem and test the first number first, then prove the rest.

Pattern Recognition

• Choosing a formula based on a few observations doesn't guarantee its validity, but pattern recognition is important.

• Once you have a pattern or formula that you think works, use mathematical induction to prove it.

Example 1: Finding a Formula and Proving Validity

• Find a formula for the sum and prove its validity: $3 + 7 + 11 + 15 + \ldots + 4n - 1$

• Prove: $S_n = 3 + 7 + 11 + \ldots + 4n - 1 = n(2n + 1)$

  1. $S_1 = 3$ and when $n = 1$, $n(2n + 1) = 1(2(1) + 1) = (1)(3) = 3$. Since $3 = 3$, the first case is true.

  2. Assume $P(k)$ is true, so $S_k = 3 + 7 + 11 + \ldots + 4k - 1 = k(2k + 1)$.

  3. Then $P(k+1)$ is $S_{k+1} = 3 + 7 + 11 + \ldots + 4k - 1 + 4(k+1) - 1 = (2k + 1) + 4(k+1) - 1 = (k+1)(2(k+1)+1)$.

• Since the first case is true and $P(k)$ implies $P(k+1)$, the formula holds.

Finding a Formula for the nth Term of a Sequence: Guidelines

1. Calculate the first several terms of the sequence, writing them in both simplified and factored forms.

2. Find a recognizable pattern for the terms and write a formula for the nth term of the sequence. This is your hypothesis or conjecture. Test your hypothesis by computing one or two more terms in the sequence.

3. Use mathematical induction to prove your hypothesis.

Example 2: Finding a Formula and Proving Validity

• Find a formula for the sum and prove its validity: $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + \frac{1}{4 \cdot 5} + \ldots + \frac{1}{n(n + 1)}$

• Prove: $S_n = \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + \ldots + \frac{1}{n(n+1)} = \frac{n}{n+1}$

  1. $S_1 = \frac{1}{2}$ and $\frac{1}{1(1+1)} = \frac{1}{2}$, since $\frac{1}{2} = \frac{1}{2}$, the first case is true

  2. Assume $P(k)$ is true, so $S_k = \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \ldots + \frac{1}{k(k+1)} = \frac{k}{k+1}$.

  3. Then $S_{k+1} = \frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \ldots + \frac{1}{k(k+1)} + \frac{1}{(k+1)(k+2)} = \frac{k}{k+1} + \frac{1}{(k+1)(k+2)} = \frac{k(k+2) + 1}{(k+1)(k+2)} = \frac{k^2 + 2k + 1}{(k+1)(k+2)} = \frac{(k+1)^2}{(k+1)(k+2)} = \frac{k+1}{k+2}$

• Since the first case is true and $P(k+1)$ follows from $P(k)$, $\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \ldots + \frac{1}{n(n+1)} = \frac{n}{n+1}$ for all $n \in \mathbb{Z}$ such that $n \geq 1$.

Sums of Powers of Integers

• Formulas:

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

  2. $1^2 + 2^2 + 3^2 + 4^2 + \ldots + n^2 = \frac{n(n + 1)(2n + 1)}{6}$

  3. $1^3 + 2^3 + 3^3 + 4^3 + \ldots + n^3 = \frac{n^2(n + 1)^2}{4}$

  4. $1^4 + 2^4 + 3^4 + 4^4 + \ldots + n^4 = \frac{n(n + 1)(2n+1)(3n^2 + 3n - 1)}{30}$

  5. $1^5 + 2^5 + 3^5 + 4^5 + \ldots + n^5 = \frac{n^2(n + 1)^2(2n^2 + 2n - 1)}{12}$

• Memorize the first three formulas.

Examples

• Find each sum:

  • $\sum_{i=1}^{7} i^3 = 1^3 + 2^3 + 3^3 + 4^3 + 5^3 + 6^3 + 7^3$

  • $\sum_{i=1}^{4} (6 - 4i^2)$

Applying Sum Formulas

• $\sum_{i=1}^{20} i = \frac{20(20+1)}{2} = \frac{20(21)}{2} = \frac{420}{2} = 210$

• $\sum<em>{i=1}^{5} (i^2 + 3i) = \sum</em>{i=1}^{5} i^2 + 3 \sum_{i=1}^{5} i$

• $\sum<em>{i=1}^{5} i^2 = \frac{5(5+1)(2(5)+1)}{6} = \frac{5(6)(11)}{6} = 55$ and $3 \sum</em>{i=1}^{5} i = 3 \frac{(5)(5+1)}{2} = 3 \frac{(5)(6)}{2} = 45$, so $\sum_{i=1}^{5} (i^2 + 3i) = 55 + 45 = 100$

Finite Differences

• The first differences of a sequence are found by subtracting consecutive terms.

• The second differences are found by subtracting consecutive first differences.

• Example: For the sequence 3, 5, 8, 12, 17, 23, \ldots

Linear vs. Quadratic Models

• If the second differences of a sequence are all the same, the sequence has a perfect quadratic model.

• If the first differences are all the same, the sequence has a perfect linear