previous next
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 3: Induction in CMPT 225 Part 2: How Induction Relates to Computer Science

Induction is about mathematical structures which are self-similar. So are algorithms and computer programming, both of which apply recursion and iteration to solve problems.


Induction and Recursion

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 nth case, you relied on the n − 1st 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 nth case was true.

This sort of recursive reasoning, where you break down the large case into smaller cases, is known as the top-down approach. In this example, it leads directly to a recursive implementation of the function SumOdd(n), which for positive n returns the sum of the first n odd integers: the resulting sum is based on a call to SumOdd(n-1), when n > 1. The case for n = 1, where the recursion stops, is the base case. 

int SumOdd(int n) {
  // base case
  if (n == 1) return 1; 

  // recursive case
  return SumOdd(n-1) + (2*n - 1);
}


Induction and Iteration

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 bottom-up approach. In the squares example, it leads directly to an iterative implementation of the function SumOdd(n), defined as before. This time a variable total holds the running sum of the first i-1 odd integers. In each iteration, the ith odd integer is added to the running sum. 

int SumOdd(int n) {
  total = 1;
  for (int i = 2; i <= n; ++i) {
    // assert(total == (i-1)*(i-1));
    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 ∑ = i2. An assertion about how the data of the algorithm relate to the loop index is called a loop invariant. 		 
next next        Next: Loop Invariants