Proving the Multinomial Theorem--Collapsing Double Sum (Multiple Summation Step)

Question

I am wanting to figure out how to prove the multinomial theorem, but I am stuck on what particular part which is called "collapsing the double sum". How can I show that these two expressions equal one another to conclude the following:

$$\sum_{k_{r + 1} \mathop = 0}^n \left({\sum_{k_1 + k_2 + \cdots + k_r \mathop = n - k_{r + 1} } \binom n {k_{r + 1} } \binom {n - k_{r + 1} } {k_1, k_2, \ldots, k_r} {x_1}^{k_1} {x_2}^{k_2} \cdots {x_r}^{k_r} {x_{r + 1} }^{k_{r + 1}} }\right)=\sum_{k_1 + k_2 + \cdots + k_r + k_{r + 1} \mathop = n} \binom n {k_{r + 1} } \binom {n - k_{r + 1} } {k_1, k_2, \ldots, k_r} {x_1}^{k_1} {x_2}^{k_2} \cdots {x_r}^{k_r} {x_{r + 1} }^{k_{r + 1} } \text{ .}$$

I am wanting to do so with induction or another formal technique, and not just expanding it out.

Any help would be greatly appreciated!

Answer 1

Since the summands are identical, we just need to compare the summation limits of the double sum on LHS to see if they are equivalent to the limits of the single sum on RHS.

The inner sum specifies that $$\begin{align} k_1+k_2+\cdots+k_r&=n-k_{r+1}\\ \Rightarrow k_1+k_2+\cdots+k_r+k_{r+1}&=n\end{align}$$ and the outer sum specifies that $k_{r+1}$ runs through all possible values, i.e.from $0$ to $n$.

Hence $$\sum_{k_{r+1}=0}^n\sum_{k_1+k_2+\cdots+k_r=n-k_{r+1}}f(k_1, k_2, \cdots k_{r+1})=\sum_{k_1+k_2+\cdots+k_r+k_{r+1}=n}f(k_1, k_2, \cdots k_{r+1})$$

Answer 2

I figured this out after awhile. I appreciate the time others spent trying to help me.

Define the following:

$A_1=\sum_{(i_1,i_2, \cdots, i_{k_{r+1})\in \lbrace (k_1, k_2, \cdots, k_{r+1})| k_1+k_2+\cdots+k_{r+1}=n, k_1,k_2, \cdots, k_{r}\in \mathbb{W}, \text{ and } k_{r+1}\in \mathbb{W} , k_{r+1}\leq n}\rbrace } \binom n {i_{r + 1} } \binom {n - i_{r + 1} } {i_1, i_2, \ldots, i_r} {x_1}^{i_1} {x_2}^{i_2} \cdots {x_r}^{i_r} {x_{r + 1} }^{i_{r + 1}},$

$A_2=\sum_{(i_1,i_2, \cdots, i_{k_{r+1})\in \lbrace (k_1, k_2, \cdots, k_{r+1})| k_1+k_2+\cdots+k_{r+1}=n, k_1,k_2, \cdots, k_{r}, k_{r+1}\in \mathbb{W}}\rbrace } \binom n {i_{r + 1} } \binom {n - i_{r + 1} } {i_1, i_2, \ldots, i_r} {x_1}^{i_1} {x_2}^{i_2} \cdots {x_r}^{i_r} {x_{r + 1} }^{i_{r + 1}},$

$A_3=\sum_{k_1 + k_2 + \cdots + k_r+k_{r + 1} \mathop = 0}^n \binom n {k_{r + 1} } \binom {n - k_{r + 1} } {k_1, k_2, \ldots, k_r} {x_1}^{k_1} {x_2}^{k_2} \cdots {x_r}^{k_r} {x_{r + 1} }^{k_{r + 1}}.$

Consider the following:\begin{align*} \sum_{k_{r + 1} \mathop = 0}^n \left({\sum_{k_1 + k_2 + \cdots + k_r \mathop = n - k_{r + 1} } \binom n {k_{r + 1} } \binom {n - k_{r + 1} } {k_1, k_2, \ldots, k_r} {x_1}^{k_1} {x_2}^{k_2} \cdots {x_r}^{k_r} {x_{r + 1} }^{k_{r + 1}} }\right)&= A_1 \\ &= A_2 \\ &= A_3.\\ \end{align*} On the right hand side, the first and second expressions down are equal because their sets are equal. We can write this as a lemma (see below):

Lemma:

$\underbrace{\lbrace (k_1, k_2, \cdots, k_{r+1})| k_1+k_2+\cdots+k_{r+1}=n, k_1,k_2, \cdots, k_{r}\in \mathbb{W}, \text{ and } k_{r+1}\in \mathbb{W} , k_{r+1}\leq n\rbrace}_{=A}=\underbrace{\lbrace (k_1, k_2, \cdots, k_{r+1})| k_1+k_2+\cdots+k_{r+1}=n, k_1,k_2, \cdots, k_{r}, k_{r+1}\in \mathbb{W} \rbrace}_{=B}$

Proof:

$\subseteq$ Obviously $A\subseteq B$ for this direction.

$\supseteq$ Assume $x\in B$. [Show $x\in A$.] Thus, $x=(k_1, k_2,..., k_{r+1})$ for which $k_1+k_2+\cdots+k_{r+1}=n, k_1,k_2, \cdots, k_{r}\in \mathbb{W}, \text{ and } k_{r+1}\in \mathbb{W} $. Now, suppose $k_{r+1}>n$ and show a contradiction. This means $0>n-\underbrace{k_{r+1}}_{n-k_1-k_2\cdots k_r}=\underbrace{k_1+k_2+\cdots k_r}_{\in \mathbb{W}}$. This is a contradiction. Thus, $k_{r+1}\leq n$. This means $x\in A$. //