How to Invent Inductive Proofs There is no “crank to turn” that is guaranteed to give you an inductive proof of any (true) statement S(n). Finding inductive proofs, like finding proofs of any kind, or like writing programs that work, is a task with intellectual challenge, and we can only offer a few words of advice. If you examine the inductive steps in Examples 2.4 and 2.6, you will notice that in each case we had to rework the statement S(n + 1) that we were trying to prove so that it incorporated the inductive hypothesis, S(n), plus something extra.

 

We expressed the sum 1 + 2 + 4 + · · · + 2n + 2n+1 as the sum 1 + 2 + 4 + · · · + 2n which the inductive hypothesis tells us something about, plus the extra term, 2n+1 In Example 2.6, we expressed the set C, with strings of length n + 1, in terms of two sets of strings (which we called D0 and D1) of length n, so that we could apply the inductive hypothesis to these sets and conclude that both of these sets were of limited size. Of course, working with the statement S(n + 1) so that we can apply the inductive hypothesis is just a special case of the more universal problem-solving adage “Use what is given.”

 

The hard part always comes when we must deal with the “extra” part of S(n+1) and complete the proof of S(n+1) from S(n). However, the following is a universal rule:  An inductive proof must at some point say “· · ·and by the inductive hypothesis we know that· · · .” If it doesn’t, then it isn’t a inductive proof.