Prove $\sum\limits_{r=0}^{2n} r \binom{2n}{r}^2 = 2n \binom{4n-1}{2n}$

139 Views Asked by At

I expanded

$(1+x)^{2n}$ = $\sum\limits_{r=0}^{2n} \binom{2n}{r} x^r $

Differentiating both sides, we get

$2n(1+x)^{2n-1}$ = $0$ + $\binom{2n}{1}$ + $2\binom{2n}{2}x$ + $3\binom{2n}{3}x^2$ .....

Put $x=1$.

As you see, I'm not able to get the 'squares'.Any idea on how to go about it?

3

There are 3 best solutions below

2
On

Out of $4n$ people, $2n$ men and $2n$ women, select a committee of $2n$ people and choose a woman to be the chair of the committee. If $r$ women are chosen, there are $\binom{2n}{r} \binom{2n}{2n-r} = \binom{2n}{r}^2$ ways to choose the committee and $r$ ways to choose the chair, so the left hand side gives the number of ways to do so. Alternatively, first choose one of the $2n$ women as chair and then select the remaining members of the committee in $\binom{4n-1}{2n-1} = \binom{4n-1}{2n}$ ways.

0
On

$\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_{r = 0}^{2n}r{2n \choose r}^{2} = 2n{4n - 1 \choose 2n}:\ {\large ?}}$

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

\begin{align} \color{#00f}{\large\sum_{r = 0}^{2n}r{2n \choose r}^{2}}& =\sum_{r = 0}^{2n}r{2n \choose r} \int_{\verts{z} = 1}{\pars{1 + z}^{2n} \over z^{r + 1}}\,{\dd z \over 2\pi\ic} =\int_{\verts{z} = 1}{\pars{1 + z}^{2n} \over z} \sum_{r = 0}^{2n}{2n \choose r}{r \over z^{r}}\,{\dd z \over 2\pi\ic} \\[3mm]&=\int_{\verts{z} = 1}{\pars{1 + z}^{2n} \over z} \lim_{\mu \to 1/z}\bracks{\mu\,\partiald{}{\mu} \sum_{r = 0}^{2n}{2n \choose r}\mu^{r}}\,{\dd z \over 2\pi\ic} \\[3mm]&=\int_{\verts{z} = 1}{\pars{1 + z}^{2n} \over z} \lim_{\mu \to 1/z}\bracks{\mu\,\partiald{\pars{1 + \mu}^{2n}}{\mu}} \,{\dd z \over 2\pi\ic} \\[3mm]&=\int_{\verts{z} = 1}{\pars{1 + z}^{2n} \over z} \bracks{{1 \over z}\,2n\pars{1 + {1 \over z}}^{2n - 1}}\,{\dd z \over 2\pi\ic} =2n\int_{\verts{z} = 1}{\pars{1 + z}^{4n - 1} \over z^{2n + 1}} \,{\dd z \over 2\pi\ic} \\[3mm]&=\color{#00f}{\large 2n{4n - 1 \choose 2n}} \end{align}

2
On

$$ \begin{align} \sum_{r=0}^{2n}r\binom{2n}{r}^2 &=\sum_{r=1}^{2n}r\binom{2n}{r}\binom{2n}{2n-r}\tag{1}\\ &=\sum_{r=1}^{2n}2n\binom{2n-1}{r-1}\binom{2n}{2n-r}\tag{2}\\ &=2n\binom{4n-1}{2n-1}\tag{3}\\ &=2n\binom{4n-1}{2n}\tag{4} \end{align} $$ Explanation:
$(1)$: $\binom{n}{k}=\binom{n}{n-k}$
$(2)$: $k\binom{n\vphantom{1}}{k}=n\binom{n-1}{k-1}$
$(3)$: Vandermonde's Identity
$(4)$: $\binom{n}{k}=\binom{n}{n-k}$


Here is a proof of the Vandermonde Identity step using the binomial identity.

The binomial theorem says $$ \begin{align} (1+x)^{2n-1}(1+x)^{2n} &=\sum_{j=0}^{2n-1}\binom{2n-1}{j}x^j\sum_{k=0}^{2n}\binom{2n}{k}x^k\\ &=\sum_{s=0}^{4n-1}\color{#00A000}{\sum_{r=0}^s\binom{2n-1}{r}\binom{2n}{s-r}x^s} \end{align} $$ but it also says $$ (1+x)^{4n-1}=\sum_{s=0}^{4n-1}\color{#00A000}{\binom{4n-1}{s}x^s} $$ Equating the coefficients of $x^s$, we get $$ \sum_{r=0}^s\binom{2n-1}{r}\binom{2n}{s-r}=\binom{4n-1}{s} $$ Setting $s=2n-1$ and substituting $r\mapsto r-1$ gives $$ \sum_{r=1}^{2n}\binom{2n-1}{r-1}\binom{2n}{2n-r}=\binom{4n-1}{2n-1} $$