Prev: The Inductive Step Next: Programming Using Induction 
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
The Basis Cases The inductive step is a powerful engine indeed. For the squares example, the n + 1^{st} case relies on the n^{th} case, so you can verify any case as high as you like, i.e., for all positive integers n. Well, almost all. The inductive step doesn't verify the 1^{st} case, because no case comes before it! The 1^{st} case is a special case called a basis case. It is special because you must verify it using another method besides the inductive step. It turns out that you already did this when you tested out the first few sums: you verified the 1^{st} case (as well as the 2^{nd}, 3^{rd}, and 4^{th} cases) when you were searching for your general pattern.  
For simple induction, you only have to verify one basis case: n = 1. For strong induction, it may be several cases: whatever your inductive step doesn't cover. The process of verifying these cases is known as the basis step. The combination of the inductive step and basis step is a proof by induction. In most of the examples that follow, we will skip the basis step, which is pretty common for usage by computer scientists, like yourself. Why? Because you just aren't likely to assert a claim without first verifying a few small cases! But please note that the basis step is treasured by some overly skeptical mathematicians who know that the inductive step on its own is not strong enough as a general proof. This is because it is possible to prove the inductive step on something that is always false. For example, the method of differences also works on , which is false for all n. The mathematicians aren't wrong about this, but then again they aren't as practical as yourself, either. Now just because you aren't going to prove any basis cases doesn't mean you should just forget about them either. They bear a strong resemblance to the base cases of recursive algorithms, which is the first topic of Part 2.  You have seen proofs by induction before, most notably in MACM 101. It is important that you are comfortable with the mechanics of a proof by induction before proceeding to Parts 2 and 3. To bone up, there are worked examples and exercises for you to try.  
Next: Programming Using Induction 