Table of Contents   |   Proof Methods   |   Glossary

Forming a Stronger Hypothesis

Occasionally, when doing induction, you'll find that the proof doesn't quite work out.  This is especially true when proving inequalities where you're not looking for an exact answer, such as upper and lower bounds like O(n).  But this can also occasionally happen with statements that are not strict enough to be proven true.

In this situation, even though you may not be able to prove the exact Inductive Hypothesis you were aiming for, you may be able to prove a stronger version of it.

Thinking back to the dominoes, a weakly formed inductive hypothesis is like having a weak domino that can't knock over its neighbor.  

If a stronger inductive hypothesis can be found,

then the proof becomes possible.

Example 1

(Floyd and Beigel, pg. 44)

The sum of the first n cubes have the following characteristics:

This pattern seems to imply the following proposition.
                   

Suppose we tried to prove this statement by induction.

  2) We know from the above table that the base case is true.

  3) The Inductive Hypothesis would assume that

         

for some natural number j.

  4) The inductive step would be to prove that

         

is true for some larger natural number l > j

After substituting the inductive hypothesis, we get

       

         =? l2

But it's not true that for all k and j that

         

will result in a square.  (This can be easily checked at k=1 and j=5000.)  This is an example of where a more general (weaker) hypothesis is too hard to prove.  

 We can try to formulate a stronger hypothesis.  Reexamining the pattern reveals something that's hopefully familiar

The numbers 0, 1, 3, 6, and 10 are the same numbers that show up in the summation identity

from k = 0 to 4

  1) A stronger proposition to prove is:

           

[lightbulb goes here]  If we can prove this hypothesis correct, then we also have proved a specific case of the original hypothesis.  It seems to be nonintuitive to prove something more complex in order to prove something more general but in fact, a stronger case can be easier to prove (when chosen correctly).  In this case, we used a pattern to develop a stronger proposition but, in general, there are few heuristics that can help you build a stronger hypothesis.  We discuss one of these in the 2nd Example.

 2) First, the base case. At k = 0

         

         

 3) Assume the following Inductive hypothesis.

          

 4) The Inductive Step is to prove that

         

First checking the base case at k=0

so the base case is true

After substituting the inductive hypothesis, we get

5) This completes the proof of the proposition that

is true.

And also proves the original statement:

     

Back to:

Top of Page   |   Table of Contents   |   Proof Methods   |   Glossary