Solution Verification: Show that $\sum_{i=0}^{n}{\binom{n+a}{n-i}\binom{i+a+1}{i}}=2^{n}\binom{n+a}{a}+2^{n-1}\binom{n+a}{a+1}$ for $n\geq 1$

Question

I solved it by counting the same object using different methods. Say that there are $n+a$ boys and $1$ girl. I want to form a team of $a+1$ kids with some reserve players, but I want the girl to be either in the team or at least be a reserve player.

Method 1

I first select $i+a$ boys, then from these and the girl ($i+a+1$ kids) I select $a+1$ to be in the team while the rest ($i$ kids) will be the reserve players. The number of possibilities is;

$\sum_{i=0}^{n}{\binom{n+a}{i+a}\binom{i+a+1}{a+1}}= \sum_{i=0}^{n}{\binom{n+a}{n-i}\binom{i+a+1}{i}} $

Method 2

If the girl is in the team, then I need to select $a$ boys to complete the team while the remaining $n$ boys can be reserve players or not. The number of possibilities is;

$2^{n}\binom{n+a}{a}$

If the girl is only a reserve player, I need to select $a+1$ boys to be in the team while the remaining $n-1$ boys can be reserve players or not. The number of possibilities is;

$2^{n-1}\binom{n+a}{a+1}$

Conclusion

Since both method count the same objects then I can conclude that;

$\sum_{i=0}^{n}{\binom{n+a}{n-i}\binom{i+a+1}{i}}=2^{n}\binom{n+a}{a}+2^{n-1}\binom{n+a}{a+1}$

I want to know if my solution is correct and if there’s any different solution out there.

Answer 1

OP asks for an alternate evaluation of

$$\sum_{q=0}^n {n+a\choose n-q} {a+1+q\choose q}.$$

We have by inspection that this is

$$[z^n] (1+z)^{n+a} \frac{1}{(1-z)^{a+2}}$$

which is in turn

$$\underset{z}{\mathrm{res}}\; \frac{1}{z^{n+1}} (1+z)^{n+a} \frac{1}{(1-z)^{a+2}}.$$

Now we put $z/(1+z) = w$ so that $z=w/(1-w)$ and $dz = 1/(1-w)^2 \; dw$ to get

$$\underset{w}{\mathrm{res}}\; \frac{1}{w^n} \frac{1-w}{w} \frac{1}{(1-w)^a} \frac{(1-w)^{a+2}}{(1-2w)^{a+2}} \frac{1}{(1-w)^2} \\ = \underset{w}{\mathrm{res}}\; \frac{1-w}{w^{n+1}} \frac{1}{(1-2w)^{a+2}}.$$

This is

$$[w^n] (1-w) \frac{1}{(1-2w)^{a+2}} = 2^n {n+a+1\choose a+1} - 2^{n-1} {n+a\choose a+1} \\ = 2^n \frac{n+a+1}{a+1} {n+a\choose a} - 2^{n-1} {n+a\choose a+1} \\ = 2^n {n+a\choose a} + 2^n \frac{n}{a+1} {n+a\choose a} - 2^{n-1} {n+a\choose a+1} \\ = 2^n {n+a\choose a} + 2^{n-1} {n+a\choose a+1}$$

which is the claim.