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}?$

Question

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}.$$

Answer 1

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.