3

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?

John Doe
  • 502
  • 4
    Unfortunately, there is no quality control on MathSE reviewers downvoting a posting. Initially, your posting was downvoted, which I totally disagree with. In fact, I upvoted your posting because you are (in effect) attempting to manually derive the multinomial theorem. Also, there is no quality control on voting to close. Your posting has received 1 vote to close. If it receives $4$ more, then your posting will be closed. ...see next comment – user2661923 Dec 30 '22 at 15:37
  • 2
    I regard your posting as high quality, for the work shown. However, your posting is difficult for a MathSE reviewer to deal with, because of the awkwardness of the expression at the end of your posting. For the most part, this is not your fault, because (in my opinion), the awkwardness is built in to the analysis that you are striving for. Anyway, it is an unfortunate fact, that lacking quality control, many MathSE reviewers will react negatively, even when the posting shows good work, because the posting is inconvenient. ...see next comment – user2661923 Dec 30 '22 at 15:40
  • 2
    That is, since the reviewer does not want to deal with the awkward notation, they pretend that the posting is low quality. Personally, I also don't want to deal with the awkward notation, so I will leave it alone. However, this does not compel me to pretend that your posting was low quality. – user2661923 Dec 30 '22 at 15:42
  • @user2661923 Thanks for your comment, I appreciate it, and hopefully someone answers before i get the 4 "close" verdicts. ;) – John Doe Dec 30 '22 at 15:55
  • 1
    John Doe, I was the first one to upvote your post by the way ;) @user2661923 what do you mean by awkwardness? I want to avoid it myself since I keep getting downvotes without explanation. – Kamal Saleh Dec 30 '22 at 17:10
  • @KamalSaleh Thanks too ;) – John Doe Dec 30 '22 at 20:15
  • 1
    @KamalSaleh By awkwardness, I meant that the Math expression in the last two lines of the posting is hard to decipher, despite the use of MathJax. To a small extent, this is the OP's (i.e. original poster's) fault, since he could have spread the posting out over many more lines, and avoided (for example consecutive $(($ symbols in favor of something like $~[ ~(.~$ However, for the most part the difficulty in deciphering is because the (necessary) consecutive summations are themselves difficult to decipher. – user2661923 Dec 30 '22 at 21:47

1 Answers1

1

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

Rafaël
  • 181