# Change of summation index and Rewriting multiple summation as one sum - Induction Proof of Multinomial Theorem

Pictures from http://www.math.msu.edu/~dhand/MTH481FS08/Notes7.pdf

I checked out Changing Summation Index Question but I still can't figure this out. I. First page of PDF. Substitute $a = n - k, b = k$ in the first sum to get the second sum. The first sum's index is $0 \le k \le n \iff$ Variable substitution $\color{blue}{n} = a + k = \color{blue}{a + b}, \, \color{green}{b = k}$ $\iff 0 \le \color{green}{b} \le \color{blue}{a -b}$.
But the PDF has $a + b = n$. How come?

II. Second page on PDF. What happened to the sum over $a_1 + ... + a_{k - 1} = b$? Did it get substituted into the first sum? Why? In https://math.stackexchange.com/a/448118/87058, James Cook recommends writing out the multiple sums. So we should not rewrite them as one sum.

\begin{eqnarray} (x_1+...+x_k)^n &=& \sum_{i_k+j=n} { n! \over i_k! j! } (x_1+... x_{k-1})^j x_k^{i_k} \\ &=& \sum_{i_k+j=n} { n! \over i_k! j! } \left( \sum_{i_1+...i_{k-1}=j} { j! \over i_1! ... i_{k-1}!} x_1^{i_1}...x_{k-1}^{i_{k-1}} \right) x_k^{i_k} \\ &=& \sum_{i_k+j=n} \sum_{i_1+...i_{k-1}=j} { n! \over i_1! ... i_k!} x_1^{i_1}... x_k^{i_k} \\ \end{eqnarray} Now note that $\{(i_1,...,i_k) | i_1+...+i_k = n \} = \cup_{j=0}^n \{(i_1,...,i_{k-1}) | i_1+...i_{k-1}=j \} \times \{ (i_k) | i_k=n-j\}$ to get \begin{eqnarray} (x_1+...+x_k)^n &=& \sum_{i_1+...i_{k}=n} { n! \over i_1! ... i_k!} x_1^{i_1}... x_k^{i_k} \\ \end{eqnarray}
To the first question. This $a+b=n$ means that the sum is taking every pair $(a,b)$ such that $$a\ge0, b\ge0, a+b=n.$$