CSC/MAT 208 (Spring 2024)

Reading: Mathematical Induction and Other Variations

Mathematical Induction

So far, we have applied induction exclusively to lists. However, are there other structures that are inductive? It turns out that the natural numbers are the most common structure to perform induction over in mathematics. Now that we have some experience with inductive proof, let’s explore this foundational application of the technique in detail.

The Natural Numbers

Recall that we can apply induction to any inductively-defined structure, that is, a structure defined in terms of a finite set of (potentially recursively-defined) cases. How can we define the natural numbers, i.e., non-negative integers, in this manner? One natural choice is to start at zero, the smallest natural number, and work our way up.

Since it is the smallest natural number, zero seems to serve as a base case, similar to the empty list. However, how can we characterize a non-zero natural number in terms of another natural number? Consider the number seven, written in unary, i.e., tally marks:

\[ \underbrace{1111111}_{7} \]

Do we see a smaller natural number nested somewhere inside of seven? The unary representation makes this explicit:

\[ 1\underbrace{111111}_{6}. \]

Seven can be thought of as six but with one extra mark! In general, any non-zero natural number \(k\) is one more than \(k - 1\). This fact leads to the following definition of the natural number as an inductive structure:

Definition (Natural Number): a natural number is either:

  • Zero, or
  • The successor, \(k + 1\) of some natural number \(k\).

With lists, we use list functions list to query and break apart the structure:

We do the same thing with natural numbers, albeit with functions that you have seen before but may not have thought of in this context:

Exercise (Primitive Zero): using the inductive definition of a natural number, write a recursive function (plus n1 n2), which returns the result of adding n1 and n2. In your implementation, you are only allowed to use:

  • Conditionals,
  • zero?,
  • A recursive function call,
  • Subtraction by one, i.e., (- n 1).

(Note: This isn’t how we would implement plus in a real system. This is merely an exercise in using the inductive definition of the natural numbers.)

Induction Over the Natural Numbers

Now that we have an inductive definition of the natural numbers, we can:

  1. Perform recursive operations over the natural numbers, and
  2. Prove properties involving natural numbers by using inductive reasoning.

Of course, not having a formal inductive definition didn’t stop us from writing recursive functions over the natural numbers. Similarly, with lists, having this definition in-hand can give us more confidence that we are doing the right thing when we begin programming.

With that being said, let us focus on the second activity for the remainder of this section: writing inductive proofs with natural numbers. Induction over the natural numbers is so common that we give it a generic Consider the following canonical recursive function over the natural numbers:

(define factorial
  (lambda (n)
    (if (zero? n)
        1
        (* n (factorial (- n 1))))))

And the following claim about factorial asserts that factorial produces only positive, non-negative, non-zero results.

Claim: for any natural number n, (< 0 (factorial n)).

Note that the definition of factorial reflects the structure of the inductive definition of a natural number. This strongly suggests that we ought to prove this claim using induction. Let’s go ahead and try it, following the same style of proof introduced for lists, but instead invoking the inductive definition of natural numbers.

Proof. By induction on n.

  • n is zero. …

  • n is non-zero. …

The case analysis of our inductive is similar to that of lists. The “base case” for a natural number is when that number is zero. The “inductive case” for a natural number is when that number is non-zero. Note that because a natural number cannot be negative and the inductive case number is not zero, this number must be a positive integer. If we call that natural number k, then we know that k-1 is well-defined (since k is at least 1).

The proof of the base case follows from evaluation:

  • n is zero. (factorial n) -->* 1 and so (< 0 (factorial 0)) -->* (< 0 1).

The proof of the recursive case also follows from evaluation, invoking the induction hypothesis, and collecting assumed constraints about the different pieces of the inequality.

  • n is non-zero. We assume our induction hypothesis:

    Induction Hypothesis: (< 0 (factorial (- n 1)))

    And try to prove:

    Goal: (< 0 (factorial n))

    The left-hand side of the equivalence evaluates as follows:

         (< 0 (factorial n))
    -->* (< 0 (* n (factorial (- n 1))))

    Our induction hypothesis tells us that (< 0 (factorial (- n 1))), i.e., (factorial (- n 1)) is a strictly positive integer. Furthermore, we know that n is non-zero, so n is also a strictly positive integer. Therefore, we know that their product (* n (factorial (- n 1))) is also strictly positive and thus (< 0 (* n (factorial (- n 1)))).

Note that in the inductive case, we acquire the following assumptions:

These two facts combined with the knowledge that two multiplying two positive numbers produces a positive number tell us that the body of factorial produces a strictly positive result.

Exercise (Racket Sum): Consider the following Racket definition.

(define sum
  (lambda (n)
    (if (zero? n)
        0
        (+ n (sum (- n 1))))))

Prove the following claim using mathematical induction.

Claim: for all natural numbers n, (sum n) ≡ (/ (* n (+ n 1)) 2).

(Hint: when manipulating the right-hand side of the equation, you will likely need to employ several arithmetic identities to get the goal into a form where the induction hypothesis applies. You might find it helpful to rewrite the Racket expression to infix notation, , \(\frac{(n+1)n}{2}\), to see how to manipulate the expression.)