The proof by induction of the multinomial theorem

Question

I looked at the proof by induction of the multinomial theorem on Wikipedia and do not understand how to get the last step. Specifically, I do not know why this equality is true: $$\sum_{k_1 + k_2 + \cdots + k_{m-1} + K = n} \binom{n}{k_1, k_2, \ldots, k_{m-1}, K} x_1^{k_1} x_2^{k_2} \cdots x_{m-1}^{k_{m-1}} \sum_{k_m + k_{m+1} = K} \binom{K}{k_m, k_{m+1}} x_m^{k_m} x_{m+1}^{k_{m+1}} = \sum_{k_1 + k_2 + \cdots + k_{m-1} + k_m + k_{m+1} = n} \binom{n}{k_1, k_2, \ldots, k_{m-1}, k_m, k_{m+1}} x_1^{k_1} x_2^{k_2} \cdots x_{m-1}^{k_{m-1}} x_m^{k_m} x_{m+1}^{k_{m+1}}.$$ Is there a summation identity that states you can multiply the contents of each summation like this, where you combine the two summations into one? I looked at the general summation identities on Wikipedia but cannot see how they would be applied here. I would think it should not be so simple as to just multiply the contents of the summations together because the distributive property should add new terms. Maybe it is the long sigma notation with all the $k_i$'s that is making it harder for me to understand these summations, but the lack of parentheses around the second summation is confusing as well because I cannot tell if the smaller summation is nested in the larger summation. I assume it is, though.

Answer 1

Letting $K=k_m+k_{m+1}$ in the indices of the first summation allows the distributivity.

This different approach might help clear things up for you.

$$((x_1+\dots+x_m)+x_{m+1})^n$$

$$=\sum_{i+j=n}\binom{n}{i} (x_1+\dots+x_m)^i x_{m+1}^j$$

$$=\sum_{i+j=n}\binom{n}{i} \left(\sum_{k_1 + \cdots + k_m = i} \binom{i}{k_1,\dots, k_m} x_1^{k_1} \dots x_m^{k_m} \right) x_{m+1}^j$$

$$=\sum_{k_1 + \cdots + k_m +j= n} \binom{n}{k_1,\dots, k_m,j} x_1^{k_1} \dots x_m^{k_m}x_{m+1}^j$$

Answer 2

Let $$A:=\sum_{k_1 + \cdots + k_{m-1} + K = n} \sum_{k_m + k_{m+1} = K}\sigma(k_1, \ldots, k_{m+1})$$ and $$B:=\sum_{k_1 + \cdots + k_{m+1} = n} \sigma(k_1, \ldots, k_{m+1})$$ where $$\sigma(k_1, \ldots, k_{m+1})=\binom{n}{k_1,\ldots, k_{m+1}} x_1^{k_1} \cdots x_{m+1}^{k_{m+1}}$$

---

I'm going to give three explanations about why $A=B$.

Explanation 1 :

$\displaystyle\sum_{k_1 + \cdots + k_{m-1} + K = n}$ means that the sum runs over all $(k_1,\ldots, k_{m-1},K)$ whose total is $n$ where $k_1,\ldots,k_{m-1},K$ are non-negative integers.

$A$ is the sum of the small sums $(A=\sum+\sum+\cdots +\sum)$. Each of the small sums has the terms with the same $(k_1,\ldots,k_{m-1})$.

In each of the small sums where $K$ is already determined, $\displaystyle\sum_{k_m+k_{m+1}=K}$ means that the sum runs over all $(k_m,k_{m+1})$ whose total is $K$ where $k_m,k_{m+1}$ are non-negative integers.

So, we can say that each term of $A$ satisfies $k_1+\cdots +k_{m+1}=n,k_1\ge 0,\cdots,k_{m+1}\ge 0$, and that $A$ does not have any term which does not satisfy $k_1+\cdots +k_{m+1}=n,k_1\ge 0,\cdots,k_{m+1}\ge 0$.

Therefore, we can say that $A=B$.

---

Explanation 2 :

Let us divide $B$ into small groups each of which has the terms with the same $(k_1,\ldots,k_{m-1})$.

Since $\displaystyle\sum_{k_1 + \cdots + k_{m+1} = n}$ means that the sum runs over all $(k_1,\ldots, k_{m+1})$ whose total is $n$ where $k_1,\ldots,k_{m+1}$ are non-negative integers, each of the small groups has all the possible non-negative integer pairs $(k_m,k_{m+1})$ satisfying $k_m+k_{m+1}=n-(k_1+\cdots +k_{m-1})$.

So, we can say that for each term of $B$, there is a non-negative integer $K$ such that $k_1+\cdots +k_{m-1}+K=n,k_m+k_{m+1}=K,k_1\ge 0,\ldots, k_{m+1}\ge 0$, and that there is no term in $B$ such that there is not such a non-negative integer $K$.

Therefore, we can say that $B=A$.

---

Explanation 3 :

To prove that $A=B$, it is sufficient to prove the following two claims :

Claim 1 : Each term in $A$ is included in $B$.

Claim 2 : Each term in $B$ is included in $A$.

Proof of Claim 1 : Each term in $A$ satisfies $$\begin{cases}k_1+\cdots +k_{m-1}+K=n \\k_m+k_{m+1}=K \\\text{$k_1,\cdots,k_{m+1},K$ are non-negative integers}\end{cases}$$

So, each term in $A$ satisfies $$\begin{cases}k_1+\cdots +k_{m+1}=n \\\text{$k_1,\cdots,k_{m+1}$ are non-negative integers}\end{cases}$$

Proof of Claim 2 : Each term in $B$ satisfies $$\begin{cases}k_1+\cdots +k_{m+1}=n \\\text{$k_1,\cdots,k_{m+1}$ are non-negative integers}\end{cases}$$

Let $K:=k_m+k_{m+1}$. Then, $K$ is a non-negative integer.

So, each term in $B$ satisfies

$$\begin{cases}k_1+\cdots +k_{m-1}+K=n \\k_m+k_{m+1}=K \\\text{$k_1,\cdots,k_{m+1},K$ are non-negative integers}\end{cases}$$

Therefore, it follows from two clmais that $A=B$.

Answer 3

I have thought of a proof that involves working backwards from the desired result.

A word of warning: while this proof may be correct, it makes the process of combining two dependent $\sum$'s more complicated than the linked Wikipedia article and this ProofWiki article suggests. I would appreciate it if someone could give a more direct proof and explain why the process is treated as straightforward.

Proof

Suppose $m \ge 2$. Start with the RHS

$$\sum_{k_1 + \cdots + k_{m+1} = n} \binom{n}{k_1, \ldots, k_{m+1}} x_1^{k_1} \cdots x_{m+1}^{k_{m+1}},$$

which sums the summand $\sigma(k_1, \ldots, k_{m+1})=\binom{n}{k_1, \ldots, k_{m+1}} x_1^{k_1} \cdots x_{m+1}^{k_{m+1}}$ over all groups of nonnegative integral values $(k_1, \ldots, k_{m+1})$ satisfying the condition $k_1 + \cdots + k_{m+1} = n$.

Now, for every group $(k_1, \ldots, k_{m+1})$ satisfying such condition, $k_m + k_{m+1}$ is some fixed integer. Since $k_m$ and $k_{m+1}$ are nonnegative and $k_m + k_{m+1}$ must not exceed $n$, we have $0 \le k_m + k_{m+1} \le n$, that is, $k_m + k_{m+1} = 0, 1, \ldots, n$. In light of this fact, we can divide the summands of the expanded sum into groups based on their value of $k_m + k_{m+1}$:

$$\sum_{k_1 + \cdots + k_{m+1} = n} \sigma = \sum_{\substack{k_1 + \cdots + k_{m-1} + 0 = n, \\ k_m + k_{m+1} = 0}} \sigma + \cdots + \sum_{\substack{k_1 + \cdots + k_{m-1} + n = n, \\ k_m + k_{m+1} = n}} \sigma. \tag{1}$$

From here, consider the summation

$$\sum_{\substack{k_1 + \cdots + k_{m-1} + K = n, \\ k_m + k_{m+1} = K}} \sigma$$

for some $K=0,1,\ldots,n$. Let the number of groups of values of $(k_1, \ldots, k_{m-1})$ satisfying $k_1 + \ldots + k_{m-1} + K = n$ be $M$, and the number of groups of values of $(k_m, k_{m+1})$ satisfying $k_m + k_{m+1} = K$ be $N$. Observe that any and every group of values $(k_1, \ldots, k_{m-1}, k_m, k_{m+1})$ satisfying both $k_1 + \ldots + k_{m-1} + K = n$ and $k_m + k_{m+1} = K$ can be created by combining any of the $M$ $(k_1, \ldots, k_{m-1})$ with any of the $N$ $(k_m, k_{m+1})$. Also notice that

$$\sum_{k_m + k_{m+1} = K} \sigma$$

first inserts the $N$ $(k_m, k_{m+1})$ into $\sigma$, and the outer summation in

$$\sum_{k_1 + \cdots + k_{m-1} + K = n} \sum_{k_m + k_{m+1} = K} \sigma$$

combines each of the $M$ $(k_1, \ldots, k_{m-1})$ with each of the $N$ $(k_m, k_{m+1})$, yielding the same expanded form as

$$\sum_{k_1 + \cdots + k_{m+1} = n} \sigma.$$

Therefore, the RHS of equation (1) becomes

$$(\sum_{k_1 + \cdots + k_{m-1} + 0 = n} \sum_{k_m + k_{m+1} = 0} \sigma) + \cdots + (\sum_{k_1 + \cdots + k_{m-1} + n = n} \sum_{k_m + k_{m+1} = n} \sigma)$$

which, using the same logic as in equation (1), simplifies to

$$\sum_{k_1 + \cdots + k_{m-1} + K = n} \sum_{k_m + k_{m+1} = K} \sigma$$

as required.

$$\tag*{$\square$}$$