How to prove that the order of addition does not matter?

Question

The more precise version of my question:

Let $(a_i)_{i=1}^n$ be a set of values for which the commutative and associative rules hold.

Let $P$ be a permutation of $\{1, 2, ..., n\}$. ($1 \le P(i) \le n$ and $i \ne j \implies P(i) \ne P(j) $)

Prove that $\sum_{i=1}^n a_i =\sum_{i=1}^n a_{P(i)} $.

My idea on proving this is to transform the sequence by a series of associative and commutative rule applications to a "normal" form in which the sequence is sorted. This sorted sequence has the same sum as the original sequence. (This requires the result that any sequence can be sorted by a series of transpositions.)

Since sorting the permuted sequence gives the same "normal" form, its sum is the same.

Another proof might be by induction on $n$. This would also seem to need a "normal" form for the sequence. The new element would be inserted into the sequence wherever the normal form requires it to be.

Answer 1

The permutation group $S_n$ of $n$ elements is generated by the transposition $\tau = (12)$ and a cycle of length $n$, namely $\sigma = (123\cdots n)$. To prove what you want for a particular $n$, you just need to verify two identities:

• Swapping the first two elements (i.e. invariance under $\tau$ ) $$(((a_1 + a_2) + a_3) + \cdots + a_n) = (((a_2 + a_1) + a_3 + \cdots + a_n )$$
• Shifting all elements to the right (i.e. invariance under $\sigma^{-1}$) $$(((a_1 + a_2) + a_3) + \cdots + a_n) = (((a_n + a_1) + a_2 + \cdots + a_{n-1})$$

The first identity is trivially true, it is just the commutativity between two elements $a_1$ and $a_2$.

For the second identity, assume you have proved the statement for any sum of $n-1$ elements. Treating $(a_1+a_2)$ as a single element and apply the assumed identity to the list of $n-1$ elements: $$(a_1+a_2), a_3, a_4, \cdots a_n$$ We get

$$(((a_1 + a_2) + a_3 ) + a_4 + \cdots + a_n)) = ((a_n + (a_1 + a_2)) + a_3 + \cdots + a_{n-1}))$$ By the ordinary associativity among the 3 elements $a_n, a_1, a_2$, $$a_n + (a_1 + a_2) = (a_n + a_1) + a_2$$ the RHS can be transformed $$(((a_n + a_1) + a_2) + a_3 + \cdots a_{n-1} )$$ This is precisely what we need for the second identity for the given $n$ to be true. Since the statement is trivially true for $n = 3$, by induction, the second identity is true for all $n \ge 3$.

Combine these two identities, we have established the general commutativity for finite sums defined recursively by following formula:

$$\sum_{k=1}^n a_k \stackrel{def}{=} \begin{cases} \displaystyle\left(\sum_{k=1}^{n-1} a_k \right) + a_n,& n > 1\\ \\ a_1, & n = 1 \end{cases} $$

Please note that in this proof, we have not proved nor used general associativity at all.