Given a finite collection of numbers, the products obtained by multiplying them in any order are all equal.

Question

How do I prove the following by induction?

Given a finite collection of numbers, the sums/products obtained by adding/multiplying them in any order are all equal.

Answer 1

The proof for multiplication is identical to that for addition, so I'll only look at addition; it works for any commutative associative operation.

Inductive hypothesis: any sum of $n$ numbers is equal to the sum of those same $n$ numbers in sorted order, expressed as $a_1 + (a_2 + (a_3 + \dots))$ where $a_1 \leq a_2 \leq \dots$.

Then take a collection of $n+1$ numbers, $\{a_1, a_2, \dots, a_{n+1}\}$. Their sum is expressed as $x + y$, where $x$ and $y$ are some nonempty collections of the $a_i$. There are two cases: $x$ is formally the sum of just one $a_i$, or it's the sum of more than one.

• If $x = a_i$, say, then by the inductive hypothesis, the sum of the $a_i$ comprising $y$ is equal to the same sum in ascending order and associating to the right. So we just need to combine $a_i$ with the sorted $a_1 + (a_2 + \dots)$ excluding $a_i$. You can do this inductively: $$x + (a_1 + (a_2 + \dots)) = (x + a_1) + (a_2 + \dots) = (a_1 + x) + (a_2 + \dots) = a_1 + (x + (a_2 + \dots))$$ and proceed until $x = a_i$ is in the right place. (This case also can be used if $y$ is just one $a_i$, by using commutativity.)
• If $x$ is a sum of more than one $a_i$, then by inductive hypothesis it is $a_{i_1} + (a_{i_2} + \dots)$; and $y$ is $a_{j_1} + (a_{j_2} + \dots)$. Use commutativity if necessary to ensure that $a_{i_1} \leq a_{j_1}$; then use associativity to separate the sum into $a_{i_1} + ((a_{i_2} + \dots) + (a_{j_1} + (a_{j_2} + \dots)))$. Now use the inductive hypothesis on the non-$a_{i_1}$ term.

Answer 2

Okay. So, we proceed by way of induction. You need to show the base case is true which in this case is $n=3$. So, suppose we have $3$ arbitrary numbers $m_1,m_2,m_3$. We know that for any two numbers $a,b$ that $ab=ba$ and that multiplication is associative. So

$$m_1m_2m_3=m_1(m_2m_3)=m_1(m_3m_2)=m_1m_3m_2=(m_1m_3)m_2=(m_3m_1)m_2=m_3m_1m_2$$

By associativity and commutativity (for the case $n=2$). You can continue in this fashion to get all $6$ rearrangements of the product easily and show the base case holds.

Now, we need to show that the $n$th case implies the $n+1$st case. So, suppose that multiplication commutes for any $n$ numbers and consider the collection $m_1,m_2, \dots m_{n+1}$ of $n+1$ numbers. We want to show that any arbitrary arrangement of the product is equal to $m_1m_2\dots m_nm_{n+1}$ (why is this good enough?). So, say we have some arbitrary arrangement

$$m_im_{i+1} \dots m_{i+(n+1)}$$

Then we can group this (by associativity) however we like. So, if $m_1$ is in the $i+j$ position, then we can group all the numbers to its left and consider it as one big number (by our induction hypothesis) since there will be clearly be at most $n$ of them (why?). We can commute them and so we have

$$m_1(m_i \dots m_{i+j-1} m_{i+j+1} \dots m_{i+(n+1)})$$

Continuing in this fashion we recover

$$m_1m_2 \dots m_{n+1}$$

Since this can be done for any arbitrary arrangement the result follows. Hence, multiplication commutes for any finite collection of numbers.

Addition is done in a similar manner.