I have this identity that I'd like to prove. $\sum_{k=0}^{n}\left(\frac{n-2k}{n}\binom{n}{k}\right)^2=\frac{2}{n}\binom{2n-2}{n-1}$

Question

I have this identity that I'd like to prove. $$\displaystyle{\sum_{k=0}^{n}\bigg(\dfrac{n-2k}{n}\binom{n}{k}}\bigg)^2=\dfrac{2}{n}\binom{2n-2}{n-1}$$

Here's what I have done so far: (using a binomial indentity)

$$=\displaystyle{\sum_{k=0}^{n}\bigg({\binom{n}{k}-2\binom{n-1}{k-1}}\bigg)^2}$$ $$=\displaystyle{\sum_{k=0}^{n}\bigg({\binom{n-1}{k}-\binom{n-1}{k-1}}\bigg)^2}$$ $$=\displaystyle{\sum_{k=0}^{n}\bigg({\binom{n-1}{k}-\binom{n-1}{k-1}}\bigg)^2}$$

At this point I expanded the square, Here's where I made a mistake

$$=\displaystyle{{\sum_{k=0}^{n}\binom{n-1}{k}^2+\sum_{k=0}^{n}\binom{n-1}{k-1}}^2-\sum_{i=0}^{n}\sum_{j=0}^{n}}\binom{n-1}{j-1}\binom{n-1}{i}$$

$$=\displaystyle{{\sum_{k=0}^{n}\binom{n-1}{k}^2+\sum_{k=0}^{n}\binom{n-1}{k-1}}^2-\sum_{i=0}^{n}\sum_{j=0}^{n}}\binom{n-1}{j-1}\binom{n-1}{i}$$

$$=\displaystyle{2\binom{2n-2}{n-1}-\sum_{i=0}^{n}\sum_{j=0}^{n}}\binom{n-1}{j-1}\binom{n-1}{i}$$

because I can separate the sums $$=\displaystyle{2\binom{2n-2}{n-1}-2^{2n-2}}$$

Clearly, at some point here I made a stupid mistake. I was hoping someone will point the error to me and perhaps give me a hint. I prefer hints to complete solutions. Thank you for your time.

Answer 1

After expanding the square, the summation index should be the same for the last summation, making it a single summation over $i,$ not a double summation with $i,j.$ You then have a sum which can be evaluated with Vandermonde's identity.

Answer 2

I would have followed a slightly different approach, let us see if it is really faster.
Clearly we have $\sum_{k=0}^{n}\binom{n}{k}^2=\binom{2n}{n}$ by Vandermonde's identity, and similarly

$$ \sum_{k=0}^{n}k(n-k)\binom{n}{k}^2=[x^n]\left(\sum_{k=0}^{n}k\binom{n}{k}x^k\right)^2=[x^n]\left( n^2 x^2 (1+x)^{2n-2}\right)=n^2\binom{2n-2}{n-2}. $$

Since $(n-2k)^2 = n^2-4k(n-k)$ it follows that

$$ \sum_{k=0}^{n}(n-2k)^2\binom{n}{k}^2 = n^2\binom{2n}{n}-4n^2\binom{2n-2}{n-2} $$ and it just remains to perform some simplification. Yeah, it looks faster.

Answer 3

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \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}$ $\ds{\color{#44f}{\sum_{k = 0}^{n}\bracks{\pars{n - 2k \over n} {n \choose k}}^{2} = {2 \over n}{2n - 2 \choose n - 1}}:\ {\large ?}}$

---

\begin{align} &\sum_{k = 0}^{n}\bracks{\pars{n - 2k \over n} {n \choose k}}^{2} = \sum_{k = 0}^{n}\pars{n - 2k \over n}^{2} {n \choose k}\ \overbrace{\bracks{z^{n - k}}\pars{1 + z}^{n}} ^{\ds{{n \choose n - k} = {n \choose k}}} \\[3mm] = & \bracks{z^{n}}\pars{1 + z}^{n}\sum_{k = 0}^{n} {n \choose k}\pars{1 - {4k \over n} + {4k^{2} \over n^{2}}}z^{k} \\ = & \bracks{z^{n}}\pars{1 + z}^{n} \bracks{1 - {4 \over n}\pars{z\,\partiald{}{z}} + {4 \over n^{2}} \pars{z\,\partiald{}{z}}^{2}}\ \overbrace{\sum_{k = 0}^{n}{n \choose k}z^{k}} ^{\ds{\pars{1 + z}^{n}}} \\[3mm] = & \bracks{z^{n}}\pars{1 + z}^{n} \braces{\pars{1 + z}^{n} - 4z\pars{1 + z}^{n - 1} + {4 \over n}\bracks{z\pars{1 + z}^{n - 1} + \pars{n - 1}z^{2}\pars{1 + z}^{n - 2}}} \\[3mm] = & \bracks{z^{n}}\pars{1 + z}^{2n} - 4\,{n - 1 \over n}\bracks{z^{n - 1}}\pars{1 + z}^{2n - 1} + 4\,{n - 1 \over n}\bracks{z^{n - 2}}\pars{1 + z}^{2n - 2} \\[3mm] = & {2n \choose n} - 4\,{n - 1 \over n}{2n - 1 \choose n - 1} + 4\,{n - 1 \over n}{2n - 2 \choose n - 2} \\[3mm] = & {2n\pars{2n - 1}\pars{2n - 2}! \over n!\, n!} - 4\,{n - 1 \over n}{\pars{2n - 1}\pars{2n - 2}! \over \pars{n - 1}!\, n!} + 4\,{n - 1 \over n}{\pars{2n - 2}! \over \pars{n - 2}!\, n!} \\[3mm] = & \underbrace{\bracks{{2\pars{2n - 1} \over n} - {4\pars{n - 1}\pars{2n - 1} \over n^{2}} + {4\pars{n - 1}^{2} \over n^{2}}}}_{\ds{2 \over n}}\ \underbrace{\pars{2n - 2}! \over \pars{n - 1}!\pars{n - 1}!} _{\ds{2n - 2 \choose n - 1}} \\[3mm] = & \bbx{\color{red}{{2 \over n}{2n - 2 \choose n - 1}}} \end{align}