The Seesat language has the singleletter word $A.$
Longer words are built by applying a sequence of the following rules: Rule $r_1$
says that if $x$
is a word then $Ax$
is a word; Rule $r_2$
says that if $x$
and $y$
are words then $Bxy$
is a word. For example, the sequence $r_1(r_2(A,A))$
yields the word $ABAA.$
(i) Give a valid sequence of rules that yields the word $AAABBAAA.$
(ii) Write $N_A (x)$
and $N_B(x)$
for the number of $A$
and $B$
letters in the word $x$
respectively. By expressing $N_A(x)$
and $N_B(x)$
in connection with the rules, prove mathematically that $N_A(x) > N_B(x)$
for any word $x$
in the language.

 Prove, by mathematical induction, that
$\sum_{k=1}^{n}k^2 = \frac{n(n+1)(2n+1)}{6}.$
 Prove, by mathematical induction, that

In simple terms, what do rule
$r_1$
and$r_2$
do? 
How many times should you apply rule
$r_2$
to get$AAABBAAA?$

If
$x$
is a word in the language, express$N_A(r_1(x))$
in terms of$N_A(x).$

Similarly, find
$N_B(r_1(x)),$
$N_A(r_2(x,y))$
and$N_B(r_2(x,y)),$
with$y$
being another word in the language. 
What assumption do you need to make in order to claim that
$N_A(r_1(x)) > N_B(r_1(x))$
and$N_A(r_2(x,y)) > N_B(r_2(x,y))?$

Is your assumption valid? Hint: Consider
$N_A(A)$
and$N_B(A).$

Try proving by induction.

… more specifically, induction over each of the rules.

Starting with a singleletter word
$A,$
the rules allow us to create new words from existing ones. Rule$r_1$
lets us add an$A$
in front of a word, while rule$r_2$
combines two words and adds a$B$
in front. There are$2$
$B$
s in$AAABBAAA,$
thus we must apply rule$r_2$
twice: first to have$BAA,$
then$BBAAA.$
Hence, the sequence of rule is$r_1(r_1(r_1(r_2(r_2(A,A),A)))).$
In order to prove that
$N_A(x) > N_B(x)$
for any word$x$
in the language, we use induction over each of the rules. The base case is simple,$N_A(A) = 1 > 0 = N_B(A).$
For the inductive step, our assumption is that$N_A(x) > N_B(x)$
and$N_A(y) > N_B(y),$
for some words$x$
and$y$
in the language. We have to show that$N_A(r_1(x)) > N_B(r_1(x))$
and$N_A(r_2(x,y)) > N_B(r_2(x,y)):$

$r_1:$
$N_A(r_1(x)) = 1 + N_A(x) > N_B(x) = N_B(r_1(x))$

$r_2:$
$N_A(r_2(x,y)) = N_A(x) + N_A(y) > 1 + N_B(x) + N_B(y) = N_B(r_2(x,y)).$
Hence,
$N_A(x) > N_B(x)$
for all words$x$
in the language. 