Chapter 9.4 Mathematical Induction

                                                          Chapter 9.4 Mathematical Induction

What is Mathematical induction???????

Mathematical induction is a method of proof in which a statement is proved for one step in a process, and it is shown that if the statement holds for that step, it holds for the next.

The reasoning behind mathematical induction can be linked to a infinite chain of dominos.  It is impossible to go and push the dominos down one by one.  However, if it is given that by pushing down one domino it will push down that domino next to it then it can be inferred that simply by pushing down one domino you are pushing them all down.

It is very important to note that this process must be a legitimate proof, and is not simply jumping to conclusions.

Mathematical induction is a three step process.

1. Show that the claim is true for n=1

2. Assume that the claim is true for n.

3. Show that it is true for n+1

Example

1 + 3 + 5 + ... + (2n-1) = n²

1. Show it is true for n=1

1 = 1² is True

2. Assume it is true for n=k

1 + 3 + 5 + ... + (2k-1) = k² is True

3. Now, prove it is true for k+1

1 + 3 + 5 + ... + (2k-1) + (2(k+1)-1) = (k+1)² 

 1 + 3 + 5 + ... + (2k-1) = k² (the assumption above), so we can do a replacement for all but the last term:

k² + (2(k+1)-1) = (k+1)²

Now expand all terms:

k² + 2k + 2 - 1 = k² + 2k+1

And simplify:

k² + 2k + 1 = k² + 2k + 1

It's good!

So:

1 + 3 + 5 + ... + (2(k+1)-1) = (k+1)² is True

And that's mathematical induction In a nut shell.

www.youtube.com/watch?v=lOGqZAMHS-M

Matthew Silbergleit