Summation of binomial with factor squared $\sum_{k=0}^n k^2 \binom nk^2 = n^2 {2n-2 \choose n-1}$

Question

How to prove that $$ \sum_{k=0}^n k^2 {n \choose k}^2 = n^2 {2n-2 \choose n-1} $$ in combinatorial way?

Answer 1

Note that $$ k {n \choose k}=n{n-1\choose k-1} $$ Hence $$ \sum_{k=0}^n k^2 {n \choose k}^2=n^2\sum_{k=1}^n {n-1 \choose k-1}^2=n^2\sum_{k=0}^{n-1} {n-1 \choose k}^2=n^2\sum_{k=0}^{n-1} {n-1 \choose k}{n-1 \choose n-k-1}=n^2 {2n-2 \choose n-1} $$ The last step is obtained by comparing the term in $x^{n-1}$ in expansion of $$ (1+x)^{n-1}(1+x)^{n-1}=(1+x)^{2n-2} $$

Answer 2

$\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}$ $$\bbox[10px,#efe,border:0.1em groove navy]{\mbox{This is an 'algebraic proof' which can still be useful besides the 'combinatorical way'.}}$$

Hereafter, I'll use the identities $$\left\{\begin{array}{rcl} \ds{m \choose n} & \ds{=} & \ds{\oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{m} \over z^{n + 1}} \,{\dd z \over 2\pi\ic}\,,\qquad n \in \mathbb{Z}}. \\[3mm] \ds{\sum_{k = 0}^{n}{n \choose k}k^{2}z^{k}} & \ds{=} & \ds{\pars{z\,\partiald{}{z}}^{2}\sum_{k = 0}^{n}{n \choose k}z^{k} = \pars{z\,\partiald{}{z}}^{2}\pars{1 + z}^{n} = \pars{n^{2}z^{2} + nz}\pars{1 + z}^{n - 2}} \end{array}\right. $$

\begin{align} \color{#f00}{\sum_{k = 0}^{n}k^{2}{n \choose k}^{2}} & = \sum_{k = 0}^{n}k^{2}{n \choose k}{n \choose n - k} = \sum_{k = 0}^{n}k^{2}{n \choose k} \oint_{\verts{z}\ =\ 1^{-}}\!\!\!{\pars{1 + z}^{n} \over z^{n - k + 1}} \,{\dd z \over 2\pi\ic} \\[5mm] & = \oint_{\verts{z}\ =\ 1^{-}}\!\!\!{\pars{1 + z}^{n} \over z^{n + 1}} \sum_{k = 0}^{n}{n \choose k}k^{2}z^{k}\,{\dd z \over 2\pi\ic} \\[5mm] & = \oint_{\verts{z}\ =\ 1^{-}}\!\!\!{\pars{1 + z}^{n} \over z^{n + 1}} \bracks{\pars{n^{2}z^{2} + nz}\pars{1 + z}^{n - 2}}\,{\dd z \over 2\pi\ic} \\[5mm] & = n^{2}\oint_{\verts{z}\ =\ 1^{-}}\!\!\!{\pars{1 + z}^{2n - 2} \over z^{n - 1}} \,{\dd z \over 2\pi\ic} + n\oint_{\verts{z}\ =\ 1^{-}}\!\!\!{\pars{1 + z}^{2n - 2} \over z^{n}} \,{\dd z \over 2\pi\ic} \\[5mm] & = n^{2}{2n - 2 \choose n - 2} + n{2n - 2 \choose n - 1} = n^{2}{\pars{2n - 2}! \over \pars{n - 2}!n!} + n{2n - 2 \choose n - 1} \\[5mm] & = n^{2}\,{n - 1 \over n}{\pars{2n - 2}! \over \pars{n - 1}!\pars{n - 1}!} + n{2n - 2 \choose n - 1} = \pars{n^{2} - n}{2n - 2 \choose n - 1} + n{2n - 2 \choose n - 1} \\[5mm] & = \color{#f00}{n^{2}{2n - 2 \choose n - 1}} \end{align}

Answer 3

I really like the proof provided by @hermes, but in case you wanted a pure combinatorial proof, here's a candidate based on hermes's analysis. Let $S_n=\{1 \ldots n\}$ and define $Z$ to be the set of ordered quadruplets $(a,b,A,B)$, where $a,b \in S_n$ and $A,B \subseteq S_n$ satisfying $a \in A$, $b \in B$ and $|A| = |B|$.

For any $k \in \{0 \ldots n\}$, there are exactly $k^2 {{n} \choose{k}}$ such quadruplets such that $|A| = |B| = k$; $n\choose k$ choices for each of $A$ and $B$, and then $k$ choices for each of $a$ and $b$. Thus $|Z| = \displaystyle \sum_{k=0}^n k^2 {{n} \choose{k}}$.

To count in another way, first pick $a$ and $b$, which can be done in $n^2$ ways. To pick $A$ and $B$, consider the set of pairs $P=\{(x,y):x \in S_n, y \in \{0,1\}\} \setminus \{(a,0),(b,1)\}$; clearly $|P| = 2n-2$. Let $Q$ be any subset of $P$ of size $n-1$, for which there are ${2n-2} \choose {n-1}$ possibilities. Letting $A = \{a\} \cup \{x:x \in S|(x,0) \in Q\}$ and $B = \{x:x \in S|(x,1) \notin Q\}$, we claim $(a,b,A,B) \in Z$. Clearly $a \in A$ and $b \in B$ since $(b,1) \notin P$, and we have $$|A| = k \Leftrightarrow \\ |\{x:x \in S|(x,0) \in Q\}| = k-1 \Leftrightarrow \\ |\{x:x \in S|(x,1) \in Q\}| = n-k \Leftrightarrow \\ |\{x:x \in S|(x,1) \notin Q\}| = |B| = k$$ It is clear that any selection of $Q$ yields different choices for $A$ and $B$, so we know there are at least ${2n-2} \choose {n-1}$ possibilities for $A$ and $B$. But it is not hard to see that for any quadruplet $(a,b,A,B) \in Z$, one can reverse this process to create $Q \subset P$ of size $n-1$.

Answer 4

Here is a purely combinatorial proof, one that uses no algebraic preliminaries.

You have a pool of $n$ men and $n$ women. You want to form two committees, one of women and one of men, and appoint a chair of each committee; the one restriction is that the two committees must be the same size. In how many different ways can you do this?

On the one hand you could first decide on the size of the committees. Suppose that you decide on a size of $k$; there are $\binom{n}k$ ways to choose the $k$ women and $\binom{n}k$ ways to choose the $k$ men. Once you’ve chosen the $k$ members of each committee, there are $k$ ways to choose the chair of the women’s committee and $k$ ways to choose the chair of the men’s committee. Thus, there are altogether $k^2\binom{n}k^2$ ways to choose committees of size $k$ and pick their chairs, and summing over $k$ gives the desired total: it’s

$$\sum_{k=0}^nk^2\binom{n}k^2\;.$$

Alternatively, you could begin by selecting the two chairs; this can evidently be done in $n^2$ ways. Now comes the one slightly tricky bit. Suppose that I choose $n-1$ of the $2n-2$ people remaining after the chairs have been selected and find that I have $k$ women in my selection, something that I can do in $\binom{2n-2}{n-1}$ differet ways. Then I must have $n-1-k$ men in my selection, so there must be $(n-1)-(n-1-k)=k$ men whom I have not selected. The $k$ selected women and the $k$ unselected men will be the non-chair members of the committees. I really can get every possible pair of equal-sized committees in this way, so there are

$$n^2\binom{2n-2}{n-1}$$

ways to carry out the task, and it follows that

$$\sum_{k=0}^nk^2\binom{n}k^2=n^2\binom{2n-2}{n-1}\;.$$

An easier combinatorial argument can be given if we first apply the same initial manipulation that User1006 used:

$$\sum_{k=0}^nk^2\binom{n}k^2=\sum_{k=0}^nn^2\binom{n-1}{k-1}^2=n^2\sum_{k=0}^n\binom{n-1}{k-1}^2=n^2\sum_{k=0}^{n-1}\binom{n-1}k^2\;.$$

$$\sum_{k=0}^{n-1}\binom{n-1}k^2=\binom{2n-2}{n-1}\;,$$

and we might as well simplify the notation by proving instead that

$$\sum_{k=0}^n\binom{n}k^2=\binom{2n}n\;.$$

Finally, we can rewrite the lefthand side to make this

$$\sum_{k=0}^n\binom{n}k\binom{n}{n-k}=\binom{2n}n\;.$$

Then we make the simple combinatorial argument that both sides are the number of ways to pick a committee of $n$ people from a pool consisting of $n$ men and $n$ women; the lefthand side simply breaks up the count according to the number $k$ of women on the committee.

Answer 5

We have $$(1+x)^n = \sum_{k=0}^n \binom{n}{k}x^k $$ Differentiating with respect to $x$, we get $$n(1+x)^{n-1} = \sum_{k=0}^n k \binom{n}{k}x^{k-1}$$ and hence $$n\left(1+\frac{1}{x}\right)^{n-1} = \sum_{k=0}^{n}k\binom{n}{k}\frac{1}{x^k} $$ The given expression is the constant term in $$n^2(1+x)^{n-1}\left(1+\frac{1}{x}\right)^{n-1} $$ and hence in $$n^2\frac{(1+x)^{2n-2}}{x^{n-1}}$$ and equals $$n^2\binom{2n-2}{n-1}$$