The most common errors students make with induction:

• Not stating clearly what the statement  P(n)  is that they are working with;
• Not stating clearly what values of  “n”  (or  “k”)  they are working with;
• Doing proofs “backwards”.

1. Always begin by stating clearly and explicitly the statement(s)  P(n)  (or whatever you want to call them) which you're trying to prove; this includes mentioning the values of  n  that are being considered.

2. If  P(n)  is an algebraic statement, such as “ n² < n! ”,  NEVER use an equal sign as it is used after the  P(n)  in the following example:

   P(n) = n² < n!.

   (It is not clear whether  P(n)  stands for the algebraic expression  n²  or the statement  n² < n!,  and students often confuse the two when they write things this way.) Correct ways of defining  P(n)  were discussed in class.

3. Don't do any of the proofs backwards, even the base case (until you're absolutely sure you know when and how it is safe to do a proof backwards). I.e., never start with what you're trying to prove and somehow squeeze out of it something you know is true. (I have mentioned this several times in class since the beginning of the semester.)

4. When you do the inductive step (e.g.,
          assume  P(n)  and prove  P(n+1),
   or
          assume  P(k-1)  and prove  P(k) ),
   always state specifically what assumption you are making about the  n  or the  k  you are using (e.g.,  n ≥ 0?  k ≥ 3?).

5. Finish off the proof by summarizing what you have accomplished.

See also Induction Checklist.

Return to Course Home Page.

Last modified 4/11/08