"I really like this domino analogy. Also, I'd e..."


by Eric Rogstad Jul 17 2016

The principle of mathematical induction is a proof technique in which a statement, $~$P(n)$~$, is proven about a set of natural numbers $~$n$~$\. It may be best understood as treating the statements like dominoes: a statement $~$P(n)$~$ is true if the $~$n$~$\-th domino is knocked down\. We must knock down a first domino, or prove that a base case $~$P(m)$~$ is true\. Next we must make sure the dominoes are close enough together to fall, or that the inductive step holds; in other words, we prove that if $~$k \\geq m$~$ and $~$P(k)$~$ is true, $~$P(k+1)$~$ is true\. Then since $~$P(m)$~$ is true, $~$P(m+1)$~$ is true; and since $~$P(m+1)$~$ is true, $~$P(m+2)$~$ is true, and so on\.

I really like this domino analogy.

Also, I'd expect to see the word "all" somewhere in this first paragraph -- I think it's worth emphasizing the point that if we have the base case and the inductive step then the statement will be true for all of the numbers after the base case, just like all of the dominoes after the first one would fall down. I think the current final sentence of the intro paragraph doesn't make this clear enough.