**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.