Im trying to prove using algebra that $$ {n \choose r_{1},\ldots,r_{k}}=\sum_{j=1}^{k}{n-1 \choose r_{1},\ldots,r_{j}-1,\ldots,r_{k}} $$
Attempt:
The multinomial theorem states that $$ \left(x_{1}+\ldots+x_{k}\right)^{n}=\sum_{\underset{r_{i}\geq0}{{\scriptscriptstyle \Sigma r_{i}=n}}}{n \choose r_{1},\ldots,r_{k}}x_{1}^{r_{1}}\cdot\ldots\cdot x_{k}^{r_{k}} $$ Moreover we know that $\left(x_{1}+\ldots+x_{k}\right)^{n}=\left(x_{1}+\ldots+x_{k}\right)^{n-1}\left(x_{1}+\ldots+x_{k}\right)$, so combinig this with the above we get that \begin{align*} \sum_{\underset{r_{i}\geq0}{{\scriptscriptstyle \Sigma r_{i}=n}}}{n \choose r_{1},\ldots,r_{k}}x_{1}^{r_{1}}\cdot\ldots\cdot x_{k}^{r_{k}} & =\left[\sum_{\underset{r_{i}\geq0}{{\scriptscriptstyle \Sigma r_{i}=n-1}}}{n-1 \choose r_{1},\ldots,r_{k}}x_{1}^{r_{1}}\cdot\ldots\cdot x_{k}^{r_{k}}\right]\left(x_{1}+\ldots+x_{k}\right)=\\ & =\sum_{j=1}^{k}\sum_{\underset{r_{i}\geq0}{{\scriptscriptstyle \Sigma r_{i}=n-1}}}{n-1 \choose r_{1},\ldots,r_{k}}x_{1}^{r_{1}}\cdot\ldots\cdot x_{j}^{r_{j}+1}\cdot\ldots\cdot x_{k}^{r_{k}}=\\ {\scriptstyle \left[\tilde{r}_{j}=r_{j}+1\right]} & =\sum_{j=1}^{k}\sum_{\underset{r_{i}\geq0\:,\:\tilde{r}_{j}\geq1}{r_{1}+\ldots+\tilde{r}_{j}+\ldots+r_{k}=n}}{n-1 \choose r_{1},\ldots,\tilde{r}_{j}-1,\ldots,r_{k}}x_{1}^{r_{1}}\cdot\ldots\cdot x_{j}^{\tilde{r}_{j}}\cdot\ldots\cdot x_{k}^{r_{k}} \end{align*}
How can we proceed? Eventually I guess we would probably use $x_{i}=1$ for all $1\leq i\leq k$.
I think this is quite a bit simpler than it looks:
\begin{eqnarray*} \sum_{j=1}^k {n-1 \choose r_1, r_2, \ldots, r_j-1, \ldots, r_k} & = & \frac{(n-1)!}{(r_1-1)!\ldots r_k!} + \ldots + \frac{(n-1)!}{r_1!\ldots (r_k-1)!} \\ & = & \frac{r_1(n-1)!}{r_1!r_2!\ldots r_k!} + \frac{r_2(n-1)!}{r_1!r_2!\ldots r_k!} + \ldots + \frac{r_k(n-1)!}{r_1!r_2!\ldots r_k!} \\ & = & \frac{(r_1 + r_2 + \ldots + r_k)(n-1)!}{r_1!r_2!\ldots r_k!} \\ & = & \frac{n\cdot (n-1)!}{r_1!\ldots r_k!} \\ & = & \frac{n!}{r_1!\ldots r_k!} \\ & = & {n \choose r_1, r_2\ldots, r_k}. \end{eqnarray*}