Prev: The Basis Cases Next: Loop Invariants 
What Every CMPT 225 Student Should Know About Mathematical Induction
 by Brad Bart, Simon Fraser University  
Part 1: Overview of Induction
Part 2: How Induction Relates to Computer Science

Part 2: How Induction Relates to Computer Science
Induction is about mathematical structures which are selfsimilar. So are algorithms and computer programming, both of which apply recursion and iteration to solve problems.
Recursion is an algorithmic technique where you solve a problem by using the solutions to smaller instances of the same problem. The inductive step from the squares example was recursive because in order to verify the n^{th} case, you relied on the n − 1^{st} case. But similarly, case n − 1 depended on case n − 2. And case n − 2 depended on case n − 3, which depended on case n − 4, . . ., which depended on case 3, which depended on case 2, which depended on case 1. And since case 1 was verified in the basis step, you concluded the n^{th} case was true.
This sort of recursive reasoning, where you break down the large case
into smaller cases, is known as the topdown approach.
In this example, it leads directly to a recursive implementation of the
function int SumOdd(int n) { // base case if (n == 1) return 1; // recursive case return SumOdd(n1) + (2*n  1); }
The other way to look at induction is by starting with case 1, the basis case. Then, by using the inductive step, case 1 implies case 2. Now that you have case 2, you use the inductive step again, and you have case 3. Case 3 implies case 4, which implies case 5, which implies case 6, and so on, climbing your infinite ladder, rung by rung, going as high as you like.
This sort of recursive reasoning, where you use the smaller cases to
build up to the large case, is known as the bottomup approach.
In the squares example, it leads directly to an iterative implementation
of the function int SumOdd(int n) { total = 1; for (int i = 2; i <= n; ++i) { // assert(total == (i1)*(i1)); total += (2*i  1); // assert(total == i*i); } }The two assertions in the implementation serve to convince the reader that the code does just what it is supposed to do: that at the beginning of the loop ∑ = (i − 1)^{2}, and at the end of the loop ∑ = i^{2}. An assertion about how the data of the algorithm relate to the loop index is called a loop invariant.  
Next: Loop Invariants 