0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Michael Burr Apr 11 '17 at 10:56
  • $\begingroup$ 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. $\endgroup$ – gandalf61 Apr 11 '17 at 11:02
0
$\begingroup$

The way I'd go about proving this is as follows:

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}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It is worth noting that this proof is not complete. It has a few loop holes left that don't exactly make it air tight, but they're all easy fixes if you're used to writing proofs. The idea however, should be clear. $\endgroup$ – Mitchell Faas Apr 11 '17 at 11:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.