Induction: The Best Proof Technique That Wasn’t

Inductive proofs are one of the first types of formal theorem proving students run across. There is good reason for this; it’s easy to teach and powerful (and comes in handy for the piles of complexity analyses I’ve assigned my students this week).

As a quick refresher, in an induction proof you are trying to show that $f(n) = g(n)$f(n)=g(n) by first showing that $f(0) = g(0)$f(0)=g(0), and then assuming that $f(k) = g(k)$f(k)=g(k) for some $kn$k<n. If you can show that, given these results, $f(k+1) = g(k+1)$f(k+1)=g(k+1), you’ve shown that $f(n) = g(n)$f(n)=g(n). QED.

This is about where you should be suspicious. We picked $k$k arbitrarily, right? This is about where people tell you that you have some “well-ordered” numbers.