Prove That $\sum\sum\binom{k-m-mi}{i}=\sum\binom{n+1-mj}{j}$

binomial-coefficientscombinatorial-proofscombinatoricssolution-verification

Question

This is inspired by a question regarding the same identity for special case $m=1$ : $\sum_{k=1}^n \sum_{i=0}^{k-1}\binom{k-1-i}{i}=\sum_{j=0}^{n+1} \binom{n+1-j}{j}-1$ . I want to prove that the following expression is true for non negative integers $m$:

$$
\sum_{k=m}^{n}{\sum_{i=0}^{\left\lfloor\frac{k-m}{m+1}\right\rfloor}{\binom{k-m-mi}{i}}}=\sum_{j=1}^{\left\lfloor\frac{n+1}{m+1}\right\rfloor}{\binom{n+1-mj}{j}}
$$

My Solution

Left Hand Side

If we have $k+1$ indistinguishable candies and distribute it to $i+1$ distinguishable boxes where each box contain at least $m+1$ candies, the number of possible distribution is given by the binomial coefficient on the left side using Stars and Bars:

$$
\binom{(k+1)-m(i+1)-1}{(i+1)-1}=\binom{k-m-mi}{i}
$$

The left hand side then gives the number of all possible distribution of $m+1,m+2,…,n+1$ candies to all possible number of boxes:

$$
\sum_{k=m}^{n}{\sum_{i=0}^{\left\lfloor\frac{k-m}{m+1}\right\rfloor}{\binom{k-m-mi}{i}}}
$$

Right Hand Side

For each candies distribution, add another box filled with at least $m+1$ candies so that the total number of candies being distributed is always $n+m+2$. Notice that we get all possible distribution of $n+m+2$ indistinguishable candies to all possible number of boxes where each box contains at least $m+1$ candies, except the distribution in which all $n+m+2$ candies are in one box. The right hand side gives the number of these possible distribution:

$$
\sum_{j=1}^{\left\lfloor\frac{n+1}{m+1}\right\rfloor}{\binom{n+1-mj}{j}}
$$

Conclusion

Since both left and right hand sides are used to count the same objects they must be equal.

Seeking Help

Need your help to see if my solution is correct and I will also appreciate alternatives and discussions

Best Answer

The nice binomial identity \begin{align*} \color{blue}{\sum_{k=m}^n\sum_{j=0}^{\left\lfloor\frac{k-m}{m+1}\right\rfloor}\binom{k-m-mj}{j}=\sum_{j=1}^{\left\lfloor\frac{n+1}{m+1}\right\rfloor}\binom{n+1-mj}{j}\qquad\qquad 0\leq m\leq n}\tag{1} \end{align*} is correct. Here is an algebraic proof.

We obtain \begin{align*} \color{blue}{\sum_{k=m}^n\sum_{j=0}^{\left\lfloor\frac{k-m}{m+1}\right\rfloor}\binom{k-m-mj}{j}} &=\sum_{k=0}^{n-m}\sum_{j=0}^{\left\lfloor\frac{k}{m+1}\right\rfloor}\binom{k-mj}{j}\tag{2}\\ &=\sum_{j=0}^{\left\lfloor\frac{n-m}{m+1}\right\rfloor}\sum_{k=j(m+1)}^{n-m}\binom{k-mj}{j}\tag{3}\\ &=\sum_{j=0}^{\left\lfloor\frac{n-m}{m+1}\right\rfloor}\sum_{k=j}^{n-m-jm}\binom{k}{j}\tag{4}\\ &=\sum_{j=0}^{\left\lfloor\frac{n-m}{m+1}\right\rfloor}\binom{n-m-jm+1}{j+1}\tag{5}\\ &=\sum_{j=1}^{\left\lfloor\frac{n-m}{m+1}\right\rfloor+1}\binom{n-jm+1}{j}\tag{6}\\ &\,\,\color{blue}{=\sum_{j=1}^{\left\lfloor\frac{n+1}{m+1}\right\rfloor}\binom{n-jm+1}{j}}\\ \end{align*} and the claim (1) follows.

Comment:

  • In (2) we shift the index of the outer sum to start with $k=0$.

  • In (3) we exchange the sums. We observe considering the upper index of the binomial coefficient $\binom{k-mj}{j}$: \begin{align*} k-mj&\geq j\\ mj+j&\geq k\\ k&\geq j(m+1) \end{align*}

  • In (4) we shift the index of the inner sum to start with $k=j$.

  • In (5) we apply the hockey-stick identity.

  • In (6) we shift the index to start with $j=1$.

Related Question