Trees Problem 2

Strengthening the claim

Suppose you are writing your inductive hypothesis. You start with a tree T generated by grammar G, and divide it at the root. You've got one or two subtrees (depending on which case you are looking at). However, some of these subtrees don't technically match grammar G because their root has label B rather than S. That's awkward.

So, let's make a grammar G' which is just like G except that B is also allowed as a start symbol. G' covers a wider set of trees, including all those covered by G. So anything we prove about all trees in G' will also hold for all trees in G.

But the claim doesn't hold for all trees in G'. Not quite. If the root of T has label B, then L(T) isn't congruent to 1 (mod 3). Is it congruent to something else (mod 3)? Figure out what constraint holds for L(T) in this case.

Now, state a modified claim that includes both trees with root label S and trees with root label B. Prove that new claim by induction.

More hints

Your modified claim will probably consist of two pieces, each applying to one particular case of what the root label might be. Long and clumsy, but mathematically precise.

When doing the inductive step, just look at the root and the subtrees immediately under it. Do NOT open up these subtrees to find smaller subtrees inside them. Instead, use the inductive hypothesis.