I know this is the multinomial theorem which is $$(a_1 + a_2 +a_3+… +a_n)^m=\sum_{k_1+k_2+…+k_n=m}\frac{m!}{k_1!\cdot…\cdot k_n!}a_1^{k_1}\cdot…\cdot a_n^{k_n}$$, but want to ask if my thought process is correct and if I made any mistakes using the sigma notation operations.
My attempt:
$$\begin{align}
(a_1 + a_2 + \cdots + a_m)^n &= \left(\sum_{i=1}^m a_i\right)^n \\
&= \sum_{i=1}^m a_i \sum_{j=1}^m a_j \sum_{k=1}^m a_k \cdots\text{n times}\cdots \sum_{z=1}^m a_z\\
&= \sum_{i=1}^m \sum_{j=1}^m \sum_{k=1}^m \cdots \sum_{z=1}^m a_i a_j a_k \cdots a_z \\
&= \sum_{i=1}^m a_i^n + n ((\sum_{1 \le i < j \le m} a_i a_j + \sum_{1 \le i < k \le m} a_i a_k + \cdots \sum_{1 \le i< z \le m}a_i a_z) \\
&+ (\sum_{1 \le j < k \le m} a_j a_k + \sum_{1 \le j < l \le m} a_j a_l + \cdots \sum_{1 \le j< z \le m}a_j a_z) + \cdots + a_y a_z).\end{align}$$
Is this correct and/or can it be simplified further?
Best Answer
That's a very nice thing to try to prove that, and I find it hard to write formally. Here's my try. First, $$ \left( \sum_{k=1}^n a_k\right)^m = \left( \sum_{k_1=1}^n a_{k_1}\right)\ldots\left( \sum_{k_m=1}^n a_{k_m}\right) = \sum_{k_1,\ldots,k_m\in\{1,\ldots,n\}}a_{k_1}\ldots a_{k_m}.$$ Now let's try to regroup the terms that look alike. Notice first that $a_{k_1}\ldots a_{k_m} = a_1^{c_1(k)}\ldots a_n^{c_n(k)}$ where $c_j(k) = \mathrm{card}\left(i\in\{1,\ldots,m\}, k_i = j\right)$, where I noted $k = (k_1,\ldots,k_m)$. Observe that we have $c_1(k)+\cdots+c_n(k) = m$ for all $k\in\{1,\ldots,n\}^m$. By then partioning the terms on the values of the $(c_j(k))$:
$$\sum_{k\in\{1,\ldots,n\}^m}a_1^{c_1(k)}\ldots a_n^{c_n(k)} = \sum_{c_1+\ldots+c_n = m}\sum_{\substack{k\in\{1,\ldots,n\}^m\\(c_j(k))_j =(c_j)_j}}a_1^{c_1}\ldots a_n^{c_n}, $$ then the term $a_1^{c_1}\ldots a_n^{c_n}$ does not depend of $k$ so this equals $$ \sum_{c_1+\ldots+c_n = m}\mathrm{card}\left(k\in\{1,\ldots,n\}^m, (c_j(k))_j =(c_j)_j\right)~~a_1^{c_1}\ldots a_n^{c_n}. $$ A bit of combinatory gives $\mathrm{card}\left(k\in\{1,\ldots,n\}^m, (c_j(k))_j =(c_j)_j\right) = \frac{m!}{c_1!\ldots c_n!}$. In fact, you have to choose $c_1$ terms in $k$ which will be $1$, so that's $\binom{m}{c_1}$ choices, then $c_2$ terms in the remaining terms which will be $2$, so that's $\binom{m-c_1}{c_2}$ choices, etc. When multiplying that gives that the cardinal is $$\binom{m}{c_1}\binom{m-c_1}{c_2}\ldots\binom{m-c_1-\ldots-c_{n-1}}{c_n} = \frac{m!}{c_1!\ldots c_n!}. $$ Finally:
$$\left( \sum_{k=1}^n a_k\right)^m =\sum_{c_1+\ldots+c_n = m}\frac{m!}{c_1!\ldots c_n!}~a_1^{c_1}\ldots a_n^{c_n}.$$