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?

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