Guidelines for Induction Proofs


Inductions have several parts that are required for full credit.

  1. Clearly stated induction hypothesis, in proposition form or whatever you want, but CLEARLY stated! Note: If your induction hypothesis includes qualifiers on the domain, e.g., "n >= 0," then you may be making a mistake. (In 280, such side-conditions are usually superfluous.)

  2. Base Case. Pretty self-explanatory, but make sure you do the right one. If the QUESTION says for n >= 0, then it's pretty suggestive. Always read the question carefully when constructing your base case.

  3. Body of your proof: Always start with something true! DO NOT START WITH WHAT YOU ARE TRYING TO PROVE! For example, if you're trying to prove that some summation equals (x+1)3, don't write that x+x2+x3.. = (x+2)3, because that's what we want to prove... write out something you know, such as write the induction hypothesis or any FACT... but nothing that you can't verify until you prove your statement. I can't stress this enough!

Things to remember:

  1. You should use your induction hypothesis, and clearly state where. Also, state what you are assuming in terms of your induction hypothesis. Are you assuming it holds for all k < n and proving the statement for n or assuming it holds for n, and proving it for n+1?

  2. The way you prove something for a given range is by proving it for the beginning of that range and proving it for n+1 or n-1, which extends the range infinitely. For example, if I wanted to prove something works for all n in the integers, I would prove it for n=0, then n+1 and n-1, and that would do it.