CS 383, Algorithms
Mathematical Background: Induction

This page is located at http://www.cs.bc.edu/~alvarez/Algorithms/Notes/induction.html

Scope

This page provides a very brief review of the technique of mathematical induction, which is useful in CS383 and in courses on the theory of computation. For further details, see courses and other sources in discrete mathematics. I encourage you to do the exercises given below and hope that this material will be helpful. Let me know if you have any questions. Have fun!

Mathematical recursion and induction

Recursion is a method of defining countable sets, relations, or functions in a step-by-step fashion. In the simplest context, one wishes to define a function on the set of natural numbers. Using recursion, one proceeds as follows:
  1. Define the "first value" f(0) of the function.
  2. Assuming that the values f(0) ... f(n) have been defined for some value of n, define the "next value" f(n+1), possibly in terms of one or more of the "previous values" f(0) ... f(n).
A toppling dominoes metaphor is appropriate. A number n topples when the corresponding function value f(n) is defined. The basis step makes 0 topple, and the induction step topples n+1 once 0..n have toppled.

More generally, a definition by recursion constructs a set A in three steps:

  1. Basis step: Define a starting set A0.
  2. Recursion step: Assume that sets A0, ... An have been defined. Then define the "next" set An+1 in terms of A0, ... An.
  3. Closure: Define the final set A as the union of all the sets An.
A set A constructed by recursion according to the above procedure is called an inductive set. The prototypical inductive set is the set N of natural numbers.

Induction is a method of reasoning which may be used to show that every element of an inductive set has a certain property. For example, suppose that you want to find a formula for the sum Sn of the first n natural numbers: Sn = 1 + 2 + 3 + ... + n. You try some small values of n and find: S0=0, S1=1, S2=3, S3=6, S4=10. After fiddling with these values for a while you see that the formula Sn=n(n+1)/2 works for these values of n. But what about larger values? Since there are infinitely many values of n to check, in order to reach some conclusion about the validity of the formula before you die you have to come up with some abbreviated logical argument that applies to all values of n without actually checking them one by one.

Here's how induction does the trick:

  1. (Basis step) Check the first value of n: n=0. Yes, S0=0=0(0+1)/2.
  2. (Induction step) Assume that you've checked all the values up to and including some n, and show that the next value, n+1, also checks:
    Sn+1 = Sn + (n+1) = n(n+1)/2 + (n+1) = (n+1)(n/2 + 1) = (n+1)(n+2)/2. Yes!
So now you see that the natural numbers are lined up like dominoes and the above two steps make all of them fall. The basis step makes the first one fall, and the induction step shows that if all the dominoes up to a certain point have fallen then the next one in line falls too. This implies that all of them fall, i.e. in this case that the formula works for all values of n.

More generally, if one wishes to prove that a statement A(n) is true for every n, an induction proof would proceed as follows.

  1. Basis: one proves that A(0) is true.
  2. Induction step: one assumes (induction hypothesis) that A(n) is true, and proves that this hypothesis implies that A(n+1) is true.

Exercises

  1. By trial and error, guess a simple formula in terms of n for the sum Sn = 1 + 4 + 9 + ... + n2 of the squares of the first n positive integers. Then prove your formula by induction.
  2. Use induction to prove that 2n > n for all natural numbers n.