Prev: Summary Next: The Basis Cases 
What Every CMPT 225 Student Should Know About Mathematical Induction
 by Brad Bart, Simon Fraser University  
Part 1: Overview of Induction

Part 1: Overview of Mathematical Induction
You concluded the last section with the unenviable task of proving your claim: . As convinced as you are by the pattern, Brad is not. Verification case by case, i.e., by substituting n = 1, 2, 3, . . ., will not be an effective proof technique, unless you happen to have an infinite amount of time on your hands.
Fortunately, you recall a math trick which you saw in calculus, known as the method of differences. Since you believe that your summation is correct, you consider n^{2}, and calculate the value you need to add to it to reach (n + 1)^{2}. That is, the difference (n + 1)^{2} − n^{2}. Since the difference is 2n + 1, which is precisely the n + 1^{st} term in the summation, you have proven your closed form holds for incrementally larger integers n. And so you go to CMPT 225 class knowing that you not only pwned the problem, but totally pwned Brad as well.
What you really did by using the method of differences is a kind of proof by induction, which, if you recall the opening paragraph, operates on structures which are selfsimilar. In this case, you used the nterm sum to generate the (n + 1)term sum by adding the n + 1^{st} term. Or, algebraically,
The technical term for this is the inductive step: to use the verified smaller structures to verify the larger structures. Each of the smaller structures is called an inductive hypothesis. In a simple induction, like this one, the inductive step shows that the n^{th} case you verify will imply the n + 1^{st} case.  
In a strong induction, the inductive step may use any combination of verified cases, i.e., the 1^{st}, 2^{nd}, 3^{rd}, . . ., n^{th} cases, in order to imply the n + 1^{st} case.  Clearly, a simple induction is a special case of a strong induction.  
Next: The Basis Cases 