Question Appendix.2: Using Mathematical Induction Use mathematical induction to p...
Using Mathematical Induction
Use mathematical induction to prove the following formula.
S_n = 1 + 3 + 5+ 7 + \cdot \cdot \cdot + (2n – 1)= n^2Mathematical induction consists of two distinct parts. First, you must show that the formula is true when n = 1.
1. When n = 1, the formula is valid because S_1 = 1 = 1^2.
The second part of mathematical induction has two steps. The first step is to assume that the formula is valid for some integer k (the induction hypothesis).
The second step is to use this assumption to prove that the formula is valid for the next integer, k + 1.
2. Assuming that the formula
S_k = 1 + 3 + 5+ 7 + \cdot \cdot \cdot + (2k – 1)= k^2is true, you must show that the formula S_{k+1} = (k + 1)^2 is true.
S_{k+1} = 1 + 3 + 5+ 7 + \cdot \cdot \cdot + (2k – 1) + \left[2 (k + 1) -1\right]= \left[1 + 3 + 5+ 7 + \cdot \cdot \cdot + (2k – 1)\right] + (2k + 2 – 1)
= S_k + (2k + 1) \quad\quad \text{ Group terms to form } S_k.
= k^2 + 2k + 1 \quad\quad \text{ Substitute } k^2 \text{ for } S_k.
= (k + 1)^{2}
Combining the results of parts (1) and (2), you can conclude by mathematical induction that the formula is valid for all positive integers n.