Principle of Mathematical Induction Notes

Principle of Mathematical Induction

Recall

• Sequence: 1, 4, 7, 10, 13, …

• $a_n = 3n - 2$

• $S_n = \frac{n}{2}(3n - 1)$

• Examples:

  • $a_1 = 3(1) - 2 = 1$

  • $a_2 = 3(2) - 2 = 4$

  • $a_3 = 3(3) - 2 = 7$

  • $a_4 = 3(4) - 2 = 10$

  • $a_5 = 3(5) - 2 = 13$

  • $S_2 = \frac{2}{2}(3(2) - 1) = 5$

  • $S_3 = \frac{3}{2}(3(3) - 1) = 12$

  • $S_1 = \frac{1}{2}(3(1) - 1) = 1$

Take Note!

• A rule, pattern, or formula that seems to work for several values of $n$ cannot be simply decided as valid for all values of $n$ without a legitimate proof.

• Mathematical Induction is a technique for proving a statement (theorem or formula) that is asserted about every natural number.

Observe the Following Sums of Odd Numbers

• $S_1 = 1 = 1^2$

• $S_2 = 1 + 3 = 4 = 2^2$

• $S_3 = 1 + 3 + 5 = 9 = 3^2$

• $S_4 = 1 + 3 + 5 + 7 = 16 = 4^2$

• $S_5 = 1 + 3 + 5 + 7 + 9 = 25 = 5^2$

• Sum of the first $n$ odd numbers:

  • $S_n = 1 + 3 + 5 + 7 + 9 + \cdots + (2n - 1) = n^2$

The Principle of Mathematical Induction

• Let $P(n)$ be a statement involving the positive integers.

• If:

  1. $P(1)$ is true, and

  2. For all positive integers $k$, the truth of $P(k)$ implies the truth of $P(k + 1)$

• Then the statement $P(n)$ must be true for all positive integers $n$.

Steps in Mathematical Induction

1. Base Case: Verify if the formula is true for $P(1)$.

2. Induction Hypothesis: Assume that the formula is true for $n = k$.

3. Induction Step: Prove that the formula is true for the next integer $k + 1$.

Example 1: Prove $P(n) = 1 + 3 + 5 + 7 + 9 + \cdots + (2n - 1) = n^2$

1. Base Case: Verify if the formula is true for $P(1)$.

   • $2(1) - 1 = 1^2$

   • $2 - 1 = 1$

   • $1 = 1$

   • $\therefore P(1) \text{ is true}$

2. Induction Hypothesis: Assume that the formula is true for $n = k$.

   • $1 + 3 + 5 + 7 + 9 + \cdots + (2k - 1) = k^2$

3. Induction Step: Prove that the formula is true for the next integer $k + 1$.

   • $1 + 3 + 5 + 7 + 9 + \cdots + (2k - 1) + 2(k + 1) - 1 = (k + 1)^2$

   • $k^2 + 2(k + 1) - 1 = (k + 1)^2$

   • $k^2 + 2k + 2 - 1 = (k + 1)^2$

   • $k^2 + 2k + 1 = (k + 1)^2$

   • $(k + 1)^2 = (k + 1)^2$

• Conclusion: $P(n)$ is true for every natural number, $\mathbb{N}$.

Example 2: Use mathematical induction to prove $2 + 4 + 6 + \cdots + 2n = n(n + 1)$.

1. Base Case: Verify if the formula is true for $P(1)$.

   • $2(1) = 1(1 + 1)$

   • $2 = 1(2)$

   • $2 = 2$

   • $\therefore P(1) \text{ is true}$

2. Induction Hypothesis: Assume that the formula is true for $n = k$.

   • $2 + 4 + 6 + \cdots + 2k = k(k + 1)$

3. Induction Step: Prove that the formula is true for the next integer $k + 1$.

   • $2 + 4 + 6 + \cdots + 2k + 2(k + 1) = (k + 1)((k + 1) + 1)$

   • $k(k + 1) + 2(k + 1) = (k + 1)(k + 2)$

   • $k^2 + k + 2k + 2 = (k + 1)(k + 2)$

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

   • $(k + 1)(k + 2) = (k + 1)(k + 2)$

• Conclusion: $P(n)$ is true for every natural number, $\mathbb{N}$.

Example 3: Given {3, 9, 15, 21, …}, write an expression to represent the $n^{th}$ term of the sequence, then find the formula for the sum of the first $n$ terms, then prove that the two expressions are true using mathematical induction.

• $a<em>n = a</em>1 + (n - 1)d$

• $a_n = 3 + (n - 1)(6)$

• $a_n = 3 + 6n - 6$

• $a_n = 6n - 3$

• $S<em>n = \frac{n}{2}(a</em>1 + a_n)$

• $S_n = \frac{n}{2}(3 + 6n - 3)$

• $S_n = \frac{n}{2}(6n)$

• $S_n = 3n^2$

• Statement: $3 + 9 + 15 + 21 + \cdots + (6n - 3) = 3n^2$

Base Case:

• Verify if the formula is true for $P(1)$.

• $6(1) - 3 = 3(1)^2$

• $6 - 3 = 3(1)$

• $3 = 3$

• $\therefore P(1) \text{ is true}$

Induction Step:

• Assume that the formula is true for $n = k$.

• $3 + 9 + 15 + 21 + \cdots + (6k - 3) = 3k^2$

• Prove that the formula is true for the next integer $k + 1$.

• $3 + 9 + 15 + 21 + \cdots + (6k - 3) + 6(k + 1) - 3 = 3(k + 1)^2$

• $3k^2 + 6(k + 1) - 3 = 3(k + 1)^2$

• $3k^2 + 6k + 6 - 3 = 3(k + 1)^2$

• $3k^2 + 6k + 3 = 3(k + 1)^2$

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

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

• Conclusion: $P(n)$ is true for every natural number, $\mathbb{N}$.

Example 4: Use mathematical induction to prove $\sum_{i=1}^{n} 2^i = 2(2^n - 1)$.

Base Case:

• Verify if the formula is true for $P(1)$.

• $2^1 = 2(2^1 - 1)$

• $2 = 2(2 - 1)$

• $2 = 2$

• $\therefore P(1) \text{ is true}$

Induction Hypothesis:

• Assume that the formula is true for $n = k$.

• $2 + 4 + 8 + \cdots + 2^k = 2(2^k - 1)$

Induction Step:

• Prove that the formula is true for the next integer $k + 1$.

• $2 + 4 + 8 + \cdots + 2^k + 2^{k+1} = 2(2^{k+1} - 1)$

• $2(2^k - 1) + 2^{k+1} = 2(2^{k+1} - 1)$

• $2^{k+1} - 2 + 2^{k+1} = 2(2^{k+1} - 1)$

• $2 Imes 2^{k+1} - 2 = 2(2^{k+1} - 1)$

• $2^{k+2} - 2 = 2^{k+2} - 2$

• $2(2^{k+1} -1) = 2(2^{k+1} - 1)$

• Conclusion: $P(n)$ is true for every natural number, $\mathbb{N}$.

Exercise

• Use mathematical induction to prove $1 + 4 + 4^2 + \cdots + 4^{n-1} = \frac{4^n - 1}{3}$.