[Cse321] Clarification on structural induction

venkat@cs.washington.edu

Hi,

Even though this is somewhat last minute for the midterm, I still
thought I'll clarify structural induction a little bit, especially w.r.t
string problems, since the example worked out in the review session
apparently confused some people. (Thanks to those who raised this in my
office hours today!)

Let us talk about that same problem (numbered 18). A set S is defined as
follows:

 Basis: a is in S and ab is in S
Recursive step: If x and y are in S, then xy is in S, and axb is in S.

Your goal is to prove that every string in S has at least twice as many
a's as b's. Let us call this property P, so P(x) if and only if x has at
least as many a's as b's. So we want to prove P(x) for every x in S.

Structural induction says that to establish this it suffices to do the
following two steps:

(i) Check that P(x) is satisfied for the x's places in S in the basis
step. In this case, this amounts to checking P(a) and P(ab), both of
which are clearly true.

(ii) Prove that if P(x) and P(y) are true, then the new strings places
in  S by the recursive rule also satisfy P. In this case, this amounts
to checking two things (since there are two recursive rules):

 * P(x) and P(y) implies P(xy). This is easily checked since the number
of a's in  xy is the sum of number of a's in x and y, which by the
structural induction hypothesis (namely P(x) and P(y)) is at least as
big  as the sum of number of b's in x and y, which in turn clearly
equals the number of b's in xy.

 * P(x) implies P(axb). This is again clear, since axb just has one more
a as well as b than x, and so if x had at least as many a's as b's, then
so must axb.

To write the above better, it might help to introduce variables
measuring the number of a's and b's in x and y and writing the new
number of a's and b's in the new strings (that is xy and axb in the two
cases) in terms of these variables. Then just check that the number of
a's remains at least as large as the number of n's, and you are done!

So, again, if you just perform the above two steps properly, you are
done. There is no need to perform induction on the length of the string.
What is implictly happening here is an induction on the number of steps
required to place a certain string in S, but you don't need to argue at
that level and can just use structural induction as a valid principle
directly in your proofs.

Hope this helps those who were confused about this. Once you understand
it, this is actually very natural and simple, but then the same can be
said of everything we will cover in this class.

See you in class tomorrow; all the best!

Venkat

_______________________________________________
Cse321 mailing list
Cse321@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/cse321