PROOF: The formal statement S{T) we need to prove by structural induction is: if Г is a tree, and T has n nodes and e edges, then n = e + 1.

BASIS: The basis case is when T is a single node. Then n - 1 and e = 0, so the relationship n - e + 1 holds.

INDUCTION: Let T be a tree built by the inductive step of the definition, from root node and к smaller trees Ti,Ti,... ,Tk. We may assume that the statements 5(Г,) hold for г = 1,2,..., A. That is, let Г,- have Tii nodes and a edges; then гц - ei + 1.

The nodes of Г are node N and all the nodes of the Tjs. There are thus

1 + Til + П2 H-----h njt nodes in T. The edges of T aie the к edges we added

explicitly in the inductive definition step, plus the edges of the Tjs. Hence, T has

k + ei+e-i + --- + ek (1.10)

edges. If we substitute ej + 1 for Ui in the coimt of the number of nodes of T we find that T has

1 + [ei + 1] + [62 + 1] + + [efe + 1] (1.11)

nodes. Since there are к of the +1 terms in (1.10), we can regroup (1.11) as

k + l + ei+e-z + - + Ck (1.12)

This expression is exactly 1 more than the expression of (1.10) that was given for the number of edges of T. Thus, T has one more node than it has edges. □

Theorem 1.22 : Every expression has an equal number of left and right parentheses.

PROOF: Formally, we prove the statement 5(G) about any expression G that is defined by the recursion of Example 1.20: the numbers of left and right parentheses in G are the same.

BASIS: If G is defined by the basis, then G is a number or variable. These expressions have 0 left parentheses and 0 right parentheses, so the numbers are equal.

INDUCTION: There are three rules whereby expression G may have been constructed according to the inductive step in the definition:

\. G = E + F.

2. G = E*F.

3. G{E).

We may assume that S(E) and S{F) are true; that is, E has the same number of left and right parentheses, say n of each, and F likewise has the same number of left and right parentheses, say m of each. Then we can compute the numbers of left, and right parentheses in G for each of the three cases, as follows:

1. If G = E + F, then G has n + m left parentheses and n + m right parentheses; n of each come from E and m of each come from F.

2. If G = F * F, the co\mt of parentheses for G is again n + m of each, for the same reason as in case (1).

3. IfG = (F), then thereare 71+1 left parentheses in G - one left parenthesis is explicitly shown, and the other n are present in E. Likewise, there are n + 1 right parentheses in G: one is explicit and the other n are in E.

In each of the three cases, we see that the numbers of left and right parentheses in G are the same. This observation conipletes the inductive step and completes the prooL □

1.4.4 Mutual Inductions

Sometimes, we cannot prove a single statement by induction, but rather need to prove a group of statements Si{n},S2{n), ...,Sk{n) together by induction on n. .Automata theory provides many such situations. In Example 1.23 we sample the common situation where we need to explain what an automaton (ioes by proving a group of statements, one for each state. These statements tell under what sequences of inputs the automaton gets into each of the states. Strictly speaking, proving a group of statements is no different from proving the conjunction (logical AND) of all the statements. For instance, the group of statements Si(n),S-2in)i.. .,Sk{n) could be replaced by the single statement Si (n) AMD S-2 (n) AND AND Sk (n). However, when there are really several independent statements to prove, it is generally less confusing to keep the statements separate and to prove them all in their own parts of the basis and inductive steps. We call this sort of proof mutual induction. An example will illustrate the necessary steps for a mutual recursion.

Example 1.23: Let us revisit the on/off switch, which we represented as an automaton in Example 1.1. The automaton itself is reproduced as Fig. l.S. Since pushing the button switches the state between on and off., and the switcli starts out in the ojf state, we expect that the following statements will together explain the operation of the switch:

Si(n): The automaton is in state ojf&Uer n pushes if and ordy if n is even.

52(n): The automaton is in state on after n pushes if and only if n is odd.

Push

Figure 1,8: Repeat of the automaton of Fig. 1.1

We might suppose tliat Si impHes S-i and vice-versa, since we know that a number n cannot be both even and odd. However, w4iat is not always true about an automaton is that it is in one and only one state. It happens that the automaton of Fig, 1,8 is always in exactly one state, but that fact must be proved as part of the mutual induction.

We give the basis and inductive parts of the proofs of statements Si(n) and S-iin) below. The proofs depend on several facts about odd and even integers: if we add or subtract 1 from an even integer, we get an odd integer, and if we add or subtract 1 from an odd integer we get an even integer,

BASIS: For the basis, we choose тг - 0. Suice there are two statements, each of which must be proved in both directions (because S\ and S2 are each if-and-only-if statements), there are actually four cases to the basis, and four cases to the induction as well.

1. [Si; If] Since 0 is in fact even, we must show that after 0 pushes, the automaton of Fig, 1,8 is in state off. Since that is the start state, the automaton is indeed in state off after 0 pushes.

2. [Si] Only-if] The automaton is in state off after 0 pushes, so we must show that 0 is even. But 0 is even by definition of even, so there is nothing more to prove.

3. [So; If] The hypothesis of the if part of S-2 is that 0 is odd. Since this hypothesis Я is false, any statement of the form if Я then C is true, as we discussed in Section 1.3.2. Thus, this part of the basis also holds.

4. [2; Only-if] The hypothesis, that the automaton is rn state on after 0 pushes, is also false, since the only way to get to state on is by following an arc labeled Push, which requires that the button be pushed at least once. Since tlie hypothesis is false, we can again conclude that the if-then statement is true.

INDUCTION: Now, we assume that 5i (n) and Snin) are true, and try to prove Si{n + 1) and S2(n + 1). Again, the proof separates into four parts.

Push

Start