# Combinatorial argument for $\sum\limits_{k=i}^{n}\binom{n}{k}\binom{k}{i} = \binom{n}{i}2^{n-i}$

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?

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.)

• 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).

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