Prove $\displaystyle\sum_{r=1}^{n-2} r.\binom{n-r}{2}=\binom{n+1}{4}$

Question

How to prove $\displaystyle\sum_{r=1}^{n-2} r.\binom{n-r}{2}=\binom{n+1}{4}$? I tried writing it as an AGP as following: $$\displaystyle\sum_{r=1}^{n-2} r.\binom{n-r}{2} = \textrm{coefficient of } x^2 \textrm{in}\displaystyle\sum_{r=1}^{n-2} r.(1+x)^{n-r} $$ This leads to a huge equation of this sort: $$\textrm{coefficient of x^2 in } \frac{(1+x)^n}{x} + \frac{((1+x)^{n-3}-1).(1+x)^n}{x^2(1+x)^{n-3}} $$ Though i could prove it by this method I would like a better solution.

Answer 1

We can use a combinatorial proof for this. We'll put $n+1$ boxes in a row, and we'll choose $4$. On one hand, of course, this can be done in $\binom{n+1}{4}$ ways, but we'll need the left hand side too. We'll look at specific choices. We first choose a "special" box, and let the number of boxes that's on the left of it be $r$ (where $r$ must range from $1$ to $n-2$. Note that the number of boxes on the right of the special box is now $n-r$). Now we choose a box that's left of that special box (and this is possible since there's at least one box left of the special box. There are $r$ possibilities for this), and two on the right (also always possible, since there are at least $2$ boxes on the right of the special box. There are $\binom{n-r}{2}$ possibilities for this). So, for every $r$ we have $r\binom{n-r}{2}$ possibilities. Now to get all possibilities (we're picking $4$ boxes this way, that the second box from the left is "special" is irrelevant), we just add all of them up and see:

$$\sum_{r=1}^{n-2}r\binom{n-r}{2}=\binom{n+1}{4}$$

---

We can even generalize this, using an equivalent method, to:

For any $0\leq m< k\leq n$, we must have $$\sum_{r=m}^{n-k+m}\binom{r}{m}\binom{n-r-1}{k-m-1}=\binom{n}{k}$$

now we can choose $n=a+1$, $k=4$, $m=1$ to get the equality we just derived.

Answer 2

$\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{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Longleftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,\mathrm{Li}_{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\ul}[1]{\underline{#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_{r = 1}^{n - 2}r{n - r \choose 2} & = \sum_{r = 1}^{n - 2}r\bracks{z^{2}}\pars{1 + z}^{n - r} = \bracks{z^{2}}\pars{1 + z}^{n}\sum_{r = 1}^{n - 2}\pars{1 \over 1 + z}^{r}r \\[5mm] & = \left.\bracks{z^{2}}\pars{1 + z}^{n}\,x\,\partiald{}{x}\sum_{r = 1}^{n - 2}x^{r} \,\right\vert_{\ x\ =\ 1/\pars{1 + z}} = \left.\bracks{z^{2}}\pars{1 + z}^{n}\,x\,\partiald{}{x}\sum_{r = 1}^{n - 2}x^{r} \,\right\vert_{\ x\ =\ 1/\pars{1 + z}} \\[5mm] & = \left.\bracks{z^{2}}\pars{1 + z}^{n}\, x\,\partiald{}{x}\pars{x\,{x^{n - 2} - 1 \over x - 1}} \,\right\vert_{\ x\ =\ 1/\pars{1 + z}} \\[5mm] & = -\bracks{z^{2}}\pars{1 + z}^{n}\pars{z + 1}\,\partiald{}{z} \pars{{1 \over z + 1}\,{\pars{z + 1}^{2 - n} - 1 \over 1/\pars{1 + z} - 1}} \\[5mm] & = \bracks{z^{2}}\pars{1 + z}^{n + 1}\partiald{}{z} \bracks{\pars{1 + z}^{2 - n} - 1 \over z} \\[5mm] & = \bracks{z^{2}}\pars{1 + z}^{n + 1} \bracks{{\pars{2 - n}\pars{1 + z}^{1 - n} \over z} - {\pars{1 + z}^{2 - n} \over z^{2}} + {1 \over z^{2}}} \\[5mm] & = \pars{2 - n}\ \overbrace{\bracks{z^{3}}\pars{1 + z}^{2}}^{\ds{=\ 0}}\ -\ \overbrace{\bracks{z^{4}}\pars{1 + z}^{3}}^{\ds{=\ 0}}\ +\ \bracks{z^{4}}\pars{1 + z}^{n + 1} \\[3mm] & = \bbox[15px,#ffe,border:1px dotted navy]{\ds{n + 1 \choose 4}} \end{align}