IIT-JEE 2003Question 1
Prove that $$2^k\binom{n}{0}\binom{n}{k}-2^{k-1}\binom{n}{1}\binom{n-1}{k-1}+2^{k-2}\binom{n}{2}\binom{n-2}{k-2}-\cdots+(-1)^k\binom{n}{k}\binom{n-k}{0}=\binom{n}{k}$$
Binomial Theorem · Properties and Sums of Binomial Coefficients
Answerproved: sum equals C(n,k)
Solution
Concept. Rewrite $\binom nj\binom{n-j}{k-j}$ as $\binom nk\binom kj$; then the sum is $\binom nk(2-1)^k$. Formulas used. (1) $\dbinom nj\dbinom{n-j}{k-j}=\dbinom nk\dbinom kj$(2) $\sum_{j=0}^{k}\dbinom kj(-1)^j\,2^{k-j}=(2-1)^k$Step 1 - Prove (1). Both sides equal $\dfrac{n!}{j!\,(k-j)!\,(n-k)!}$: $$\frac{n!}{j!\,(n-j)!}\cdot\frac{(n-j)!}{(k-j)!\,(n-k)!}=\frac{n!}{k!\,(n-k)!}\cdot\frac{k!}{j!\,(k-j)!}.$$ Step 2 - The general term. The $j$-th term ($j=0,\dots,k$) is $(-1)^j\,2^{k-j}\binom nj\binom{n-j}{k-j}$. By (1) it equals $\binom nk\cdot(-1)^j\binom kj\,2^{k-j}$. Step 3 - Sum. Take $\binom nk$ out and use (2): $$\text{LHS}=\binom nk\sum_{j=0}^{k}\binom kj(-1)^j\,2^{k-j}=\binom nk(2-1)^k=\binom nk.$$ Hence proved.