prove $\sum_{r=1}^{n-1}(n-r)^2\binom{n-1}{n-r}=n(n-1)2^{n-3}$

Question

This is problem 2.38 from the book "Principles and Techniques in Combinatorics".

Prove $$\sum_{r=1}^{n-1}(n-r)^2\binom{n-1}{n-r}=n(n-1)2^{n-3}$$ I have have been trying different things on and off for two days and still can't derive RHS from LHS. what I have got so far: $$\sum_{r=1}^{n-1}(n-r)^2\cdot\frac{n-1}{n-r}\binom{n-2}{n-r-1} =(n-1)\sum_{r=1}^{n-1}(n-r)\cdot\binom{n-2}{n-r-1} =\\(n-1)\sum_{r=2}^{n}(n-r)\cdot\binom{n-2}{n-r} =(n-1)\sum_{r=2}^{n}(n-r)\cdot\binom{n-2}{n-r} =\\(n-1)\sum_{r=2}^{n}(n-r)\cdot\frac{n-2}{n-r}\binom{n-3}{n-r-1} =\\(n-1)(n-2)\sum_{r=2}^{n}\cdot\binom{n-3}{n-r-1} $$ any hints or solutions would be greatly appreciated.

Answer 1

A good skill for such problems is knowing how to rewrite expressions in simpler forms. I'd rather write the LHS as $\sum_{i=1}^{n-1}i^2\binom{n-1}{i}$, letting $i=n-r$. Instead of rewriting this side, I'm going to interpret this combinatorially, meaning I'm going to express it as counting something, and then I'll show that the RHS counts the same thing (hopefully, you've seen such techniques before). We start with a set of $n-1$ elements. The LHS says that we choose $i$ of those elements, where $1\leq i\leq n-1$, and we choose a pair $(a,b)$ of those $i$ elements we picked, where we can have $a=b$. Think of starting with $n-1$ people and forming a committee from some subset of them with a president and treasurer, and the president may also be the treasurer.

Now we need to show that the RHS counts the same thing. Observe that $n(n-1)2^{n-3}=(n-1)(n-2)2^{n-3}+(n-1)2^{n-2}$. Can you see how this also counts the same thing? Hint: consider the case when the president and treasurer are different people, and when they're the same person.

Answer 2

Hint

Rewrite the sum as $$ \sum_{k=1}^{n-1}k^2\binom{n-1}{k}. $$ Note that $$ \sum_{u=1}^{n-1}\binom{n-1}{k}x^k=(1+x)^{n-1}-1 $$ and finally note that $$ \sum_{k=1}^{n-1}k^2\binom{n-1}{k}=\frac{d^2}{dx^2}[(1+x)^{n-1}-1]\biggr|_{x=1}+\frac{d}{dx}[(1+x)^{n-1}-1]\biggr|_{x=1} $$

Answer 3

$\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_{r = 1}^{n - 1}\pars{n - r}^{2}{n - 1 \choose n - r} & = \sum_{r = 0}^{n - 1}{n - 1 \choose r}r^{2} = \left.\partiald{}{x}\pars{x\,\partiald{}{x}}\ \sum_{r = 0}^{n - 1}{n - 1 \choose r}x^{r}\,\right\vert_{\ x\ =\ 1} \\[5mm] & = \left.\partiald{}{x}\pars{x\,\partiald{}{x}}\ \pars{1 + x}^{n - 1}\,\right\vert_{\ x\ =\ 1} = \pars{n - 1}\left.\partiald{}{x}\bracks{x\ \pars{1 + x}^{n - 2}}\,\right\vert_{\ x\ =\ 1} \\[5mm] & = \pars{n - 1}\bracks{% \pars{1 + x}^{n - 2} + \pars{n - 2}x\pars{1 + x}^{n - 3}}_{\ x\ =\ 1} \\[5mm] & = \pars{n - 1}\bracks{2^{n - 2} + \pars{n - 2}2^{n - 3}} = \bbx{n\pars{n - 1}2^{n - 3}} \end{align}

Answer 4

Another way: $$ \eqalign{ & \sum\limits_{1\, \le \,r\, \le \,n - 1} {\left( {n - r} \right)^{\,2} \left( \matrix{ n - 1 \cr n - r \cr} \right)} = \sum\limits_{1\, \le \,k\, \le \,n - 1} {k^{\,2} \left( \matrix{ n - 1 \cr k \cr} \right)} = \cr & = \sum\limits_{0\, \le \,k\, \le \,n - 1} {k^{\,2} \left( \matrix{ n - 1 \cr k \cr} \right)} = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n - 1} \right)} {\left( {k\left( {k - 1} \right) + k} \right)\left( \matrix{ n - 1 \cr k \cr} \right)} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n - 1} \right)} {k\left( {k - 1} \right)\left( \matrix{ n - 1 \cr k \cr} \right)} + \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n - 1} \right)} {k\left( \matrix{ n - 1 \cr k \cr} \right)} = \cr & = \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n - 1} \right)} {k\left( {k - 1} \right){{\left( {n - 1} \right)^{\,\underline {\,k\,} } } \over {k!}}} + \sum\limits_{\left( {0\, \le } \right)\,k\,\left( { \le \,n - 1} \right)} {k{{\left( {n - 1} \right)^{\,\underline {\,k\,} } } \over {k!}}} = \cr & = \left( {n - 1} \right)\left( {n - 2} \right)\sum\limits_{2\, \le \,k\, \le \,n - 1} {{{\left( {n - 3} \right)^{\,\underline {\,k - 2\,} } } \over {\left( {k - 2} \right)!}}} + \left( {n - 1} \right)\sum\limits_{1\, \le \,k\, \le \,n - 1} {{{\left( {n - 2} \right)^{\,\underline {\,k - 1\,} } } \over {\left( {k - 1} \right)!}}} = \cr & = \left( {n - 1} \right)\left( {n - 2} \right)\sum\limits_{2\, \le \,k\, \le \,n - 1} {\left( \matrix{ n - 3 \cr k - 2 \cr} \right)} + \left( {n - 1} \right)\sum\limits_{1\, \le \,k\, \le \,n - 1} {\left( \matrix{ n - 2 \cr k - 1 \cr} \right)} = \cr & = \left( {n - 1} \right)\left( {n - 2} \right)2^{n - 3} + \left( {n - 1} \right)2^{n - 2} = \cr & = n\left( {n - 1} \right)2^{n - 3} \cr} $$