# Babble Strings and Induction

I normally don't have any problems doing proofs by induction. However, in this case I'm struck because I have difficulty seeing how exactly I should approach the problem and construct the proof. Would anyone be so kind as to help me out of this abyss of ignorance and enter your world of enlightenment?

Define a set of "babble strings" inductively, as follows:

• $\textbf{"ba"}$ is a babble string.
• If $\textbf{s}$ is a babble string, so is $\textbf{"ab"}$$\cdot$$s$.
• If $\textbf{s}$ and $\textbf{t}$ are babble strings, so is $\textbf{s$\cdot$t}$.

Prove by induction that every babble string has the same number of a's and b's, and that every babble string ends with an "$\textbf{a}$".

• If s has the same number of a’s and b’s and ends in a, is this also true of ab·s? Yes: if s has, say, $n$ a’s and $n$ b’s, then ab·s has $n+1$ of each letter, and the last letter of ab·s is evidently the last letter of s, which by hypothesis is a.