looking for combinatorial identity [duplicate]

Question

Does anybody know a nicer expression for the sum $\sum_{i=0}^{k} \binom{n}{i} \binom{n-i}{k-i}$?

Answer 1

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

Answer 2

Suppose that I have a pool of $n$ people and want to form two disjoint committees, $A$ and $B$, using a total of $k$ of the $n$ people. $\binom{n}i\binom{n-i}{k-i}$ is the number of ways to choose $i$ people for committee $A$ and then choose $k-i$ of the remaining $n-i$ members for committee $B$. Summing over $i=0,\ldots,k$ gives the total number of ways to form these committees, including those in which $A$ or $B$ is empty.

This is the same as the number of ways to choose $k$ people from the pool and then select a subset of them to make up committee $A$; committee $B$ will then comprise the people who were among the $k$ initially chosen but are not on committee $A$. This can be done in $2^k\binom{n}k$ ways. Thus,

$$\sum_{i=0}^k\binom{n}i\binom{n-i}{k-i}=2^k\binom{n}k\,.$$