Strong Induction

There are occasions where the , at least as we have studied it up to this point, does not seem sufficient. Here is a concrete example. The professor asked Bob to study a function \(f(n)\) defined recursively by \(f(n) = 2f(n-1) - f(n-2)\) with \(f(1)=3\) and \(f(2)=5\). Specifically, the professor asked Bob to compute \(f(10^{10})\), which seems like a daunting task. Over coffee, Bob scribbled on a napkin and determined that \(f(3)=7\) and \(f(4)=9\), and on the basis of these calculations alone, he thought that it might just be possible that \(f(n) = 2n+1\) for all \(n\geq 1\). If this were true, he could simply report that \(f(10^{10})=2\cdot 10^{10}+1=20000000001\).

Bob was beginning to understand proofs by induction, so he tried to prove that \(f(n)=2n+1\) for all \(n\ge1\) by induction. For the base step, he noted that \(f(1)= 3=2\cdot1+1\), so all is ok to this point. For the inductive step, he assumed that \(f(k)=2k+1\) for some \(k\ge1\) and then tried to prove that \(f(k+1)=2(k+1)+1\). If this step could be completed, then the proof by induction would be done.

But at this point, Bob seemed to hit a barrier, because \[\begin{aligned}\end{aligned}\] using the inductive hypothesis to replace \(f(k)\) by \(2k+1\). However, he's was totally perplexed about what to do with the \(f(k-1)\). If he knew that \(f(k-1)=2(k-1)+1\), then the right hand side would result in \(2(2k+1) -(2k-1)= 2k+3=2(k+1)+1\), which is exactly what he wants. Bob always plays by the rules, and he has to admit that he doesn't know that \(f(k-1)=2(k-1)+1\). He only knows that \(f(k)=2k+1\).

Bob was about to throw in the towel and ask his computer to start making the calculations recursively, when Carlos comes along and asks what he's doing. Carlos sees right away that the approach Bob was taking to prove that \(f(n)=2n+1\) by induction won't workbut after a moment's reflection, Carlos says that there's a stronger form of an inductive proof that will do the trick. Carlos patiently explained to Bob a proposition which is called the Strong Principle of Mathematical Induction. To prove that an open statement \(S_n\) is valid for all \(n\ge1\), it is enough to

1. Show that \(S_1\) is valid, and

2. Show that \(S_{k+1}\) is valid whenever \(S_m\) is valid for all integers \(m\) with \(1\le m\le k\).

The validity of this proposition is trivial since it is stronger than the principle of induction. What is novel here is that in order to prove a statement, it is sometimes to your advantage to prove something even stronger. Combinatorial mathematicians call this the bootstrap phenomenon.

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.