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

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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