What is the Relevance of Parentheses Placement in a Sum?

[jgens]

Homework Statement

Prove that the placement of the parentheses in any given sum is irrelevant.

Homework Equations

$$a + (b + c) = (a + b) + c$$

$$a_1 + \dots + a_n = a_1 + (a_2 + \dots (a_{n-1} + a_n) \dots )$$

The Attempt at a Solution

My book suggests that I split this problem up into three segments and I've followed that advice. I would appreciate it if someone could give me feedback on whatever of the following is correct and what is not correct. Thanks!

1. We first prove that

$$(a_1 + \dots a_{n-1}) + a_n = a_1 + \dots a_n$$​

by induction on $n$. Clearly eqaulity holds when $n = 1$, $n = 2$, and $n = 3$ (by the associative property). Now assume that this equality holds for the sum of $k$ numbers; if it also holds for $k+1$ numbers, then equality always holds. Consider,

$$(a_1 + \dots + a_k) + a_{k+1}$$​

Using the associative property, this expression can be rewritten into the form

$$(a_1 + \dots + a_k) + a_{k+1} = a_1 + [(a_2 + \dots a_k) + a_{k+1}]$$​

Since this latter expression contains exactly $k$ numbers (in which case, equality holds) this sum can once again be rewritten as

$$(a_1 + \dots + a_k) + a_{k+1} = a_1 + (a_2 + \dots a_k + a_{k+1}) = a_1 + a_{k+1}$$​

as desired.


2. Next, we prove that if $n \geq k$, then

$$(a_1 + \dots a_k) + (a_{k+1} + \dots + a_n) = a_1 + \dots a_n$$​

by induction on $k$. Clearly, equality holds when $k = 1$ since the expression on the left is immediately identical to the one on the right. Now suppose that equality holds for some arbitrary $k$; if this implies that it also holds for $k+1$, then it equality always holds. So consider,

$$(a_1 + \dots + a_{k+1}) + (a_{k+2} + \dots + a_n)$$​

By part 1 we know that

$$a_1 + \dots + a_{k+1} = (a_1 + \dots + a_k) + a_{k+1}$$​

In which case, we have the equality

$$(a_1 + \dots + a_{k+1}) + (a_{k+2} + \dots + a_n) = [(a_1 + \dots a_k) + a_{k+1}] + (a_{k+2} + \dots + a_n)$$​

Using the associative property to rewrite this, we see that

$$(a_1 + \dots + a_{k+1}) + (a_{k+2} + \dots + a_n) = (a_1 + \dots a_k) + [a_{k+1} + (a_{k+2} + \dots + a_n)] = a_1 + \dots + a_n$$​

By the assumption in our inductive step. This completes this part of the proof.


3. To complete the proof, suppose that $s(a_1, \dots, a_n)$ is some sum formed from $a_1, \dots, a_n$. Then we need only show that

$$s(a_1, \dots, a_n) = a_1 + \dots a_n$$​

I figured that it might be possible to do this by utilizing the fact every sum can be split up such that $s(a_1, \dots, a_n) = s'(a_1, \dots, a_k) + s''(a_{k+1}, \dots, a_n)$. If one were to continue to split each sum up, then one would invariably end up with a number of sums of the form $a_l + \dots a_k$. Using part 2, the sum of these sums could then be shown to be equal to $a_1 + \dots + a_n$.

This was only my initial thought and the reasoning seems a bit shaky so I would appreciate any advice on how to complete this part of the proof. I would also appreciate corrections on parts 1 and 2 of the proof. Thanks!

Edit: I'm sorry if this is in the wrong section. It's a problem from my calculus book and it seems a bit more advanced than many pre-calculus problems so I figured that this would be the correct sub-forum.

 

[njama]

I have this problem in my Discrete Mathematics textbook noted as "C Exercise" which is of course not easy at all.

The problem of generalized associativity should be solved by course-of-values induction.

Here how it goes:

Let p(n) be "$$a_1+a_2+...+a_n$$ has the same value no matter how it is evaluated."

Basis: $$a_1+a_2+a_3$$ may be evaluated only two ways. Since + is associative $$(a_1+a_2)+a_3=a_1+(a_2+a_3)$$. Hence p(3) is true.

Induction: Assume that for some $$n \geq 3$$ p(3), p(4), ... ,p(n) are all true. Now consider $$a_1+a_2+...+a_{n+1}$$. Any one of the n +'s in this expression can be applied last. If the jth + is applied last, we have $$c_j=(a_1+a_2+...+a_j)+(a_{j+1}+...+a_{n+1})$$. No matter how the expression to the left and right of the jth + are evaluated, the result will always be the same, by p(j) and p(n+1-j).

Now all that must be proven is that $$c_1=c_2=...=c_n$$.

Part of this proof is taken from the book Applied Discrete Structures for Computer Science by Alan Doerr and Kenneth Levasseur page 79/task 11.

Regards.

 

[jgens]

Thanks for your feedback! I think that my textbook suggests the approach that it does because strong induction hasn't yet been introduced. I would still like feedback on the work that I've done so far along with how I might finish the proof using my calculus text's method.

To prove that $c_1 = c_2 = \dots = c_n$ I could use the well-ordering principle to argue that there must be a least pair of consecutive integers $l,m$ such that $c_l \neq c_m$. It's a trivial exercise to then show that the parentheses can be rearranged in each of these sums to show that the sums would then be equal. This contradiction shows that our initial assumption that there were consecutive integers $l,m$ such that $c_l \neq c_m$ was incorrect, and thus $c_1 = \dots = c_n$. Is this correct?

 

[njama]

It's a trivial exercise to then show that the parentheses can be rearranged in each of these sums to show that the sums would then be equal.

It's OK, but I'll rather use direct proof and show algebraically the 'thing' in the quote.

Let me write out the final steps:
If i<j,
$$c_i=(a_1+a_2+...+a_i)+((a_{i+1}+...+a_j)+(a_{j+1}+...+a_{n+1}))=$$
$$=((a_1+...+a_i)+(a_{i+1}+...+a_j))+(a_{j+1}+...+a_{n+1})=$$, by p(3)
$$=c_j$$

Now, good luck with your mathematical challenges, I see that you are very interested in Maths and also nice mathematician.

Sorry, but I can't give you feedback on your work, because I am not experienced mathematician. I am just another student of Computer Science who is interested in Maths, but I am not good at the math. induction field. The approach with course-of-values induction is much easier to understand and solve then 'classical' induction in which you need to prove p(k) implies p(k+1). I will leave the comments to the experts.

P.S You got the same idea with
$$s(a_1, \dots, a_n) = a_1 + \dots a_n$$Regards.

 

[jgens]

Well thank you very much njama. I really do like the way that you solved the problem much better. Hopefully someone can comment on the validity of my earlier work though.

 

[njama]

Well thank you very much njama. I really do like the way that you solved the problem much better. Hopefully someone can comment on the validity of my earlier work though.

No problem. Just to mention the idea of this proof is taken from the book of Alan Doerr and Kenneth Levasseur it's not mine.

Regards.

 

[jgens]

Anyone have feedback?