# recursion question

I just need a hint to solving this question or a starting point because I am totally stuck...I don't really understand how I can prove this. It doesn't seem possible to me that different applications can have same amount of brackets on each side..

I would appreciate if you could perhaps explain the question better so I could somehow understand it because currently it really makes no sense.

-
Note that you will be using what is sometimes called strong induction, or complete induction. From the hypothesis that the result holds when $k$ or fewer applications of the generating rule are used, you deduce that the result holds when $k+1$ or fewer applications are used. – André Nicolas Jan 23 '12 at 23:19

You’ve been given a recursive definition of canonical expressions: they’re the expressions that can be built from real numbers and the symbols $+,\cdot,(,)$, and $-$ using three generating rules.

1. If $A$ is any canonical expression, you can build a new one, $(-A)$, by prefixing a minus sign and enclosing the whole thing in parentheses.

2. If $A$ and $B$ are any canonical expressions, you can build a new one, $(A+B)$, by sticking a plus sign between $A$ and $B$ and enclosing the whole thing in parentheses.

3. If $A$ and $B$ are any canonical expressions, you can build a new one, $A\cdot B$, by sticking a $\cdot$ between $A$ and $B$.

Anything that you can build up from single real numbers by repeated applications of (1)-(3) is a canonical expression, and those are the only canonical expressions.

For example, starting with the real number $5$, which is a basic canonical expression, I can use (1) to build the canonical expression $(-5)$. I can then use it, the basic canonical expression $7$, and (3) to build the canonical expression $(-5)\cdot 7$. I can then combine the canonical expressions $(-5)$ and $(-5)\cdot 7$, using (2), to get the canonical expression $\color{red}((-5)+(-5)\cdot7\color{red})$, where the red parentheses are from the use (2), and the black are from (1).

If you experiment with building canonical expressions in this way, you’ll see that every canonical expression that you build has the same number of left parentheses as right parentheses. The expression $((-5)+(-5)\cdot7)$, for example, has three of each. The example in the text that you supplied has two of each. $(-5)$ has one of each. And $7$ has none of each. The problem asks you to prove that every expression that can be built from the basic canonical expressions $-$ the real numbers $-$ using rules (1)-(3) must have the same number of left parentheses as right parentheses; you can never build (for instance) a canonical expression with three left and four right parentheses.

The hint is that you should try to prove this by mathematical induction based on the number of applications of rules (1)-(3) used in building the expression. To get started, if you’ve used no application of (1)-(3), your canonical expression must be simply a real number, so it has no left and no right parentheses. Now suppose that you use (1)-(3) once. If you use (3), forming (for instance) $3\cdot5$, you add no parentheses to what was already there, and you still have the same number of left and right parentheses: none. If you use (1) or (2), forming (for instance) $(-5)$ or $(3+7)$, you add one left and one right parenthesis to the none that were there, so you now have one of each. To turn this into a proof by induction, you need to prove the following statement:

Suppose that every canonical expression that can be built with at most $n$ applications of (1)-(3) has the same number of left parentheses as it has right parentheses; then the same is true of every canonical expression that can be built with at most $n+1$ applications of (1)-(3).

This is the standard format for a proof by mathematical induction.

-

The base case is that of real numbers, which have no parentheses. Therefore they have an equal number of left and right parentheses. The induction is to assume that all canonical arithmetic expressions which can be reached by $k$ or less operations of the rules have an equal number of left and right parentheses. You then need to justify that all applications of the rules to these expressions (yielding an expression that may take $k+1$ operations) still have an equal number of left and right parentheses.

I have seen this called induction on the complexity of an expression.

-