# Sum as independently defined from the order of parentheses

Problem

Using induction show that the sum $x_1 +x_2 + \cdots + x_n$ of real numbers is defined independently of the insertion of parentheses to specify the order of addition.

Attempt at Solution:

Base Case: $$x_1=x_1$$

which is trivially true.

Inductive Case:

Let there be an arbitrary arrangement of parentheses $(x_1 +(x_2 +( \cdots + x_{n-1})))...)$ where there are $n-1$ left parentheses and as many right parentheses.

Assume by hypothesis that $$(x_1 +(x_2 +( \cdots + x_{n-1})))...) = x_1 +x_2 + \cdots + x_{n-1}$$

Adding $x_{n}$ to the left hand side of the equation above we get

$$((x_1 +(x_2 +( \cdots + x_{n-1})))...) + x_{n})$$

which by the hypothesis is equal to $$x_1 +x_2 + \cdots + x_{n-1} +x_n$$

Hence we have shown that for an arbitrary insertion of parentheses on the left-hand side of the equation we have

$$((x_1 +(x_2 +( \cdots + x_{n-1})))...) + x_{n})= x_1 +x_2 + \cdots + x_{n-1} +x_n$$ $\square$

I need help with this problem; I am not sure if I have actually proven the statement because when I aad $x_n$ to $((x_1 +(x_2 +( \cdots + x_{n-1})))...)$ I don't get truly arbitrary expression since the arrangement of parentheses could always be something like: $$(x_1 +x_2) + \cdots +x_{n-2}))+ (x_{n-1} +x_n)))$$

What can I add or what am I doing wrong? Am I on the right path? Thanks in advance for the help!

• I answered an essentially equivalent question here. It takes a different perspective via structural induction. It also contains a link to a machine-checked (executable) formal proof in Agda. – Derek Elkins Jun 11 '17 at 20:01

Yours is indeed not a correct proof.

HINT

Use Strong Induction! That is, consider the fact that however you place the parentheses to add up $n$ numbers, your eventual expression $\varphi$ will have to be of the form $\varphi_1 + \varphi_2$, where both $\varphi_1$ and $\varphi_2$ have less than $n$ numbers (hence you can apply the inductive hypothesis for strong induction)

• I wrote an answer to my own question using your hint, can you please check to see if it is correct? Also in an induction hypothesis do we take $P(i)$ to be true for all $i$ or just $i$ greater than the base cases? Thanks a lot. – Red Jun 11 '17 at 19:33

I think that you're right in saying that you haven't proven the statement. You have assumed the statement true for $n-1$, and then not really done anything useful. Your next step should be something like "Assuming that the assertion holds for $n-1$, consider a sum of $n$ real numbers with arbitrary insertion of parentheses...".

For my inductive step I'd say:

Let $x_1 +... + x_n$ be a sum of $n$ real numbers (for $n > 1$) where the given property holds for any sum of $k$ real numbers where $k < n$.

Now, in vague terms, it would go something like:

Consider an arbitrary, non-trivial (ie not just two parentheses around the outside of the whole thing) insertion of parentheses into this sum.

Given this arrangement of parentheses, compute what's inside the first occuring pair of parentheses. This is independent of the arrangement of parentheses therein by our inductive hypothesis.

Rewrite the sum appropriately (with the output of the above computation inside the pair of parentheses instead of it's expression as a sum of real numbers), and we now have a sum of $k$ real numbers where $k<n$, and our assertion holds by induction.

That's not a proof, that's a wave of the hands. I think it's got what you need, though.

Proof.

We take $\psi_n$ to be a single number or a total sum that contains less than or equal to $n$ summands.

Let $P(n)$ be the proposition that states that since each pair of parentheses specifies addition as a binary operator, the sum total of $x_1 +x_2 + \cdots + x_{n-1} +x_n$ is equal to a sum of the form $(\phi + \phi\prime)_n$ containing $n$ numbers where each $\phi$ and $\phi\prime$ are equal some number $x_i$ where $1\le i \le n$ or a sum of terms, containing equal to or less than $(n-1)$ terms, each given in an arbitrary arrangement of parentheses.

Base Step: $$P(1):= x_1 = (\phi)_1$$ $$P(2):= (x_1 + x_2) = (\phi_1 + x_2) =(\phi + \phi\prime)_2$$ $$P(3):= ((x_1+x_2) +x_3) = (x_1+(x_2 +x_3)) =(\phi + \phi\prime)_2 +x_3=(\phi\ + \ \phi\prime)_3$$ $$P(4):=(((x_1+ x_2)+x_3)+x_4) = (x_1+ ((x_2+x_3)+x_4)) = ((x_1+( x_2+x_3))+x_4) = (x_1+ (x_2+(x_3+x_4))) = ((x_1+ x_2) + (x_3+x_4)) = (\phi\ + \ \phi\prime)_3 + x_4= (\phi + \phi\prime)_4$$ Inductive Step

Inductive Hypothesis: Assume that $P(i)$ holds for $4 \lt i \le (n-1) .$ Then $P(n-1)$ is a sum of the form $(\phi + \phi\prime)_{n-1}$.

Add the term $x_n$ to $(\phi + \phi\prime)_{n-1}$, so it follows

$$(\phi + \phi\prime)_{n-1} +x_n =(\phi + \phi\prime)_n \ \ .$$ Therefore, $P(n)$ holds.