6
$\begingroup$

I need to show that $$\sum\limits_{k=i}^{n}\binom{n}{k}\binom{k}{i} = \binom{n}{i}2^{n-i}$$

I know that $\displaystyle \binom{n}{k}\binom{k}{i}$ is counting the number of ways to pick $k$ elements from $n$ and then $i$ elements from those $k$, so $\displaystyle \sum\limits_{k=i}^{n}\binom{n}{k}\binom{k}{i}$ is counting the number of ways to do that $\forall k$.

I know that $\displaystyle \binom{n}{i} = \binom{n}{n-i}$ and that $2^{n-i}$ is the number of elements in the power set for $[n]\setminus[i]$.

How do I show that both sides are equivalent? I'm stumped on this one. Could anyone give me a pointer in the right direction?

$\endgroup$
4
$\begingroup$

HINT: On both sides you’re actually dividing the pool of $n$ things into three sets. One of those sets contains exactly $i$ objects, one contains $k-i$ for some $k$, and the third contains the $n-k$ that are left. For the righthand side, note that once you’ve chosen two of those sets, you no longer have to choose the third: it’s simply what’s left.

(This is a skimpier hint than I often give, because you’ve already done most of the work: you just need to see how to put the pieces together.)

$\endgroup$
1
$\begingroup$
  • Let's start with the RHS: you choose $i$ elements among $n$ (there are $\binom{n}{i}$ choices), then choose an arbitrary subset of the remaining $n-i$ elements ($2^{n-i}$ choices).

  • Now, the LHS: you choose a size of subset $k\geq i$, then choose $k$ elements out of $n$, then choose $i$ elements out of this $k$-element set $S$. At the end, you have a subset of $i$ elements, and an arbitrary subset of $n-i$ elements (the union of the $k-i$ remaining elements from $S$, and of the $n-k$ elements).

$\endgroup$
1
$\begingroup$

We'll play a game. We're with $n$ people, but not everyone will play. We'll now pick a team red (with $i$ members) and a team blue (not equal teams- the number of members in team blue is not fixed). There are ${n\choose i}$ ways to pick team red - then we decide for every person left, whether or not he/she will be in team blue (which are $2^{n-i}$ possibilities) so total $${n\choose i}2^{n-i}$$ possibilities.


We can also first choose $k$ people who'll play (at least $i$, since we'll need to be able to make team red. ${n\choose k}$ possibilities). After that, we pick $i$ people to be in team red (${k\choose i}$ possibilities), making the total possibilities $$\sum_{k=i}^n{n\choose k}{k\choose i}$$
Thus, we arrive at the conclusion that $$\sum_{k=i}^n{n\choose k}{k\choose i}={n\choose i}2^{n-i}$$

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