Prove that $\sum_{k=1}^nk^2{n\choose k}^2=n^2 \binom {2n-2}{n-1}$

Question

Please help me / give a hand with combinational prove for: $$ 1^2 \binom n 1 ^2 + 2^2 \binom n 2 ^2 + \dots + n^2 \binom n n ^2 = n^2 \binom {2n-2}{n-1}$$

Answer 1

We have: $$\sum_{k=1}^{n}k\binom{n}{k}z^k = nz(1+z)^{n-1}\tag{1}$$ hence, replacing $z$ with $e^{\pm i\theta}$ and using the Parseval identity: $$\begin{eqnarray*}\sum_{k=1}^{n}k^2\binom{n}{k}^2&=&\frac{n^2}{2\pi}\int_{0}^{2\pi}(1+e^{i\theta})^{n-1}(1+e^{-i\theta})^{n-1}\,d\theta\\&=&\frac{n^2}{2\pi}\int_{0}^{2\pi}(2+2\cos\theta)^{n-1}d\theta\\&=&\frac{n^2 4^{n}}{2\pi}\int_{0}^{\pi/2}\cos^{2n-2}(\theta)\,d\theta\\&=&n^2\binom{2n-2}{n-1}.\end{eqnarray*}$$

Answer 2

The left hand side can be simplified as follows $$\sum_{m=1}^nm^2{n \choose m}^2=\sum_{m=1}^nm^2\frac{(n!)^2}{(m!)^2((n-m)!)^2}\\=\sum_{m=1}^n\frac{n^2((n-1)!)^2}{((m-1)!)^2((n-m)!)^2}\\=n^2\left(\sum_{m=1}^{n}{n-1 \choose m-1}^2\right)\\=n^2\color{blue}{\left(\sum_{k=0}^{n-1}{n-1 \choose k}^2\right)}\\=n^2\color{blue}{{2n-2 \choose n-1}}$$ for the parts highlighted in blue we use the combinatorial identity from here, (Equation $9$) $$\sum_{k=0}^n{n \choose k}^2={2n \choose n}$$ which is derived from the Chu-Vandermode identity - this identity can be proved using a combinatorial argument, as shown here.

Answer 3

Let $A=\{1,\dots,n\}$ and $B=\{n+1,\dots,2n\}$. LHS counts number of ways to chose two subsets of equal cardinality in $A$ and $B$ and then to choose a pair of elements - one from the subset of $A$ and other from the subset of $B$. This procedure counts all pairs from $A\times B$ with some multiplicity. Let's calculate it. Pair $(a,b)$ can be obtained from two subsets of cardinality $k$, which can be chosen $\binom{n-1}{k}^2$ ways, so this multiplicity is equal to $\binom{n-1}{0}^2+\dots+\binom{n-1}{n-1}^2$. It's well-known that this sum is equal to $\binom{2n-2}{n-1}$. Since $|A\times B|=n^2$, LHS=RHS.

Answer 4

By way of enrichment here is another solution using basic complex variables.

Start by restating the problem using the alternate binomial coefficient: we seek to show that $$\sum_{k=0}^n {n\choose k} k^2 {n\choose n-k} = n^2 {2n-2\choose n-1}.$$

Introduce the integral representation $${n\choose n-k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n-k+1}} \; dz.$$

This gives the following integral for the sum: $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z^{n+1}} \sum_{k=0}^n {n\choose k} k^2 z^k \; dz.$$

Now recall that $$(1+z)^n = \sum_{k=0}^n {n\choose k} z^k$$ and hence $$nz (1+z)^{n-1} = \sum_{k=0}^n {n\choose k} k z^k$$ and finally $$z(n (1+z)^{n-1} + nz(n-1)(1+z)^{n-2}) = \sum_{k=0}^n {n\choose k} k^2 z^k.$$

Substituting this into the sum gives $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \left(n \frac{(1+z)^{2n-1}}{z^n} + n(n-1) \frac{(1+z)^{2n-2}}{z^{n-1}} \right)\; dz.$$

Extracting coefficients we finally obtain $$n {2n-1\choose n-1} + n(n-1) {2n-2\choose n-2} \\= n \frac{2n-1}{n} {2n-2\choose n-1} + n(n-1) \frac{n-1}{n} {2n-2\choose n-1} \\ = (2n-1 + (n-1)^2) {2n-2\choose n-1} = n^2 {2n-2\choose n-1}.$$

Apparently this method is due to Egorychev. A trace as to when it appeared on MSE and by whom starts at this MSE link.