Sum of products of combinatorials

Question

In the proof of some proposition, it appears that the following statement should hold:

$$ \sum_{r=1}^{n+1} \sum_{\beta=0}^{r-1} C^{n+1}_r C^n_{\beta} =2^{2n}. $$

However, using the definition of combinatorials does not help:

$$ \sum_{r=1}^{n+1} \sum_{\beta=0}^{r-1} C^{n+1}_r C^n_{\beta} = \sum_{r=1}^{n+1} \sum_{\beta=0}^{r-1} \frac{(n+1)!}{(n+1-r)!r!} \frac{n!}{(n-\beta)! \beta!}.$$

I suspect that this has something to do with the binomial expansion. Any ideas?

Answer 1

Let the sum be $S$. By using the definition $C^n_r=C^n_{n-r}$, we’ll change the sum into:

$\quad S \\= \sum_{r=1}^{n+1} \sum_{\beta=0}^{r-1} C^{n+1}_r C^{n}_\beta \\ = \sum_{0 \le \beta < r \le n+1} C^{n+1}_r C^{n}_\beta \\ = \sum_{0 \le \beta < r \le n+1} C^{n+1}_{n-r+1} C^{n}_{n-\beta}$

Let $s=n-r+1$ and $\alpha=n-\beta$, then by the inequality $0 \le \beta < r \le n+1$, we’ll get $$0 \le s \le \alpha \le n+1$$ Substitute back to the sum and changing the variables:

$\quad\sum_{0 \le \beta < r \le n+1} C^{n+1}_{n-r+1} C^{n}_{n-\beta} \\ = \sum_{0 \le s \le \alpha \le n+1} C^{n+1}_s C^n_\alpha \\= \sum_{0 \le r \le \beta \le n+1} C^{n+1}_r C^n_\beta$

$\quad S+S \\= \sum_{0 \le \beta < r \le n+1} C^{n+1}_r C^{n}_\beta + \sum_{0 \le r \le \beta \le n+1} C^{n+1}_r C^n_\beta \\= \sum_{0 \le r, \beta \le n+1} C^{n+1}_r C^{n}_\beta \\= \left(\sum_{r=0}^{n+1} C^{n+1}_r \right)\left(\sum_{\beta=0}^n C^n_\beta\right) \\= 2^{n+1}2^{n} \\= 2^{2n+1}$

Therefore, the sum $S = \dfrac{2^{2n+1}}{2} = 2^{2n}$

Answer 2

Counting argument actually helps.

Let us count the number of ways to write $(2n+1)$ $0,1$s in a row that the number of $1$s in the first $(n+1)$ digits is strictly bigger than the number of $0$s in the next $n$ digits.

Clearly, it is LHS.

Meanwhile, you can notice that this is just an alternate explanation of counting the number of ways to write $(2n+1)$ $0,1$s in a row that the number of $1$s is at least $(n+1)$, which is $2^{2n}$.

Answer 3

$$ \begin{align} \sum_{r=1}^{n+1}\sum_{\beta=0}^{r-1}\binom{n+1}{r}\binom{n}{\beta} &=\sum_{r=0}^n\sum_{\beta=0}^r\binom{n+1}{r+1}\binom{n}{\beta}\tag1\\ &=\sum_{\beta=0}^n\sum_{r=\beta}^n\binom{n+1}{n-r}\binom{n}{r-\beta}\tag2\\ &=\sum_{\beta=0}^n\binom{2n+1}{n-\beta}\tag3\\ &=\sum_{\beta=0}^n\binom{2n+1}{n+\beta+1}\tag4\\ &=\frac12\sum_{\beta=0}^{2n+1}\binom{2n+1}{\beta}\tag5\\[9pt] &=2^{2n}\tag6 \end{align} $$ Explanation:
$(1)$: substitute $r\mapsto r+1$
$(2)$: change order of summation, substitute $\beta\mapsto r-\beta$,
$\phantom{(2)\text{:}}$ apply the symmetry of Pascal's Triangle
$(3)$: Vandermonde's Identity
$(4)$: apply the symmetry of Pascal's Triangle
$(5)$: average $(3)$ and $(4)$
$(6)$: binomial expansion of $\frac12(1+1)^{2n+1}$

Answer 4

We have

$$\sum_{r=1}^{n+1} {n+1\choose r} \sum_{\beta=0}^{r-1} {n\choose \beta} \\ = \sum_{r=1}^{n+1} {n+1\choose r} \sum_{\beta\ge 0} {n\choose \beta} [[0\le \beta\le r-1]] \\ = \sum_{r=1}^{n+1} {n+1\choose r} \sum_{\beta\ge 0} {n\choose \beta} [z^{r-1}] \frac{z^{\beta}}{1-z} \\ = \sum_{r=1}^{n+1} {n+1\choose r} [z^{r-1}] \frac{1}{1-z} \sum_{\beta\ge 0} {n\choose \beta} z^{\beta} \\ = \mathrm{Res}_{z=0} \frac{1}{1-z} (1+z)^n \sum_{r=1}^{n+1} {n+1\choose r} \frac{1}{z^r} \\ = \mathrm{Res}_{z=0} \frac{1}{1-z} (1+z)^n \left(-1 + \left(1+\frac{1}{z}\right)^{n+1}\right) \\ = \mathrm{Res}_{z=0} \frac{1}{z^{n+1}} \frac{1}{1-z} (1+z)^{2n+1} \\ = \sum_{q=0}^n {2n+1\choose q} = \frac{1}{2} 2^{2n+1} = 2^{2n}.$$