12345
of 5

Mathematic Induction

Let's look at some dominoes...
 

domino
 

Did you ever stack them so you could knock them all down?  It's actually pretty fun and, if you've never done it, I highly recommend that you do.

Let's line up a row of dominoes...
 

line of standing dominoes

There are four main parts to math induction...

1 ) Can we knock down the first domino?

 

push the first domino over

Yes!

Show P( 1 ) is true.

 

2 ) Can we knock down a random domino somewhere
in the middle?

Let's call it the kth domino.

push over the kth domino

Yes!

Assume P( k ) is true.

 

3 ) (This one is the big deal.)

If we knock down that kth domino, will the next domino get knocked down too?

push over the kth domino, which pushes over the k + 1 domino

Show P( k ) --> P( k + 1 ).

 

4 ) If we do all of the above, will all the dominoes fall?

 

all of the dominoes fall over

YES!

Thus, P( n ) is true.