IIT-JEE 1989Question 1
Using mathematical induction, prove that ${}^{m}C_0\,{}^{n}C_k+{}^{m}C_1\,{}^{n}C_{k-1}+\cdots+{}^{m}C_k\,{}^{n}C_0={}^{(m+n)}C_k$, where $m,n,k$ are positive integers, and ${}^{p}C_q=0$ for $p<q$.
Binomial Theorem · Properties and Sums of Binomial Coefficients
Answerproved
Solution
Concept. Induct on $m$, for all $n$ and $k$ at once; Pascal's rule splits ${}^{m+1}C_i$. Formulas used. (1) Pascal: ${}^{p}C_i={}^{p-1}C_i+{}^{p-1}C_{i-1}$Step 1 - Statement. $P(m)$: $\sum_{i=0}^{k}{}^{m}C_i\,{}^{n}C_{k-i}={}^{m+n}C_k$ for all $n\ge1$ and all $k\ge0$. (For $k=0$ both sides are $1$.) Step 2 - Base case $m=1$. The left side is ${}^{n}C_k+{}^{n}C_{k-1}$, which is ${}^{n+1}C_k$ by (1). True. Step 3 - Inductive step. Assume $P(m)$. By (1), ${}^{m+1}C_i={}^{m}C_i+{}^{m}C_{i-1}$, so $$\sum_{i}{}^{m+1}C_i\,{}^{n}C_{k-i}=\sum_{i}{}^{m}C_i\,{}^{n}C_{k-i}+\sum_{j}{}^{m}C_j\,{}^{n}C_{k-1-j}$$ (with $j=i-1$ in the second sum). Step 4 - Use $P(m)$ twice. The right side is ${}^{m+n}C_k+{}^{m+n}C_{k-1}={}^{m+n+1}C_k$ by (1). This is $P(m+1)$. Step 5 - Conclude. By induction, $P(m)$ holds for all positive integers $m$. Hence proved.