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:
- Define the "first value" f(0) of the function.
- 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:
- Basis step:
Define a starting set A0.
- Recursion step:
Assume that sets A0, ... An have been defined.
Then define the "next" set An+1 in terms of
A0, ... An.
- 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:
- (Basis step) Check the first value of n: n=0.
Yes, S0=0=0(0+1)/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.
- Basis: one proves that A(0) is true.
- Induction step: one assumes (induction hypothesis)
that A(n) is true, and proves that this hypothesis implies that
A(n+1) is true.
Exercises
- 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.
- Use induction to prove that 2n > n
for all natural numbers n.