Let's look at some dominoes...


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


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


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


Thus, P( n ) is true.