1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Quang Hoang May 22 at 13:31
  • $\begingroup$ This is clear and to the point thank you. $\endgroup$ – FuzzyPixelz May 22 at 13:33
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.