# How to use induction to prove this argument?

It is obvious that this grammar will always return an equal number of both a's and b's. But I was wondering how to prove it using induction? I understand induction, but I was finding it hard to apply to this situation.

The ε character denotes an empty.

-
To apply induction, you need numbers somewhere. Where are they going to come from? We need a parameter that is a number. Typically, we use the length of something. (For example, length of words.) Do you see how to proceed? – Andrés E. Caicedo May 10 '13 at 23:06

Let $P(n)$ be the assertion that if $w\in\{S,T,a,b\}^*$ can be derived in $n$ steps, then $|w|_a=|w|_b$, where $|w|_x$ is the number of occurrences of the letter $x$ in $w$.
Initially, when you begin a derivation, you have the string $S$, and $|S|_a=0=|S|_b$, so $P(0)$ is true. Suppose that $P(n)$ holds for some $n\ge 0$, and let $w\in\{S,T,a,b\}^*$ be derivable in $n+1$ steps. Suppose that the last step is $v\Rightarrow w$. Then $v$ is derivable in $n$ steps, so $|v|_a=|v|_b$. Moreover, $v$ must be of the form $xSy$ with $x,y\in\{S,T,a,b\}^*$ or of the form $xTy$ with $x,y\in\{S,T,a,b\}^*$, since a further step is possible. Now see if you can use the induction hypothesis $P(n)$ to finish the induction step by showing that $|w|_a=|w|_b$; I’ve done so below, in the spoiler-protected block.
If $v=xSy$, then $w=xy$, or $w=xTSy$; in either case $|w|_a=|v|_a=|v|_b=|w|_a$. If $v=xTy$, then $w=xy$ or $w=xaTby$. The first possibility has already been covered, and in the second we have $|w|_a=|v|_a+1=|v|_b+1=|w|_b$. In all cases, then, $|w|_a=|w|_b$, so $P(n+1)$ holds. By induction $P(n)$ holds for all $n\ge 0$. In particular, all terminal $w$ strings produced by this grammar satisfy $|w|_a=|w|_b$, which is the desired result.