In computer science, a string is a finite sequence of characters. For strings $A$ and $B$, we express $AB$ as $A$ followed by $B$. A balanced string of parentheses is a string of open and closed parentheses that is $()$, $ST$ or $(S)T$ where $S$ and $T$ are both balanced strings of parentheses. For example,
() (())() ()()()
are balanced strings of parentheses where as
)( ())( (()
are not.
I am trying to prove by induction that a balanced string of parentheses has the same number of open parentheses as closed parentheses. I started with the base case N(1) being true, since any of $()$, $ST$, $S(T)$ or $(S)T$ has an equal number of left and right parentheses. But I got stumped when thinking of the assumption for $N(k)$ since there are so many possible arrangements. Can anyone help please? Much appreciated!
Best Answer
Use strong induction on the length of the string: while trying to prove this for balanced strings of some length $n>0$, you may assume the result for balanced string for any length shorter than $n$.
Now a balanced string is either empty, or of the form $(S)T$ where $S$ and $T$ are balanced strings (to see this, the first character of a non-empty balanced string must be '(', find its matching ')' which must exist, and then you've got your form $(S)T$, since both in between and after the ')' there must be balanced strings). Since both $S$ and $T$ are strictly shorter than $(S)T$, your induction hypothesis applies to them. It easily follows that the claimed result follows for $(S)T$ as well.