How to prove that the order of addition does not matter? 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.
 A: 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.
