• An Example
• The Induction Principle
• Another Example
• Yet Another Example
• Proving Recursive Programs Correct

For more examples, look at the Induction Examples Handout

Induction is a method of proving statements about inductively defined sets. A set is inductively defined when it is generated from some base elements using some set of constructor operations.

The most common example of an inductively defined set is the set of nonnegative integers N={0,1,2,...}, also called the natural numbers. This set can be generated from the base element 0 and the successor function inc, where inc(x) = x+1. Induction over the natural numbers is often called mathematical induction.

There are many inductively defined sets other than the natural numbers, such as lists, trees, and Scheme expressions. Later in the semester we will look at induction over such sets. This type of induction is often called structural induction, but the principle is the same.

An Example

Induction is an example of logical abstraction. It essentially allows us to do infinitely many concrete arguments in a single abstract argument. This is very similar to the idea of functional abstraction. Recall that after getting tired of typing the expressions (* 3 3) ... (* 16 16) ... (* e e) ... (* 27717 27717) ... (* BIG-HAIRY-EXPRESSION BIG-HAIRY-EXPRESSION) etc., we packaged up the common part of these expressions using functional abstraction:

(define square
   (lambda (x) (* x x)))

In a sense, square packages up infinitely many potential computations (* x x) in a single finite box.

Now we can do the same sort of abstraction with logical arguments. For example, suppose we had no built-in integer multiplication and had to build it using addition. Consider the following recursive program for multiplying nonnegative integers:

(define mult (lambda (m n)
  (if (zero? n)
      0
      (+ m (mult m (dec n))))))

In arguing that this program is correct, we might go through the following thought process:

• It works if the second input is 0. For any integer A,

• (mult A 0)
  ==> ((lambda (m n)
        (if (zero? n) 0 (+ m (mult m (dec n))))) A 0)
  ==> (if (zero? 0) 0 (+ A (mult A (dec 0))))
  ==> 0
  

• If the second input is 1, it calls itself recursively on input 0. But we just argued that it works for 0, and if we supply the correct answer in the recursive call, we can argue that it works for 1.

• (mult A 1)
  ==> ((lambda (m n)
        (if (zero? n) 0 (+ m (mult m (dec n))))) A 1)
  ==> (if (zero? 1) 0 (+ A (mult A (dec 1))))
  ==> (+ A (mult A (dec 1)))
  ==> (+ A (mult A 0)) <-- here's where we supply the correct
  ==> (+ A 0)          <-- answer from the recursive call
  ==> A
  

• If the second input is 2, it calls itself recursively on input 1. But we just argued that it works for 1, and if we supply the correct answer in the recursive call, we can argue that it works for 2.

• (mult A 2)
  ==> ((lambda (m n)
        (if (zero? n) 0 (+ m (mult m (dec n))))) A 2)
  ==> (if (zero? 2) 0 (+ A (mult A (dec 2))))
  ==> (+ A (mult A (dec 2)))
  ==> (+ A (mult A 1)) <-- here's where we supply the correct
  ==> (+ A A)          <-- answer from the recursive call
  ==> 2A
  

• If the second input is 3, it calls itself recursively on input 2. But we just argued that it works for 2, and if we supply the correct answer in the recursive call, we can argue that it works for 3.

• (mult A 3)
  ==> ((lambda (m n)
        (if (zero? n) 0 (+ m (mult m (dec n))))) A 3)
  ==> (if (zero? 3) 0 (+ A (mult A (dec 3))))
  ==> (+ A (mult A (dec 3)))
  ==> (+ A (mult A 2)) <-- here's where we supply the correct
  ==> (+ A 2A)         <-- answer from the recursive call
  ==> 3A
  

and so on, ad nauseam.

Now note that the argument for the base case 0 is different, but after that the arguments all look the same. It's only the numbers that are different. Using logical abstraction, we can do all these infinitely many cases at once.

• For any B > 0, the program calls itself recursively on input B-1. Let's assume that we have shown that it works for B-1. If we supply the correct answer in the recursive call, we can argue that it works for B.

• (mult A B)
  ==> ((lambda (m n)
        (if (zero? n) 0 (+ m (mult m (dec n))))) A B)
  ==> (if (zero? B) 0 (+ A (mult A (dec B))))
  ==> (+ A (mult A (dec B)))
  ==> (+ A (mult A B-1))  <-- here's where we supply the correct
  ==> (+ A A(B-1)) <-- answer from the recursive call
  ==> AB
  

Note that we were able to make this argument purely symbolically, by using a symbol B to stand for any positive number, without knowing what B is. The argument is therefore valid for any B > 0. We could in principle string these arguments together to get up as high as we like.

The Induction Principle

The induction principle says that in order to prove that a property is true of all natural numbers, it suffices to do the following:

1. State what variable you are doing induction on.
2. Express the property you are trying to prove as a property P of that variable.
3. Prove that P is true of 0. This step is called the basis of the induction.
4. Prove that if P is true of all numbers less than n, then P is also true of n. This is called the induction step. This argument is made without any assumption of what n is. It is usually just a symbolic argument in terms of the symbol n (or some other symbol standing for an arbitrary natural number).
5. The assumption that P is true of all numbers less than n is called the induction hypothesis. In all inductive proofs, it is good practice to state the induction hypothesis explicitly and indicate explicitly where you use it in your proof that P holds for n. We will expect you to do so.

One way to think about mathematical induction is that it allows us to show that we can climb as far as we want on a ladder, by first showing that we can get on the bottom rung (the basis), and then showing that if we have gotten to some rung (any rung), then we can get to the next one (the induction step). In effect induction provides us with infinitely many results by doing only a finite amount of work (although it may seem like an infinite amount of work when you are first learning how!).

In a proof by induction, we first show that the statement is true for the "smallest" values of our inductively defined set, which for the natural numbers is just 0. This is the basis. We then want to show that the statement holds for any arbitrary n > 0. We don't get assume anything about n except that it is positive, but we do get to assume that the statement holds for all values less than n. This is the induction step.

Once we have done these things, we are done: the induction principle allows us to conclude that the property is true for all n.

Another Example

Here is a simple example of the use of induction. We want to prove that the sum of the first n squares is n(n+1)(2n+1)/6.

The expression

is mathematical shorthand for "the sum for i running from 0 to n of i²", or

0² + 1² + 2² + ... + n²

We wish to show that this property is true for all n. The variable we will do induction on is k.

Basis

We must show that the property is true of 0. Substituting 0 for n, we need to show

which simplifies to 0^2 = 0, so we are done with the basis.

Induction Step

We get to assume that the property holds for k, and we need to show that under this assumption it holds for k+1. Thus our induction hypothesis is

and we wish to prove

We break this expression up in such a way that allows us to use the induction hypothesis. In this case, this means expressing the sum as the sum of (1)the first k terms and (2) the last (k+1st) term:

By induction principle, we may now conclude that the property holds for all n>=0.

Yet Another Example

Let us show that for the set G={8,9,10,...}, each element of G is a sum of 3's and 5's. (Mathematically we say that these integers are a "linear combination" of 3 and 5.)

The variable we are doing induction on is n.

The property we are trying to prove is that for every n in the set G={8,9,10,...}, there exist nonnegative integers u and v such that n = 3u + 5v.

Basis

The smallest element of our set is 8, and 8=3+5. That was easy.

Induction step

Assuming that n is a sum of 3's and 5's, we will show that n+1 is also. Thus our induction hypothesis is n = 3u + 5v for some u and v.

On the other hand, if v = 0, then u >= 3, because the smallest number in G is 8. Then in this case we get
n+1 = 3(u-3) + 5*2.

Proving Recursive Programs Correct

Recursion and induction are closely related. Induction is often used to show that a recursive procedure computes the correct answer. We saw one example of this above.

This use of induction relies on the substitution model and mathematical induction. Consider the following procedure fact for computing n! = n(n-1)(n-2)...2 1.

(define fact (lambda (n)
  (if (= n 1)
      1
      (* n (fact (dec n)))))

We will do induction on A, where A stands for any positive integer.

The property we wish to prove is

Basis

For the basis, we wish to show that (fact 1) ==> 1. >From the substitution model we know that

(fact 1)
==> ((define fact (lambda (n))
      (if (= n 1) 1 (* n (fact (dec n))))) 1)
==> (if (= 1 1) 1 (* 1 (fact (dec 1))))
==> 1
   

so we are done with the basis.

Induction step

Assuming that (fact A) ==> A!, we wish to show that (fact A+1) ==> (A+1)!.

(fact A+1)
==> ((define fact (lambda (n))
      (if (= n 1) 1 (* n (fact (dec n))))) A+1)
==> (if (= A+1 1) 1 (* A+1 (fact (dec A+1))))
==> (* A+1 (fact (dec A+1)))
==> (* A+1 (fact A))
==> (* A+1 A!)  <-- here we used the induction hypothesis
==> (A+1)!
   

In general we will not require proofs that contain this much detail. The level of detail in this example illustrates, however, that the process is quite mechanical, and could in principle be performed by a machine. The automatic verification of programs (checking that they meet a given specification) is an active area of research.

Last update:  01/19/00 11:35 PM by BRB