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 0: The 411 on CMPT 225 So, you are taking CMPT 225 after having MACM 101 and your first couple of computing classes under your belt. After this course, there is CMPT 275, Co-Op, a vast array of interesting upper division courses, all followed by gainful employment. You are totally stoked. But not so fast— some of your prerequisites may not be as you remember. Your CMPT 225 instructor will assume you have a solid mastery of the concepts listed in their syllabi. So watch out if you were one of those CMPT 125/126/128 students who got a 0 for the recursion question on the final but still got a B in the course: recursion is relied upon heavily in CMPT 225. Also relied upon: MACM 101: Mathematical Induction big-O graphs and trees MATH 151/152: limits as n → ∞ L'Hôpital's Rule convergence of series CMPT 125/126/128: basic coding constructs recursion how to write code modularly testing your code memory management (pass by value/reference) As usual, you shouldn't expect your instructor to re-teach the prerequisite material. Instead, you should take the first 2-3 weeks of the semester when not much is on your plate to do some serious review, to fill in any gaps, to catch up. To make the process easier, I present some of the prerequisite concepts here, in workshop style. The series is called What Every CMPT 225 Student Should Know Before Taking CMPT 225. This first instalment is what you, a budding Computer Scientist, should know about Mathematical Induction. The abstract: Mathematical Induction is a central part of computer science, but it isn't presented that way in MACM 101. Induction is treated as a tool for proving things about numerical or algebraic things: sometimes equations, or inequalities, or Fibonacci numbers. Woo-hoo. And even though it's very useful for that, there is a strong connection between induction and algorithms— both the iterative kind and the recursive kind— that is never brought to light. Induction can be used to prove the correctness of algorithms; induction can be used to determine the running time of algorithms; and induction can be used in the development of algorithms.1 1Naturally, you must be reasonably proficient at the mathie kinds of proofs before you can apply induction to computing.