I would like to obtain a closed form for the following:
$${n \choose 0}{n \choose k} + {n \choose 1}{n-1 \choose k-1} + {n \choose 2}{n-2 \choose k-2} + … + {n \choose k}{n-k \choose 0}$$
To me, this looked like it closely resembles the Binomial Theorem, which I know to be: $(a+b)^k=\sum_{k=0}^n\binom nk a^k b^{n-k},$ but I couldn't get it to work.
The $\sum{n \choose k}$ bit falls nicely in the Binomial expansion, but I don't know how to manipulate $a$ and $b$ to represent $\sum_{i=0}{n-i \choose k-i}$. How should I go about this?
Best Answer
Your sum can be rewritten in sigma notation as $$ \sum_{j = 0}^k \binom{n}{j} \binom{n-j}{k-j}.$$ We observe that for $j = 0, \dots, k$, we have $$ \binom{n}{j} \binom{n-j}{k-j} = \frac{n!}{j!(n-j)!} \frac{(n-j)!}{(n-k)!(k-j)!} = \frac{n!}{k! (n-k)!} \frac{k!}{j!(k-j)!} = \binom{n}{k} \binom{k}{j}.$$ Summing over $j$ gives $$ \sum_{j = 0}^k \binom{n}{j} \binom{n-j}{k-j} = \sum_{j = 0}^k \binom{n}{k} \binom{k}{j} = 2^k \binom{n}{k}.$$