Integers as Recursively Defined Concepts

We mentioned that inductive proofs are useful when the subject matter is recursively defined. However, our first examples were inductions on integers, which we do not normally think of as recursively defined, However, there is a natural, recursive definition of when a number is a nonnegative integer, and this definition does indeed match the way inductions on integers proceed: from objects defined first, to those defined later.

BASIS: 0 is an integer.

INDUCTION: Tf П is an integer, then so is nH-1.

x>2+- (1,9)

Since X > 4, we know l/x < 1/4. Thus, the left side of (1-9) is at least 4, and the right side is at most 2.25. We have thus proved the truth of (1.9), Therefore, Equations (1-8) and (1-7) are also true. Equation (1.7) in turn gives us 2x- >{x + 1) for x > 4 and lets us prove statement S{x + 1), which we recall was 2*+> (x + l)-. □

1.4.2 More General Forms of Integer Inductions

Sometimes au inductive proof is made possible only by using a more general scheme than the one proposed in Section 1.4,1, where we proved a statement S for one basis value and then proved that if S{n) then 5(n+1). Two important generalizations of this scheme are:

1. We can use several basis cases. That is, wc prove S{i),S(i + l),.. S(J) for some j > i-

2. In proving 5(n 4-1); we can use the truth of all the statements

S{i),S{i+l),...,Sin)

rather than just using S(n). Moreover, if we have proved basis cases up to S{j), then we can assume n > j, rather than just n > i.

The conclusion to be made from this basis and inductive step is that S{n) is true for s\\ n>i.

Example 1-18: The following example will illustrate the potential of both principles. The statement S{n) we would like; to prove is that if n > 8, then n can be written as a sum of 3s and 5s. Notice, incidentally, that 7 cannot be written as a sum of 3s and 5s.

Example 1.20: Here is another recursive definition. This time we define expre.?.sions using the arithmetic operators + and *, with both iminbers and variables allowed a.s operands.

BASIS: Any nmnber or letter (i.e., a variable) is an expression.

INDUCTION: If E and F are expressi(ms, then so are E + F, E * F, and (E).

For example, both 2 and x are expressions by the basis. The inductive stej) tells ns X + 2, (x + 2), and 2* (x + 2) are all fixpressions. Notice how each of these expressions depends on the previous ones being expres.sions. □

BASIS: The basis cases are 5(8), S{9), and 5(10). The proofs are 8 3 + 5, 9 3 + 3 + 3, and 10 = 5 + 5, respectively.

INDUCTION: .Assume that 7г > 10 and that 5(8), 5(9),..., 5(n) are true. We must prove S{n + 1) from these given facts. Our strategy is to subtract 3 from n + 1, observe that this number must be writable as a sura of 3s and 5s, and add one more 3 to the sum to get a way to write n + 1.

More formally, observe that n - 2 > 8, so we may assume S{n - 2). That is, n - 2 - 3n + 56 for some integers a and b. Then h + 1 = i + ia + 5b, so n + 1 can be written as the sum of a + 1 3s and b 5s. That proves S{n + 1) and concludes the inductive step. □

1.4.3 Structural Inductions

In automata theory, there are several recursively defined structures about which we need to prove statements. The familiar notions of trees and expressions are important examples. Like inductions, all recursive definitions have a basis case, where one or more elementary structures are defined, and an inductive step, where more complex structures are defined in terms of previously defined structures.

Example 1.19 : Here is the recursive definition of a tree:

BASIS: A single node is a tree, and that node is the root of the tree.

INDUCTION: If Tj, ,..., Tj are trees, then we can form a new tree as follows:

1. Begin with a new node Л, which is the root of the tree.

2. Add copies of all the trees Tj ,T2,... ,Ti,.

3. Add edges from node N to the roots of eat:h of the trees Ti,T2, .,Tk.

Figure 1.7 shows the inductive construction of a tree w-ith root from к smaller trees. □

Figure 1.7: Inductive construction of a tree

Intuition Behind Structural Induction

We can suggest informally why structural induction is a valid proof method. Imagine the recursive definition establishing, one at a time, that certain structures Xi,X-2,..- meet the definition. The basis elements come first, and the fact that Л,- is in the defined set of structures can only depend on the membership in the defined set of structures that precede Xi on the list. Viewed this way, a structural induction is nothing but an induction on integer n of the statement (X ), This induction may be of the generalized form discussed in Section 1.4.2, with multiple basis cases and an inductive step that uses all previous instances of the statement. However, we should remember, as explained in Section 1.4.1, that this intuition is not a formal proof, and in fact we must assume the vafidlty this induction principle as we did the validity of the original induction principle of that section.

When we have a recursive definition, we can prove theorems about it using the following proof form, which is called structural induction. Let S{X) be a statement about the structures X that are defined by some particular recursive definition.

1. As a basis, prove S{X) for the basis structure(s) X.

2. For the intluctive step, take a structure X that the recursive definition says is formed from li, yj,..., У- -Assume that the statements 5(70,5(2),...,5(П), and use these to prove S{X).

Our conclusion is that 3{Х) is true for all X. The next two theorems are examples of facts that can be proved about trees and expressions.

Theorem 1.21: Every tree has one more node than it has edges.