Prev: The Inductive Step	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 The Basis Cases The inductive step is a powerful engine indeed. For the squares example, the n + 1st case relies on the nth 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 1st case, because no case comes before it! The 1st 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 1st case (as well as the 2nd, 3rd, and 4th 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 $${\sum_{i=1}^{n}(2i-1)} = n^2+1$$, 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.