Prove that a sum involving any number of vectors is independent of the way they are combined and associated I am trying to prove the following statement from my course book:
A sum involving any number of vectors is independent of the way/order they are combined and associated.
ie. One possible combination:
$(v_1+v_2)+(v_3+v_4)=(v_1+(v_2+v_3))+v_4$
A hint was given that a clever induction is required. Following this I have started a proof by induction:
Let $V$ be a vector space.
Let $P(n)$ be the the proposition: a sum of $n$ vectors in $V$ is independent of the way that they are associated and combined.
Clearly $P(2)$, by the axioms of vector spaces.
Assume $P(k)$ to be true. $P(k) \Rightarrow v_1+v_2+...+v_k$ is independent of combination order and association.
We want to prove $P(k+1)$:
a sum of $k+1$ vectors in $V$ is independent of the way that they are associated and combined.
I am unsure where to go from here.
 A: This is an immediate consequence of commutativity and associativity of addition. Assume by strong induction that the sum of any $k$ vectors is independent of order of operations, for all $k\leq n$ for some fixed $n$. This means that we can write any such sum as just $v_1+v_2+\cdots+v_k$, with no need to add in parentheses. Now, if you start from any "combination" (arrangement of parentheses) in a sum of $n+1$ vectors, two or more vectors must be combined within the same parentheses except in the trivial case where there aren't any. Thus, we can consider the entire expression as involving $n$ or less vectors and hence delete all the parentheses by induction. This completes the proof.
For example, $$((v_1+v_2)+v_3)+(v_4+v_5)$$
is just an expression involving four vectors $(v_1+v_2),v_3,v_4$ and $v_5$, justifying the deletion of all parentheses except the one surrounding $(v_1+v_2)$, $$((v_1+v_2)+v_3)+(v_4+v_5)=(v_1+v_2)+v_3+v_4+v_5.$$
You can trivially remove the final parenthesis by commutativity.
A: If one is interested in how parentheses are arranged, then it is a fact that adding up $n$ terms has $C_{n-1}$ ways to arrange the parentheses, where $C_n=\frac 1{n+1}{{2n}\choose{n}}$ is the $n$th Catalan number. The result that all different arrangements lead to the same vector follows from associative law. If one requires permutation of terms, then there are $C_{n-1}\cdot n!$ ways to write, and to prove that they are all the same, one needs both commutative and associative laws. The following proof may be overly tedious, but hopefully it is clear.
One starts with the standard model of adding terms $$(\cdots((v_1+v_2)+v_3)+\cdots+v_{n-1})+v_n.$$ Then prove that this is invariant under all other arrangements of parentheses, and permutations of terms.
By induction, the case $k=1,2$ are trivial, since $$v_1+v_2=v_2+v_1$$ and no parentheses are needed. For $k=3$, one has by associativity that $$(v_1+v_2)+v_3=v_1+(v_2+v_3).$$ By commutativity, the expression is also invariant under permutations $(12)$ and $(23)$, hence under the symmetric group $S_3$.
Assume the result is true for all $3\leq k\leq n,$ i.e. the standard model $$(\cdots((v_1+v_2)+v_3)+\cdots +v_{k-1})+v_k$$ is invariant under rearrangements of parentheses and $S_k$.
For the case of $n+1$, one first show that any arrangement of parentheses of $[v_1+v_2+\cdots+v_{n+1}]$ (with no terms permuted) is equivalent to the standard model $$(\cdots((v_1+v_2)+v_3)+\cdots+v_n)+v_{n+1}.$$
Case 1. $v_{n+1}$ has no right parentheses. Then the expression is of the form $$([v_1+\cdots+v_n])+v_{n+1},$$ where $[v_1+\cdots+v_n]$ is equivalent to the standard model by induction hypothesis.
Case 2. $v_{n+1}$ has some right parentheses. Then one has $$[v_1+v_2+\cdots+v_{n+1}]=([v_1+\cdots+v_{\ell}])+([v_{\ell+1}+\cdots+v_{n+1}]),$$ where $1\leq \ell\leq n-1$ (if $\ell=1$, the corresponding parentheses are not needed). By induction hypothesis, the last expression equals $$([v_1+\cdots+v_{\ell}])+(([v_{\ell+1}+\cdots+v_n])+v_{n+1})$$
$$=(([v_1+\cdots+v_{\ell}])+([v_{\ell+1}+\cdots+v_n]))+v_{n+1}~({\rm by~associativity})$$
$$=(\cdots((v_1+v_2)+v_3)+\cdots+v_n)+v_{n+1}~({\rm by~induction ~hypothesis}),(1)$$ which completes the proof for invariance under rearranging parentheses. Since $S_{n+1}$ is generated by $(12),(23),\cdots,(n-1,n)$ and $(n,n+1)$. To prove the invariance under $S_{n+1}$, it suffices to prove that expression (1) is equivalent to $$(\cdots((v_1+v_2)+v_3)+\cdots+v_{n+1})+v_n.(2)$$ Since both (1) and (2) are in the standard model, the equality follows easily by applying associativity, commutativity, and one more associativity. QED
