<s>[INST] Does $\sum_{j=0}^n\sum_{k=0}^n\binom{j}{a}\binom{k}{b}\binom{n-j-k}{c}=\binom{n+1}{a+b+c+2}?$ I'm working on a problem,

(a) Let $a,b,n\geq1$ with $a+b\leq n$. By considering choosing $a+b+1$ numbers from the set $\{0,1,...,n\}$, and the possibilities for the number in position $a+1$ when the chosen numbers are listed in increasing order, show that $$\binom{n+1}{a+b+1}=\sum_{k=0}^n\binom{k}{a}\binom{n-k}{b}.$$
(b) Hence, or otherwise, express $$\sum_{j=0}^n\sum_{k=0}^n\binom{j}{a}\binom{k}{b}\binom{n-j-k}{c},$$ where $a+b+c\leq n$, as a single binomial coefficient.

Does the following argument make sense for (b)? (I leave a certain amount implicit.)

Let \begin{align} 
& j && \text{ be the } (a+1)^\text{th} && \text{number chosen}, \\ 
& j+1+k && \text{ be the } (a+1)+(b+1)=(a+b+2)^\text{th} && \text{number chosen;}
\end{align}
Then there are \begin{align}
& \binom{j}{a} && \text{ways of choosing the first $a$ numbers from } [0,j-1], \\
& \binom{k}{b} && \text{ways of choosing the next $b$ numbers from } [j+1,j+k], \\
& \binom{n-j-k}{c} && \text{ways of choosing the next $c$ numbers from } [j+1+k,n];
\end{align}
therefore the given expression is equal to $$\binom{n+1}{a+b+c+2}.$$

 [/INST] We can also derive a closed formula of the double sum by applying the identity
\begin{align*}
\sum_{k=0}^n\binom{k}{a}\binom{n-k}{b}=\binom{n+1}{a+b+1}\tag{1}
\end{align*}
twice.

We obtain
\begin{align*}
\color{blue}{\sum_{j=0}^n}&\color{blue}{\sum_{k=0}^{n-j}\binom{j}{a}\binom{k}{b}\binom{n-j-k}{c}}\tag{2}\\
&=\sum_{j=0}^n\binom{j}{a}\sum_{k=0}^{n-j}\binom{k}{b}\binom{(n-j)-k}{c}\tag{3}\\
&=\sum_{j=0}^n\binom{j}{a}\binom{n-j+1}{b+c+1}\tag{$\to$ (1)}\\
&=\sum_{j=0}^{n+1}\binom{j}{a}\binom{(n+1)-j}{b+c+1}\tag{4}\\
&\,\,\color{blue}{=\binom{n+2}{a+b+c+2}}\tag{$\to$ (1)}\\
\end{align*}
and observe that lower and upper index of the result have a summand $2$.

Comment:

*

*In (2) we set the upper limit of the inner sum to $n-j$ since the upper index of $\binom{n-j-k}{c}$ is non-negative.


*In (3) we make a rearrangement as preparation to apply (1).


*In (4) we set the upper limit of the sum to $n+1$ which does not change the sum, since $\binom{0}{b+c+1}=0$. We observe we can apply (1) again.
</s>