Consider the following recursive definition of a set S of parentheses strings that contain the left and right parentheses symbols, i.e. ( and ) respectively:

• Basis: The empty string, \lambda is in S
• Inductively, if x is in S and y is in S, then (x)y is in S.

For example, starting from the empty string, we can obtain the string () in S, then use that string to construct ()() and (()) in S and so on.

• Prove by structural induction that every string in S has an equal number of left and right parentheses.