# ${10 \choose 4}+{11 \choose 4}+{12 \choose 4}+\cdots+{20 \choose 4}$ can be simplified as which of the following?

${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}$

-
Brotip: You can use {n \choose k} for nCk, which will give the more readable (IMO) $${n \choose k}$$ – Peter Tamaroff Jun 30 '12 at 20:39
Should the third term be 12 choose 4? – Matthew Conroy Jun 30 '12 at 20:39
What would happen if you added $\binom{10}{5}$ to the beginning of the expression? A chain reaction... – alex.jordan Jun 30 '12 at 20:39
Got it @alex.jordan Thanks. – Bazinga Jun 30 '12 at 20:43

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}

-