5
$\begingroup$

$\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}$ ?

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

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}$

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

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.

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

$\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}

$\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.