How do multi-indices work, step by step?

Question

Never used multi-indexed summations in my life, neither has anyone else I know.

https://en.wikipedia.org/wiki/Multinomial_theorem

does not define an upper index for the multi-indexed sum, which gives the sum no meaning whatsoever.

However, it does for some reason have an ordered set of numbers as an index for a multi-indexed sum and then completely fails to explain the procedure for each of those indices in that set. Is it a nested sum? A product of sums? A sum of products? Is each sum a coefficient of some polynomial? Is each polynomial a coefficient of some sum? And to what end-index? How do you use any part of this theorem? The world may never know.

Answer 1

Here we look at the connection between binomial expansion and multinomial expansion for the cases $n=2$ and $n=3$ which might give a better idea what's going on.

Case $n=2$:

\begin{align*} \color{blue}{(x_1+x_2)^n}&\color{blue}{=\sum_{k_1=0}^n\binom{n}{k_1}x_1^{k_1}x_2^{n-k_1}}\\ &=\sum_{k_1=0}^n\frac{n!}{k_1!(n-k_1)!}x_1^{x_1}x_2^{n-k_1}\\ &=\sum_{{k_1+k_2=n}\atop{k_1,k_2\geq 0}}\frac{n!}{k_1!k_2!}x_1^{k_1}x_2^{k_2}\tag{1}\\ &\,\,\color{blue}{=\sum_{{k_1+k_2=n}\atop{k_1,k_2\geq 0}}\binom{n}{k_1,k_2}x_1^{k_1}x_2^{k_2}} \end{align*}

Comment:

• In (1) we introduce a new index variable $k_2=n-k_1$. Note we also state in the index region $k_1,k_2\geq 0$ which is sometimes silently assumed.

Case $n=3$:

\begin{align*} \color{blue}{(x_1+x_2+x_3)^n}&=(x_1+(x_2+x_3))^n\\ &=\sum_{k_1=0}^n\binom{n}{k_1}x_1^{k_1}(x_2+x_3)^{n-k_1}\\ &\,\,\color{blue}{=\sum_{k_1=0}^n\binom{n}{k_1}x_1^{k_1}\sum_{k_2=0}^{n-k_1}\binom{n-k_1}{k_2}x_2^{k_2}x_3^{n-k_1-k_2}}\\ &=\sum_{k_1=0}^n\sum_{k_2=0}^{n-k_1}\frac{n!}{k_1!(n-k_1)!}\cdot\frac{(n-k_1)!}{k_2!(n-k_1-k_2)!}x_1^{k_1}x_2^{k_2}x_3^{n-k_1-k_2}\\ &=\sum_{k_1=0}^n\sum_{k_2=0}^{n-k_1}\frac{n!}{k_1!k_2!(n-k_1-k_2)!}x_1^{k_1}x_2^{k_2}x_3^{n-k_1-k_2}\\ &=\sum_{k_1=0}^n\sum_{{k_2+k_3=n-k_1}\atop{k_2,k_3\geq 0}}\frac{n!}{k_1!k_2!k_3!}x_1^{k_1}x_2^{k_2}x_3^{k_3}\tag{2}\\ &=\sum_{{k_1+k_2+k_3=n}\atop{k_1,k_2,k_3\geq 0}}\frac{n!}{k_1!k_2!k_3!}x_1^{k_1}x_2^{k_2}x_3^{k_3}\\ &\,\,\color{blue}{=\sum_{{k_1+k_2+k_3=n}\atop{k_1,k_2,k_3\geq 0}}\binom{n}{k_1,k_2,k_3}x_1^{k_1}x_2^{k_2}x_3^{k_3}}\\ \end{align*}

• In (2) we introduce a new index variable $k_3=n-k_1-k_2$ similarly as we did in (1).

Hint: You might find chapter 2: Sums in Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik helpful. It provides a thorough introduction in the usage of sums.