Simplifying $\displaystyle\sum_{k=0}^{20}(k+4)\binom{23-k}{3}$

Question

In trying to simplify my answer to a problem posted recently, I am trying to show that $\displaystyle\sum_{k=0}^{20}(k+4)\binom{23-k}{3}=8\binom{24}{4}$.

I know that $\displaystyle\sum_{k=0}^{20}\binom{23-k}{3}=\binom{24}{4}$, but how can I simplify $\displaystyle\sum_{k=0}^{20}k\binom{23-k}{3}$?

Answer 1

$\newcommand{\+}{^{\dagger}} \newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,} \newcommand{\dd}{{\rm d}} \newcommand{\down}{\downarrow} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\fermi}{\,{\rm f}} \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\isdiv}{\,\left.\right\vert\,} \newcommand{\ket}[1]{\left\vert #1\right\rangle} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\pp}{{\cal P}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\sech}{\,{\rm sech}} \newcommand{\sgn}{\,{\rm sgn}} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\ul}[1]{\underline{#1}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert} \newcommand{\wt}[1]{\widetilde{#1}}$ Note that $$ 4 + k=\pars{k - 20} + 24 = 24 - \pars{20 - k} $$

\begin{align} &\sum_{k = 0}^{20}\pars{k + 4}{23 - k \choose 3} ={1 \over 6}\sum_{k = 0}^{20}\pars{23 - k}\pars{22 - k}\pars{21 - k} \bracks{24 - \pars{20 - k}} \\[3mm]&=4\sum_{k = 0}^{20}\pars{23 - k}\pars{22 - k}\pars{21 - k} -{1 \over 6}\sum_{k = 0}^{20}\pars{23 - k}\pars{22 - k}\pars{21 - k}\pars{20 - k} \end{align}

Lets consider $\ds{\fermi\pars{x}\equiv\sum_{k = 0}^{20}x^{23 - k} =x^{23}\,{x^{-21} - 1 \over x^{-1} - 1} = {x^{3} - x^{24} \over 1 - x}}$

Then, \begin{align}&\color{#66f}{\large\sum_{k = 0}^{20}\pars{k + 4}{23 - k \choose 3}}= \lim_{x \to 1}\bracks{% 4\fermi'''\pars{x} - {1 \over 6}\,\fermi^{\tt\pars{IV}}\pars{x}} \\[3mm]&=4 \times 63756 - {1 \over 6}\times 1020096 =255024 - 170016 = \color{#66f}{\large 85008} \end{align}

Note that ( with $\ds{x \equiv 1 + \epsilon}$ ): \begin{align} &{x^{3} - x^{24} \over 1 - x} ={\pars{1 + \epsilon}^{24} - \pars{1 + \epsilon}^{3} \over \epsilon} ={1 \over \epsilon}\sum_{k = 0}^{24}{24 \choose k}\epsilon^{k} -{1 \over \epsilon}\sum_{k = 0}^{3}{3 \choose k}\epsilon^{k} \\[3mm]&=\sum_{k = 1}^{24}{24 \choose k}\epsilon^{k - 1} -\sum_{k = 1}^{3}{3 \choose k}\epsilon^{k - 1} \\[3mm]&=\bracks{{24 \choose 1} + {24 \choose 2}\epsilon +{24 \choose 3}\epsilon^{2} + \color{#c00000}{{24 \choose 4}\epsilon^{3}} +\color{#c00000}{{24 \choose 5}\epsilon^{4}} + \cdots} -\bracks{{3 \choose 1} + {3 \choose 2}\epsilon +{3 \choose 3}\epsilon^{2}} \end{align}

such that \begin{align}&\color{#66f}{\large\sum_{k = 0}^{20}\pars{k + 4}{23 - k \choose 3}}= 4\bracks{{24 \choose 4}6} - {1 \over 6}\,\bracks{{24 \choose 5}24} =\color{#66f}{\large24{24 \choose 4} - 4{24 \choose 5}} \\[3mm]&= {\tt 85008} \end{align}

Answer 2

Maple gives $$\sum_{k=1}^n k\binom{m+n-k}{m} =\frac{(m+n)(m+n+1)}{(m+1)(m+2)}\binom{m+n-1}{m}\ ,$$ which can be checked by induction if you wish. So your sum becomes $$4\binom{24}{4}+\frac{23\times24}{4\times5}\binom{22}{3} =4\binom{24}{4} +\frac{23\times24}{4\times5}\frac{4\times20}{23\times24}\binom{24}{4} =8\binom{24}{4}\ .$$

Answer 3

So you want to prove $$\sum^{20}_{k=1}k\binom{23-k}{3}=4\binom{24}{4}\color{red}{=\binom{24}{5}}.$$

With that note, it's easy to come up with a combinatorial argument: How many ways to choose $a_1<a_2<\cdots<a_5$ out of $\{1,2,\dots,24\}$?

$a_2$ can only be in $\{2,\dots, 21\}$. For $a_2=k+1\in\{2,\dots,21\}$, there's $k$ choices of $a_1$ and $\binom{23-k}{3}$ choices of $(a_3,a_4,a_5)$. The equality follows.