Prev: Loop Invariants Next: Elementary Data Structures 
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
Invariants and Recursive Algorithms
Recursive Algorithms often solve problems by the
Divide & Conquer paradigm,
which involves three stages:
 ^{1}It might be better to terminate the recursion at, say, any array of size n < 15, because an alternate sorting algorithm, like Insertion Sort, will perform better than Merge Sort for small n.  

// sorts A[first..last] void msort(int *A, int first, int last) { // base case if (first >= last) return; // divide int mid = (first+last) / 2; // conquer msort(A, first, mid); msort(A, mid+1, last); // combine merge(A, first, mid, last); }Just like an inductive step for a strong induction, you may assume that the algorithm is correct for all smaller cases, and therefore the conquer stage correctly sorts the two sublists A[first..mid] and
A[mid+1..last] . Since the merge(...) step
results in a sorted A[first..last] , the algorithm
is correct.
 This expeditious analysis illustrates how powerful invariants are for proving the correctness of recursive algorithms.  
The analysis of the running time is similar.
Let T(n)
represent the number of steps to Merge Sort an
n element array. When
n ≤ 1,
the array
The algebra involved in the inductive step is beyond the scope
of CMPT 225: you will do proofs like this when you
take CMPT 307. If you just can't wait until then, click here.
You will write and prove your own loop invariants in CMPT 225: some will be about the algorithm's progress/correctness; some about its running time. Induction has another use however— as applied to the development and analysis of data structures. This is the subject of Part 3.  
Next: Elementary Data Structures 