# Combinatorial proof for $\sum_{k=0}^p {p+q\choose k} {p+q-k\choose p-k}=2^p {p+q \choose p}$

I'm looking for a combinatorial proof of the identity: $$\sum_{k=0}^p {p+q\choose k} {p+q-k\choose p-k}=2^p {p+q \choose p} \text{ (1)}$$ I'm especially curious about its relationship with this other identity: $$\sum_{k=0}^n {p\choose k} {q\choose n-k}= {p+q \choose n} \text{ (2)}$$ Formula (2) is obvious in the sense that choosing $$n$$ elements from two sets of $$p$$ and $$q$$ elements respectively could be done in $$n$$ distinct ways, but there surely is a nuance I'm missing because I don't see how this is any different from the LHS of (1). Thanks in advance

Consider the number of ways to choose $$p$$ objects from $$p+q$$ and colour each one red or blue. We first choose $$k$$ objects to be coloured red, which has $${p+q} \choose k$$ ways to do so, and then we choose another $$p-k$$ objects to be coloured blue, which has $${p+q-k} \choose {p-k}$$ ways. Summing over $$k$$ gives the LHS, but the number of ways to do this is also clearly the RHS, since we are choosing p objects, each with 2 possibilities for each colour.

The two identities you've given are also not the same; there's a $$-k$$ in one of the upper arguments in the first identity but not the second.

• To add to your answer, the difference between the two identities is that, the second identity reflects the situation where the objects are already colored: $p$ red and $q$ blue. – Quang Hoang May 22 at 13:31
• This is clear and to the point thank you. – FuzzyPixelz May 22 at 13:33

It's tidier to substitute $$q=n-p$$: $$\sum_{k=0}^p {n\choose k} {n-k\choose p-k}=2^p {n \choose p}$$

Choose $$p$$ elements from $$n$$ in two rounds. $$k$$ counts the elements chosen in the first round.

Note that:

$$\binom{p+q-k}{p-k} \times \binom{p+q}{k} = \frac{(p+q-k)!}{(p-k)! q!} \times \frac{(p+q)!}{(p+q-k)! k!}$$

$$=\frac{(p+q)!}{k! (p-k)! q!}$$

Multiply and divide by $$p!$$.

$$= \frac{p! \times \binom{p+q}{p} }{k! (p-k)!}$$

$$= \binom{p}{k} \times \binom{p+q}{p}$$

Now use the fact that,

$$\sum_{k=0}^{n} \binom{p}{k} = 2^p$$

Consider the number of strings of length $$p+q$$ such that

• at $$p$$ positions there is either $$0$$ or $$1$$ and
• at the remaining $$q$$ positions there is $$2$$

Now,

RHS:

• Choose $$p$$ positions from $$p+q$$ positions and fill these $$p$$ positions with $$0$$'s and $$1$$'s resp. (The remaining positions are filled with $$2$$'s): $$\color{blue}{\binom{p+q}{p}\cdot 2^p}$$

LHS: (split the counting according to the number of occurring $$0$$'s)

• Choose $$k$$ from $$p+q$$ positions to place there $$0$$'s and choose $$p+q-k$$ positions to place there $$1$$'s. (The remaining positions are filled with $$2$$'s): $$\color{blue}{\sum_{k=0}^p\binom{p+q}{k}\binom{p+q-k}{p-k}}$$