PROOF: (If part) Assume a - b. Then ач we observed above, x mod г = 0 for any integer x. Thus, a mod 6 = & mod a - 0 whenever a - b.

(Only-if part) Now, assume a mod i) - Ь mod a. The best technique is a proof by contradiction, so assume in addition the negation of the conclusion; that iS; assume a b. Then since a ~ bin eliminated, we have only to consider the cases a < b and b < a.

We already observed above that when a < b., we have a mod b = a and b mod a < a. Thus, these statements, in conjunction with the hypothesis a mod b = b mod a lets us derive a contradiction.

By symmetry, if u < a then b mod a - i and a mod b < b. We again derive a contradiction of the hypothesis, and conclude the only-if part is also true. We have now proved both directions and conclude that the theorem is true. □

1.4 Inductive Proofs

Tht!re is a special form of proof, c:alled inductive, that is essential when dealing with recursively defined objects. Many of the most familiar inductive proofs deal with integers, but in automata theory, we also need inductive proofs about sucli recursively defined concepts as trees and expressions of various sorts, such as the regular expressions that were mentioned briefly in Section 1,1.2. In this section, we shall introduce the subject of inductive proofs first with simple inductions on integers. Then, we show how to perfonn structural inductions on any recur.sively defined concept.

1.4.1 Inductions on Integers

Suppose we are given a statement 5(n), about an integer n, to prove. One common approach is to prove two things:

1. The basis, where we show S{i) for a particular integer i. Usually, г = 0 or г = 1, but there are examples where we want to start at some higher г, perhaps because the statement S is false for a few small integers.

2. The inductive step, where we assume n > i, where i is the basis integer, and we show that if S{n) then 5{n -I- 1).

Intuitively, these two parts should convince us that S{;n) is true for every integer n that is equal to or greater than the basis integer i. We can argue as follows. Suppose S{n) were false for one or more of those integers. Then tliere would have to be a smallest value of я, say j, for which S{j) is false, and yet j > i. Now j could not be i, because we prove in the basis part that S{i) is true. Thus, j must be greater than i. We now know that j - l>i, and S(j - 1) is true.

However, we proved in the inductive part that if n > i, then S{n) implies S(n + 1). Suppose we let n - j - I. Then we know from the inductive step that S{j -I) implies S{j]. Since we also know 5 (j - 1), we can conclude S{j).

Theorem 1.16: For all n > 0:

(Tt + l)(2n+l) =--- (Ы)

PROOF: The proof is in two parts: the basis and the inductive step; we prove each in turn.

BASIS: For the ba.sis, we pick n = 0. It might seem surprising that the theorem even makes sense for n - 0, since the left side of Equation (1.1) is when

n = 0. However, there is a general principle that when the upper limit of a sum (0 in this case) is less than the lower limit (1 here), the sum is over no terms and therefore the sum is 0, That is, X;Li 0.

The right side of Equation (1,1) is also 0, since Ox (0 + 1) x (2x 0 + l)/6 = 0. Thus, Equation (1.1) is true when n = 0.

INDUCTION: Now, assume n > 0, We must prove the inductive step, that Equation (1.1) implies the same formula with n + 1 substituted for n. The latter formula is

2 [n + l]([ + l] + l)(2[n + l] + l) 2)

We may simplify Equations (1.1) and (1.2) by expanding the sums and products on the right sides. These equations become:

i2 = (2n3 + 3n + n)/6 (1,3)

We have assumed the negation of what we wanted to prove; that is, we assumed S{j) was false for some j >i. In each case, we derived a contradiction, so we have a proof by contradiction that S{n) is true for all n > i.

Unfortunately, there is a subtle logical flaw in the above reasoning. Our assumption that we can pick a least j > г for which S(j) is false depends on our believing the principle of induction in the first place. That is, the only way to prove that we can find such a ; is to prove it by a method that is essentially an inductive proof. However, the proof discussed above makes good intuitive sense, and matches our understanding of the real world. Thus, wc generally take as an integral part of our logical reasoning system:

The Induction Principle: If we prove S(i) and we prove that for all n>i, 8{п) implies S(n + 1), then we may conclude S(n) for all n > г.

The following two examples illustrate tlie use of the induction principle to prove theorems about integers.

(2n +971 + 13n + 6)/6 (1.4)

We need to prove (1,4) using (1.3), since in the induction principle, these are statements S(n + 1) and S{n), respectively. The trick is to break the sum to n + 1 on the right of (1.4) into a sum to n plus the (n + I)st term, In that way, we can replace the sum to n by the left side of (1.3) and show that (1,4) is true. These steps are as follows:

Yi\+{n + 1) = (2n + + 13n + 6)/6 (1.5)

1=1

(2n + Зтг +n)/6 + (n + 2n + 1) = (2n + + 13n + 6)/6 (1.6)

The final verification that (1.6) is true requires only simple polynomial algebra on the left side to show it is identical to the right side, □

Example 1.17: In the next example, we prove Theorem 1,3 from Section 1,2.1, Recall this theorem states that Lf x > 4, then 2 > x. We gave an Informal proof based on the idea that the ratio x/2 shrinks as x grows above 4. We can make the idea precise if we prove the statement 2 > by induction on I, starting with a basis of a: - 4. Note that the statement is actually false for X < 4.

BASIS: И X 4, then 2 and x are both 16. Thus, 2 > 4? holds.

INDUCTION: Suppose for some x > 4 that 2= > x. With this statement as the hypothesis, we need to prove the same statement, with x + 1 in place of x, that is, 2[+J > [x + 1] These are the statements 5(x) and 5(x + 1) in the induction principle; the fact that we are using x instead of n as the parameter should not be of concern; x or n is just a local variable.

As in Theorem 1.16, we should rewrite S{x + 1) so it can make use of S{x). In this case, we can write 2(+! as 2 x 2. Since 5{x) tells us that 2* > x, we can conclude that 2+ = 2 x 2 > 2x.

But we need something different; we need to show that 2+ > (x + 1). One way to prove this statement is to prove that 2x > {a: + 1) and then use the transitivity of > to show 2=+ > 2x > (x + l). In our proof that

2x2 > (a;+ 1)2 (1.7)

we may use the assumption that x > 4. Begin by simplifying (1.7):

x>2x + \ (1.8)

Divide (1,8) by x, to get: