Let $I_n=\{i\in\mathbb N\mid 1\leq i\leq n\}$, $(a_1,\cdots,a_n)$ be a finite sequence in $\mathbb N$, and $\sigma$ be a permutation of $I_n$. I've shown that there is a sequence $(s_1,\cdots,s_n)$ such that $s_1=a_1$ and $s_{i+1}=s_i+a_{i+1}$ for all $1\leq i<n$ here. As a result, we write $s_n=a_1+\cdots+a_n$, or $s_n=\sum_{i=1}^n a_i$. Prove that:
$$\sum_{i=1}^n a_i=\sum_{i=1}^n a_{\sigma(i)}$$
I'm not sure whether Case 2 where $\sigma(k+1)\leq k$ contains error, please help me check that Case.
Please suggest any shorter or simpler approach.
My attempt:
I will prove this by induction on $n$. It's clear that the theorem is trivially true for $n=1$. Assume that the theorem is true for $n=k$, i.e. $\sum_{i=1}^k a_i=\sum_{i=1}^k a_{\sigma(i)}$ where $\sigma$ is any permutation of $I_k$.
Let $\sigma'$ be any permutation of $I_{k+1}$. We have $\sum_{i=1}^{k+1} a_{\sigma'(i)}=\sum_{i=1}^k a_{\sigma'(i)}+a_{\sigma'(k+1)}$. There are two cases in total.
- $\sigma'(k+1)=k+1$
As a result, $\{\sigma'(i)\mid 1\leq i\leq k\}=I_k$, then $\sigma'(i)\restriction_{I_k}$ is obviously a permutation of $I_k$. Thus $\sum_{i=1}^k a_{\sigma'(i)}\overset{IH}{=}\sum_{i=1}^k a_i$, then $\sum_{i=1}^{k+1} a_{\sigma'(i)}=\sum_{i=1}^k a_{\sigma'(i)}+a_{\sigma'(k+1)}=\sum_{i=1}^k a_i+a_{k+1}=\sum_{i=1}^{k+1} a_i$.
- $\sigma'(k+1)\leq k$
As a result, there exists $y\leq k$ such that $\sigma'(y)=k+1$. We generate sequence $(b_i\mid 1\leq i\leq k)$ such that $b_i=a_{\sigma'(i)}$.
Thus $\sum_{i=1}^k a_{\sigma'(i)}=\sum_{i=1}^k b_i\overset{IH}{=}\sum_{i=1,i\neq y}^k b_i+b_y=\sum_{i=1,i\neq y}^k a_{\sigma'(i)}+a_{\sigma'(y)}=\sum_{i=1,i\neq y}^k a_{\sigma'(i)}+a_{k+1}$, then $\sum_{i=1}^{k+1} a_{\sigma'(i)}=\sum_{i=1}^k a_{\sigma'(i)}+a_{\sigma'(k+1)}=(\sum_{i=1,i\neq y}^k a_{\sigma'(i)}+a_{k+1})+a_{\sigma'(k+1)}\overset{Associativity}{=}\sum_{i=1,i\neq y}^k a_{\sigma'(i)}+(a_{k+1}+a_{\sigma'(k+1)})\overset{Commutative}{=}\sum_{i=1,i\neq y}^k a_{\sigma'(i)}+(a_{\sigma'(k+1)}+a_{k+1})\overset{Associativity}{=}(\sum_{i=1,i\neq y}^k a_{\sigma'(i)}+a_{\sigma'(k+1)})+a_{k+1}.$
Notice that $\{\sigma'(i)\mid 1\leq i\leq k\text{ and }i\neq y\}\cup\{\sigma'(k+1)\}=I_{k+1}\setminus\{k+1\}=I_{k}$. Thus $\sum_{i=1,i\neq y}^k a_{\sigma'(i)}+a_{\sigma'(k+1)}\overset{IH}{=}\sum_{i=1}^k a_i$. Then $\sum_{i=1}^{k+1} a_{\sigma'(i)}=\sum_{i=1}^k a_i+a_{k+1}=\sum_{i=1}^{k+1} a_i$.
To sum up, in either case, $\sum_{i=1}^{k+1} a_{\sigma'(i)}=\sum_{i=1}^{k+1} a_i$. Hence the theorem is true for $n=k+1$. This completes the proof.
I think the main doubt is for the $\sigma$ in the case of $k+1$, is it the same $\sigma$ for the case of $k$? Is the induction hypothesis valid since $\sigma$ is not a permutation of $I_k$?
One possible approach is note that permutation is a products of adjacent transposition so we can focus on proving that under adjacent transposition, the sum is preserved.
Suppose $\sigma$ only switches $j$ and $j+1$.
We have
\begin{align}\sum_{i=1}^{j+1}a_{\sigma(i)}&=\left( \sum_{i=1}^{j-1}a_i + a_{j+1}\right) + a_{j} \\ &= \sum_{i=1}^{j-1}a_i + (a_{j+1} + a_{j}), \text{Associativity}\\ &=\sum_{i=1}^{j-1} a_i +(a_j+a_{j+1}), \text{Commutative} \\ &=\left(\sum_{i=1}^{j-1}a_i+a_j\right) + a_{j+1} , \text{Associativity}\\ &=\sum_{i=1}^{j+1}a_i\end{align}
Hence $\sum_{i=1}^n a_{\sigma(i)}= \sum_{i=1}^n a_i$.
Hence the result is true by induction on the number of adjacent transposition.