# Prove the sum $\sum_{i=1}^n a_{\sigma_i}$ computed over all permutations σ of the set {1, 2, …, n} remains unchanged.

I'm recently wondering how to prove the order in which addition is performed does not matter even when adding many numbers. This proof should be merely based on the commutative and associative property of addition.

That is, prove $$\sum_{i=1}^n a_{\sigma_i}\quad \text{keeps unchanged},$$ where $\sigma$ is any permutation of the set {1, 2, …, n}, $\sigma_i$ is the value in the $i$th position after the reordering $\sigma$, $a_{\sigma_i} \in R$, $i=1,2,\dots ,n$ and $n$ is an integer.

• The summation $i\in \sigma$ doesn't really make sense because a permutation is a function and not a set. The reasoning behind the question you're trying to ask is that the sums have the same terms, just rearranged by the permutation. The associative property tells you that you can regroup the sum as you wish (so you don't need parentheses) and the commutative property allows you to rearrange the terms. – Michael Burr Apr 11 '17 at 10:56
• Use the associative and commutative properties to show that you can swap any two terms in the sum without affecting the total. Once you know you can swap any two terms, then you can transform any given order of terms into any other order of terms without affecting the total. – gandalf61 Apr 11 '17 at 11:02

Let $(1, 2, ..., n)$ be the order we'd normally find $a_i$ in and $(\sigma1, \sigma2, ..., \sigma n)$ the order after our permutation has been applied. Then let $\sigma j$ correspond with $1$. If we now exchange $\sigma j$ and $\sigma(j-1)$, we'll keep the same sum (addition is commutative). Therefore, we can move $\sigma j$ to the first place in $j-1$ steps and get a new permutation which has the same sum. We can then repeat this process for all terms to "revert" the permutation made and end up with our original sum.
Therefore it must be that $$\sum_i a_i=\sum_i a_{\sigma i}$$