${10 \choose 4}+{11 \choose 4}+{12 \choose 4}+\cdots+{20 \choose 4}$ can be simplified as ?
A. ${21 \choose 5}$
B. ${20 \choose 5}-{11 \choose 4}$
C. ${21 \choose 5}-{10 \choose 5}$
D. ${20 \choose 4}$
Please give me a hint. I'm unable to group the terms. By brute force, I'm getting ${21 \choose 5}-{10 \choose 5}$
HINT 1 :
Add $\dbinom{10}5$
HINT 2:
Make use of the identity $$\dbinom{n}{r} + \dbinom{n}{r-1} = \dbinom{n+1}{r}$$
The same thing, combinatorially. We want to choose $5$ positive integers from the first $21$. This can be done in $\binom{21}{5}$ ways.
We count the same thing in a different way. If the biggest chosen number is $21$, the rest can be chosen in $\binom{20}{4}$ ways. If the biggest is $20$, the rest can be chosen in $\binom{19}{4}$ ways. If the biggest is $19$, the rest can be chosen in $\binom{18}{4}$ ways. And so on, until if the biggest is $5$, the rest can be chosen in $\binom{4}{4}$ ways. We conclude that $$\binom{20}{4}+\binom{19}{4}+\binom{18}{4}+\cdots+\binom{10}{4}+\binom{9}{4}+\cdots +\binom{4}{4}=\binom{21}{5}. \tag{$1$}$$ The same reasoning shows that $$\binom{9}{4}+\binom{8}{4}+\cdots+\binom{4}{4}=\binom{10}{5}. \tag{$2$}$$
Now subtract $(2)$ from $(1)$.
A variation of Vandermonde's Identity says $$ \sum_{j=m}^{n-k}\binom{n-j}{k}\binom{j}{m}=\binom{n+1}{k+m+1}\tag{1} $$ Seting $k=0$ yields $$ \sum_{j=m}^{n}\binom{j}{m}=\binom{n+1}{m+1}\tag{2} $$ $(2)$ should be useful with $m=4$.
What is the problem in this solution? If $S=\binom{10}{4} + \binom{11}{4} + \cdots + \binom{20}{4}$ we have \begin{eqnarray} S&=& \left \{ \binom{4}{4} + \binom{5}{4} \cdots + \binom{20}{4}\right \} - \left \{\binom{4}{4} + \binom{5}{4} \cdots + \binom{9}{4}\right \} &=& \binom{21}{5} - \binom{10}{5} \end{eqnarray}
{n \choose k}for nCk, which will give the more readable (IMO) $${n \choose k}$$ – Pedro Jun 30 '12 at 20:39