Induction

This far in this book, we have considered a number of ways of proving theorems. In Chapter 3, we saw
the theorems of propositional logic could be established via truth tables, substitution, equational
reasoning, or natural deduction. When we considered predicate logic, we saw that the techniques of
equational reasoning and natural deduction could be extended from propotional logic to predicate logic.
Furthermore, we saw that we could establish whether two sets (or relations, or functions or sequences)
are equivalent by using our system of equational reasoning. Together, the techniques of equational
reasoning and natural deduction allow us to reason about, and prove properties of, most formal
descriptions that we may develop.

If, on the other hand, we wished to prove some property of all sequences of a given type, or all natural
numbers, then we need a different technique-that technique is called induction. Induction is a powerful
mathematical technique, which is central to many computing applications. Furthermore, it is closely
related to recursion, which we met in Chapter 9 and 10. Indeed, induction is often the only means of
establishing that certain classes of recursive algorithms are correct.

In this chapter we consider two types of induction : mathematical induction, which allows us to establish
properties of all natural numbers, and structural induction, which allows us to establish certain
properties of all elements of a given inductively-defined type (such as, for example, sequence). We
consider mathematical induction to programming.

11.1 Mathematical Induction

In Chapter 2 we considered the topic of Peano arithmetic—atreatment of the natural numbers originally
proposed by Giuseppe Peano. There, we saw that the natural numbers can be defined in terms of five
axioms, the first four of which we considered in Chapter 2. These were started as follows.

1. 0 is a natural number.

2. If x is a natural number, then x + 1 is also a natural number.

3. There is no natural number, z, such that z + 1 = 0.

4. Given two natural number x and y, if x + 1 = y + 1 then x = y.

Peano’s fifth axiom, which we consider now, can be started in the following way.

If one can prove that if a property holds for some natural number x then it holds for x + 1, and if
you can prove that the same property holds for 0, then the property will hold for all natural
numbers.

That is, given some property p, if we can establish that p(0) holds, and if we can also establish that p(n)
=> p (n + 1) holds for every natural number n, then it follows that p(n) holds for all natural numbers. We
can write this axiom in the style of our natural deduction rules as follows.
[mathematical induction]

Thus the proof that such a property holds for all natural numbers is divided into the proof of two case:
the base case—in which we establish that the property holds for 0- and the inductive step—in which we
establish that if the property holds for n, then also holds for n + 1. This is achieved by assuming the
property holds of n-- this is termed the inductive hypothesis and using this assumption to prove that the
property holds of n + 1. We may state the principle of mathematical induction formally as follows.

Assume some property p, which is either true or false for each natural number. If

1. p(0) is true and

2. p(n) => p (n + 1) is true,

Then p is true for all natural numbers.

We start with a relatively simple example.

Example 11.1 We wish to prove that the theorem

Holds.

To prove every natural number n is less than n + 1, we have to prove the base case and the
inductive step. We consider the base case first. Here, we have

0<0+1

Which is obviously true, by definition of < and +.

Next, we consider the inductive step. To prove this, we first assume that the theorem is true for
some value x, i.e., that

X<x+1

This is the inductive hypothesis. From this, we have to prove

(x + 1) < (x + 1) + 1

By arithmetic, if m < n the it follows that m + 1 < n + 1. Given that the inductive hypothesis states that x
< x + 1, we may use this to conclude

(x + 1) < (x + 1) + 1

As we have established both the base case and the inductive step, we can conclude that
Holds.

Many discrete mathematic texts motivate mathematical induction by means of falling dominoes. This
analogy is given by considering a row of dominoes lined up one behind another. If the dominoes have
been correctly spaced, the knocking over the first one will result in the second one being knocked over,
which will result in the third one being knocked over, and so on. This establishes that all of the dominoes
will be knocked over. The way that mathematical induction works is that if the theorem holds for 0, the
it holds for 1, then it holds 2, if it holds for 2, then it holds for 3, and so on. This analogy is certainly
appropriate for the above example.

We now consider a second example.

Example 11.2 We can establish that the formula

Holds for all natural numbers n, by means of an inductive proof. To convince oneself of the validity of
this formula consider the case of n = 3 which is given below.

As a further example, consider the case of n = 5 which is given below.

To establish the base case of n = 0 we arrive at

Which of course is true

We attempt to establish the inductive step by first assuming that the theorem is true for some value x,
i.e.,

This is the inductive hypothesis. The inductive step is proved if we can establish that

Follows from

When n = x + 1, the left-hand side of the equation is given by

1 + 2 + 3 + ... + x + (x + 1)

The inductive hypothesis allows us to rewrite this as

We can continue with our proof as follows

x × ( x +1 )
2
x
+ ( x+1 )=( x+ 1 ) × +1
2 ( )
( x+1 ) × ( x +2 )
¿
2

( x+1 ) × ( ( x +1 ) +1 )
¿
2

As such, we have proved the inductive step.

Given that the base case and the inductive step both hold, we can conclude that

Holds for all natural numbers, n.