Prev: Summary	What Every CMPT 225 Student Should Know About Mathematical Induction - by Brad Bart, Simon Fraser University
Part 1: Overview of Induction Summary The Inductive Step The Basis Cases Part 2: How Induction Relates to Computer Science Programming Using Induction Loop Invariants Invariants and Recursive Algorithms Part 3: Induction in CMPT 225 Elementary Data Structures Linked Structures 1: Binary Search Trees Linked Structures 2: Binary Heaps	Part 1: Overview of Mathematical Induction You concluded the last section with the unenviable task of proving your claim: $${\sum_{i=1}^{n} (2i-1) = n^2}$$. 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. Method of Differences 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 n2, and calculate the value you need to add to it to reach (n + 1)2. That is, the difference (n + 1)2 − n2. Since the difference is 2n + 1, which is precisely the n + 1st 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. The Inductive Step 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 self-similar. In this case, you used the n-term sum to generate the (n + 1)-term sum by adding the n + 1st term. Or, algebraically, $$\begin{array}{rl} & \displaystyle{\sum_{i=1}^{n} (2i-1) = n^2... ... & \displaystyle{\sum_{i=1}^{n+1} (2i-1) = (n+1)^2} \end{array}$$ 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 nth case you verify will imply the n + 1st case.
	In a strong induction, the inductive step may use any combination of verified cases, i.e., the 1st, 2nd, 3rd, . . ., nth cases, in order to imply the n + 1st case.	Clearly, a simple induction is a special case of a strong induction.