# Help with this combinatorial proof $\sum\limits_{k=1}^nk^2(k-1){n\choose k}^2 = n^2(n-1){2n-3\choose n-2}$ considering $n\ge2$

$\displaystyle\sum\limits_{k=1}^nk^2(k-1){n\choose k}^2 = n^2(n-1) {2n-3\choose n-2}$ considering $n\ge2$

Can somebody help with this combinatorial proof? I'm struggling a lot. Thanks.

EDIT: Ok. I could figure it out, if we had $\displaystyle\sum\limits_{k=1}^nk^2{n\choose k}^2 = n^2 {2n-2\choose n-1}$.

The problem is, i don't understand what to do with that $(k-1)$ and how it leads to ${2n-3\choose n-2}$.

I know $k{n\choose k} = n{n-1\choose k-1}$

Choosing a team of $k$ elements from $n$ and from that $k$ elements, pick a captain is the same as choose a captain first, and then, complete the team, choosing $k-1$ elements from $n-1$

But, what about $k(k-1){n\choose k}$ ?

• Where did you get this formula? left-hand side gives $480$ and right hand side gives $160$ for $n=4$... – Jean-Sébastien Apr 10 '14 at 22:19
• I commited a mistake. Now the formula is correct – Vitor Silva Apr 10 '14 at 22:25

Hint: Note that because choosing $k$ elements from a set of $n$ is the same as choosing the complement of the $k$ elements, we have $$\binom{n}{k}=\binom{n}{n-k}\tag{1}$$ and since choosing a team of $k$ people and then a leader from those chosen is the same as choosing a leader and then choosing the remaining $k-1$ from the remaining $n-1$, we get $$k\binom{n}{k}=n\binom{n-1}{k-1}\tag{2}$$ and $$k^2(k-1)=k(k-1)(k-2)+2k(k-1)\tag{3}$$ Then consider Vandermonde's Identity.

Full Solution:

\hspace{-5mm}\begin{align} &\sum_{k=1}^nk^2(k-1)\binom{n}{k}^2\\ &=\sum_{k=1}^nk(k-1)(k-2)\binom{n}{k}\binom{n}{n-k}+2\sum_{k=1}^nk(k-1)\binom{n}{k}\binom{n}{n-k}\tag{4}\\ &=n(n-1)(n-2)\sum_{k=1}^n\binom{n-3}{k-3}\binom{n}{n-k}+2n(n-1)\sum_{k=1}^n\binom{n-2}{k-2}\binom{n}{n-k}\tag{5}\\ &=n(n-1)(n-2)\binom{2n-3}{n-3}+2n(n-1)\binom{2n-2}{n-2}\tag{6}\\[4pt] &=(n-1)(n-2)^2\binom{2n-3}{n-2}+4(n-1)^2\binom{2n-2}{n}\tag{7}\\[4pt] &=n^2(n-1)\binom{2n-3}{n-2}\tag{8} \end{align} Explanation:
$(4)$: apply $(1)$ and $(3)$
$(5)$: apply $(2)$ several times
$(6)$: Vandermonde Identity
$(7)$: $\binom{2n-3}{n-3}\stackrel{(1)}=\binom{2n-3}{n}\stackrel{(2)}=\frac{2n-3}{n}\binom{2n-4}{n-1}\stackrel{(1)}=\frac{2n-3}{n}\binom{2n-4}{n-3}\stackrel{(2)}=\frac{n-2}{n}\binom{2n-3}{n-2}$
$(7)$: $\binom{2n-2}{n-2}\stackrel{(1)}=\binom{2n-2}{n}\stackrel{(2)}=\frac{2n-2}{n}\binom{2n-3}{n-1}\stackrel{(1)}=\frac{2n-2}{n}\binom{2n-3}{n-2}$

• I was trying to hide the solution, but the spoiler hiding feature fails here. – robjohn Apr 11 '14 at 14:54

There's a factor of $n-1$ missing from the right side of the equation. Let us write the equation as $$\sum_{k=1}^n k (k-1){\binom{n}{k}}\cdot k{\binom{n}{n-k}}=n^2(n-1)\binom{2n-3}{n-2}.$$ Now count the number of sequences of length $2n$ on the alphabet $\{a_0,a_1,a_2,b_0,b_1\}$ with $n$ $a$'s (with any subscript) and $n$ $b$'s (with any subscript) satisfying the following additional conditions. There is exactly one $a_1$, one $a_2$ and one $b_1$. Furthermore, $a_1$ and $a_2$ appear in the first half of the sequence and $b_1$ appears in the second half.

• That's correct. I missed that part. – Vitor Silva Apr 10 '14 at 22:24

$\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}}$ $\ds{\sum_{k = 1}^{n}k^{2}\pars{k - 1}{n \choose k}^{2} = n^{2}\pars{n - 1}{2n - 3 \choose n - 2}}$

\begin{align} &\mbox{Lets consider}\quad \fermi\pars{x} \equiv \sum_{k = 0}^{n}{n \choose k}^{2}x^{k} \\&\mbox{such that}\quad \sum_{k = 1}^{n}k^{2}\pars{k - 1}{n \choose k}^{2} =\left.\bracks{\pars{x\,\partiald{}{x}}^{3} - \pars{x\,\partiald{}{x}}^{2}}\fermi\pars{x} \right\vert_{x\ =\ 1}\tag{1} \end{align}

Hereafter we'll use the identity $$\color{#c00000}{% {m \choose n} = \int_{\verts{z} = 1}{\pars{1 + z}^{m} \over z^{n + 1}} \,{\dd z \over 2\pi\ic}\,,\qquad m, n \in {\mathbb N}\,,\quad m \geq n}\tag{2}$$

\begin{align} \fermi\pars{x}&=\sum_{k = 0}^{n}x^{k}{n \choose k} \int_{\verts{z} = 1}{\pars{1 + z}^{n} \over z^{k + 1}}\,{\dd z \over 2\pi\ic} =\int_{\verts{z} = 1}{\pars{1 + z}^{n} \over z} \sum_{k = 0}^{n}{n \choose k}\pars{x \over z}^{k}\,{\dd z \over 2\pi\ic} \\[3mm]&=\int_{\verts{z} = 1}{\pars{1 + z}^{n} \over z}\pars{1 + {x \over z}}^{n} \,{\dd z \over 2\pi\ic} =\int_{\verts{z} = 1}{\pars{1 + z}^{n} \over z^{n + 1}}\,\pars{x + z}^{n} \,{\dd z \over 2\pi\ic}\tag{3} \end{align}

With $\pars{1}$ and $\pars{3}$ we'll have: \begin{align} &\color{#00f}{\large\sum_{k = 1}^{n}k^{2}\pars{k - 1}{n \choose k}^{2}} \\[3mm]&=\int_{\verts{z} = 1}{\pars{1 + z}^{n} \over z^{n + 1}}\, n\pars{n - 1}\bracks{% \pars{n - 2}\pars{1 + z}^{n - 3} + 2\pars{1 + z}^{n - 2}}\,{\dd z \over 2\pi\ic} \\[3mm]&=n\pars{n -1}\pars{n - 2} \int_{\verts{z} = 1}{\pars{1 + z}^{2n - 3} \over z^{n + 1}}\,{\dd z \over 2\pi\ic} + 2n\pars{n -1} \int_{\verts{z} = 1}{\pars{1 + z}^{2n - 2} \over z^{n + 1}}\,{\dd z \over 2\pi\ic} \\[3mm]&=n\pars{n -1}\pars{n - 2}{2n - 3 \choose n} + 2n\pars{n -1}{2n - 2 \choose n} \\[3mm]&={\pars{2n - 3}! \over \pars{n - 3}!\pars{n - 3}!} + 2\,{\pars{2n - 2}! \over \pars{n - 2}!\pars{n - 2}!} \\[3mm]&={\pars{n - 1}\pars{n - 2}^{2} + 2\pars{n - 1}\pars{2n - 2} \over \pars{n - 2}!\pars{n - 1}!}\,\pars{2n - 3}! =\bracks{\pars{n - 2}^{2} + 4n - 4}\pars{n - 1} {2n - 3 \choose n - 2} \\[3mm]&=\color{#00f}{\large n^{2}\pars{n - 1}{2n - 3 \choose n - 2}} \end{align}