Sum of products of combinatorials 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?
 A: 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}$
A: $$
\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}$
A: 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}$.
A: 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}.$$
