4
$\begingroup$

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

  • 0
    Got it @alex.jordan Thanks.2012-06-30

4 Answers 4

10

HINT 1 :

Add $\dbinom{10}5$

HINT 2:

Make use of the identity $\dbinom{n}{r} + \dbinom{n}{r-1} = \dbinom{n+1}{r}$

2

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)$.

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$.

0

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}