3
$\begingroup$

I've been given the task of calculating: $$\sum_{k=1}^{10}k{{10}\choose{k}}{{20}\choose{10-k}}$$

I've tried to start with what I'm familiar with - $\sum_{k=0}^{10}{{10}\choose{k}}{{20}\choose{10-k}}$. I've tried adding the value of $k=0$ to the sum, which is $0{{10}\choose{0}}{{20}\choose{10}} = 0$ and then subtracting it to get the equality: $$\sum_{k=1}^{10}{{10}\choose{k}}{{20}\choose{10-k}} = \sum_{k=0}^{10}{{10}\choose{k}}{{20}\choose{10-k}} - 0$$

Combinatorically, this is equal to ${30}\choose{10}$.

However, I'm stuck with that $k$ which is in the beginning of each value of the sum: $\sum_{k=1}^{10}\color{red}{k}{{10}\choose{k}}{{20}\choose{10-k}}$. I just can't seem to find a way to solve this algebraically, or combinatorically. I feel like I'm missing something really basic here but I can't point the finger to what it may be. Suggestions are greatly appreciated!

$\endgroup$
  • $\begingroup$ Hint: $$ k\binom{10}{k}=10\binom{9}{k-1} $$ $\endgroup$ – Jack D'Aurizio Jan 23 '18 at 19:52
5
$\begingroup$

$$\sum_{k=1}^{10}k\binom{10}{k}\binom{20}{10-k} = 10\sum_{k=1}^{10}\binom{9}{k-1}\binom{20}{10-k} \stackrel{k\mapsto j+1}{=} 10\sum_{j=0}^{9}\binom{9}{j}\binom{20}{9-j} $$ equals $10\binom{29}{9}$ by Vandermonde's identity.

$\endgroup$
  • $\begingroup$ As stated by yourself in the comment, I'll look up the first equality and see if I understand that transition. Also, the second transition from the middle part to the right part of the equality, is it because you added another value to the sum, you also updated all of your $k$s to be $k+1$, thus resulting in the right side of the equality? $\endgroup$ – 0rka Jan 23 '18 at 20:01
  • $\begingroup$ @0rka: exactly. $\endgroup$ – Jack D'Aurizio Jan 23 '18 at 20:02
  • $\begingroup$ Brilliant. Thank you! $\endgroup$ – 0rka Jan 23 '18 at 20:08
  • $\begingroup$ Jack, after looking at this again I noticed that in the right side equality you changed to top part of the sum to be $9$ instead of $10$. Can you elaborate some more on that transition? I thought you only added another value, but seems as though you have "subtracted" from $k=1$ and from $10$. $\endgroup$ – 0rka Jan 23 '18 at 21:08
  • $\begingroup$ @0rka: answer edited, I hope it is more clear now. I just applied a reindexing. $\endgroup$ – Jack D'Aurizio Jan 23 '18 at 21:25
0
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{k = 1}^{10}k{10 \choose k}{20\choose 10 - k} & = \sum_{k = 1}^{10}k{10 \choose k}\bracks{z^{10 - k}}\pars{1 + z}^{20} = \bracks{z^{10}}\pars{1 + z}^{20}\sum_{k = 1}^{10}{10 \choose k}kz^{k} \\[5mm] & = \bracks{z^{10}}\pars{1 + z}^{20}\,z\,\totald{}{z} \sum_{k = 1}^{10}{10 \choose k}z^{k} = \bracks{z^{9}}\pars{1 + z}^{20}\,\totald{\pars{1 + z}^{10}}{z} \\[5mm] & = 10\bracks{z^{9}}\pars{1 + z}^{29} = 10{29 \choose 9} = \bbx{100150050} \end{align}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.