Mathematical Induction Makes Extrapolation Accurate
Last week, I introduced the idea of avoiding egregious errors in a program by verifying (perhaps by stepping through it by hand) that it works for a small test case, then extending our knowledge a little at a time by reasoning, "It works for n, and extending it by one seems to do the right thing, so the code is probably correct."
This kind of reasoning may help our gut feeling about a piece of code, but it would be nice to be able to draw conclusions about a program that can give us confidence beyond gut feelings. To explain how to formalize our reasoning, I must first explain a concept that is central to much of mathematics. I suspect that many software developers have studied this concept, probably in high school or college, and then have figuratively put it on a shelf and forgotten about it. This article aims to take the concept from the shelf and dust it off so that we can use it. The concept is mathematical induction.
Mathematical induction typically deals with non-negative integers, also known as natural numbers. As this description implies, -1 is not a natural number, but 0 is. Moreover, if n is a natural number, so is n+1. Thus, for example, we know that 3 is a natural number because 3=2+1 and 2 is a natural number. I'll leave it to the reader to understand why 2 is a natural number.
By definition, there can be no largest natural number. If there were a largest natural number, which we might call
N, then we would be unable to reconcile this state of affairs with the fact that
N+1 is a natural number. By implication, there are infinitely many natural numbers. However, there is a smallest natural number, namely 0. Moreover, natural numbers are well ordered, which means that every set of natural numbers has a smallest element, even though it does not necessarily have a largest element.
Mathematical induction is a technique for using these properties of natural numbers to prove claims about every natural number. For example, let's define
f(n) as the sum of all of the natural numbers less than n. Under this definition:
f(0) = 0 (because no natural numbers are less than 0 and the sum of the empty set is 0)
f(1) = 0 (because 0 is the only natural number less than 1)
f(2) = 0 + 1 = 1
f(3) = 0 + 1 + 2 = 3
f(4) = 0 + 1 + 2 + 3 = 6
f(5) = 0 + 1 + 2 + 3 + 4 = 10
f(6) = 0 + 1 + 2 + 3 + 4 + 5 = 15
and so on. At this point, if we're good at recognizing patterns, we might suspect that if
n>0, f(n)=n*(n-1)/2, because that relationship holds for all the values of
n we have seen so far. How do we prove or disprove it?
We might start by formalizing our definition of
f. We can define
f(0) as 0; in addition, we can define
f(n)+n for any natural number
n. The list of examples above should make this definition obvious; but because the examples are neither formal nor complete, we will try to prove that
f(n)=n*(n-1)/2 for natural numbers
Because we will want to state the claim that
f(n)=n*(n-1)/2, we will abbreviate this claim as
As we might have done with a piece of code, we will try to extend what we know one step at a time. Suppose we know that
P(n) is true for a particular value of
n, and we want to prove that
P(n+1) is true. Then we are saying that we know that
f(n)=n*(n-1)/2, and we want to prove that
f(n+1)=(n+1)*((n+1)-1)/2. We can do so as follows:
= (n+1)*n/2 [because (n+1)-1 is n]
= n*(n+1)/2 [because multiplication is commutative]
= n*((n-1)+2)/2 [because n+1 = (n-1) + 2]
= (n*(n-1))/2 + (n*2)/2 [because multiplication distributes over addition]
= (n*(n-1))/2 + n [because (n*2)/2 = n]
= f(n) + n [because we know that P(n) is true]
= f(n+1) [by definition]
In other words, whenever we know that
P(n) is true, we know that
P(n+1) is also true.
The well-ordering property of natural numbers allows us to conclude that
P(n) is true for every natural number
n. For suppose that it were not true. Then there would be a set of natural numbers for which
P(n) is false. Because natural numbers are well ordered, that set has a smallest element; call that element
k-1 is smaller than
k is the smallest element in the set we know that
P(k-1) is true. But that means that
P(k) must also be true, even though we started with the assumption that
P(k) is false. This contradiction stems from the assumption that
P(n) is false for some values of
n, so we have just proven that
P(n) is true for every natural number
We can summarize this proof technique as follows:
- We wish to prove that a claim
P(n)holds true for every natural number
- We prove that
- We prove that whenever
P(n)is true for a particular natural number
P(n+1)is also true.
- By completing these two subproofs, we have proven that
P(n)is true for every natural number
This example should help explain why I consider mathematical induction to be a kind of formal extrapolation: The second part of an induction proof is always of the form "If we have gotten to this point, we can prove that it is possible to go one step further." However, because the claims made in an induction proof are precise, we can rely on them in a way that we could not rely on the kind of extrapolation by handwaving that we discussed last week.
Induction proofs are slippery, and can be a nuisance to keep straight. Indeed, I had to correct several false starts while I was writing this article. As a result, many programmers are understandably reluctant to try to construct induction proofs for their programs. Fortunately, just as an induction proof is really just a particular kind of proof by contradiction that relies on the properties of natural numbers, there is a technique that we can use to reason about our programs that has an induction proof hidden behind it that we do not actually need to write down in detail.
That technique is called loop invariants. The idea behind it is to write down claims about what is happening in various parts of our code, then use those claims to prove (implicitly by induction) that no matter how many times a loop executes, the claims that we have made about it remain valid. We shall discuss this technique in more detail next week.