9.4 Mathematical Induction

mathematical induction - means of proving a theorem by showing that if it is true of any particular case, it is true of the next case in a series, and then showing that it is indeed true in one particular case

Steps to Mathematical Induction:

Let P(n) be a statement involving the positive integer n.

1.) Show that P(1) is true.

2.) Assume P(n) is true for n.

3.) Show that is is true for n+1.

 

Example

P(n) = 1 + 3 + 5 + 7 +...+ (2n-1) = n^2

Step 1: Show it is true for n=1.

P(1) = 1 = 1^2
          1 = 1 ✓

Step 2:  Assume P(n) is true.

P(n) = 1 + 3 + 5 + 7 +...+ (2n-1) = n^2 

Step 3: Show it is true for n+1.

1 +3 + 5 + 7 +...+ (2n-1) + [2(n+1) - 1] = (n+1)^2 
                                     n^2 + 2n + 1 = n^2 + 2n + 1  ✓

*Since 1 + 3 + 5 + 7 +...+ (2n-1) = n^2, you can substitute 1 +3 + 5 + 7 +...+ (2n-1)  for n^2*