Combinatorial coefficients squared If $C_0,C_1,C_2,...,C_n$ are the combinatorial coefficients in the expansion of $(1+x)^n$ then prove that:
$$1C_0^2+3C_1^2+5C_3^2+...+(2n+1)C_n^2=\dfrac{(n+1)(2n)!}{n!n!}=(n+1)\binom {2n}n$$
I am able to compute the linear addition but not the squares of coefficients.
Thanks!
 A: $$\sum_{k=0}^{n}(2k+1)\binom{n}{k}^2=\sum_{k=0}^{n}(2k+1)\binom{n}{k}\binom{n}{n-k}=[x^k]\left[(1+x)^n\sum_{k=0}^{n}\binom{n}{k}(2k+1)x^k\right] $$
but by setting $x=z^2$ we have:
$$\sum_{k=0}^{n}\binom{n}{k}(2k+1)x^k=\frac{d}{dz}\sum_{k=0}^{n}\binom{n}{k}z^{2k+1}=(1+x)^{n-1}(1+(2n+1)x)$$
hence:
$$\sum_{k=0}^{n}(2k+1)\binom{n}{k}^2= [x^n]\left[(1+x)^{2n}+2nx(1+x)^{2n-1}\right]=\binom{2n}{n}+2n\binom{2n-1}{n}$$
and simplifying:
$$\sum_{k=0}^{n}(2k+1)\binom{n}{k}^2=(n+1)\binom{2n}{n} $$
as wanted.
A: $$\begin{align*}
\sum_{k=0}^n(2k+1)\binom{n}k^2&=2\sum_{k=0}^nk\binom{n}k\binom{n}{n-k}+\sum_{k=0}^n\binom{n}k\binom{n}{n-k}\\
&\overset{(1)}=2n\sum_{k=0}^n\binom{n-1}{k-1}\binom{n}{n-k}+\binom{2n}n\\
&=2n\sum_{k=0}^n\binom{n-1}{k-1}\binom{n}{n-k}+\binom{2n}n\\
&\overset{(2)}=2n\binom{2n-1}{n-1}+\binom{2n}n\\
&\overset{(3)}=n\binom{2n}n+\binom{2n}n\\
&=(n+1)\binom{2n}n
\end{align*}$$
$(1)$ uses the identity $k\binom{n}k=n\binom{n-1}{k-1}$ and Vandermonde’s identity; $(2)$ is another application of Vandermonde’s identity, and $(3)$ is another application of $k\binom{n}k=n\binom{n-1}{k-1}$.
A: $\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}$
\begin{align}
\sum_{k = 0}^{n}\pars{2k + 1}{n \choose k}^{2} & =
{1 \over 2}\sum_{k = 0}^{n}\braces{\pars{2k + 1}{n \choose k}^{2} +
\bracks{2\pars{n - k} + 1}{n \choose n - k}^{2}}
\\[5mm] & =
\pars{n + 1}\sum_{k = 0}^{n}{n \choose k}^{2} =
\bbx{\ds{\pars{n + 1}{2n \choose n}}}
\end{align}

$\ds{\sum_{k = 0}^{n}{n \choose k}^{2} = {2n \choose n}}$ is a  well known identity. Note that
  $\ds{\left\lbrace
\begin{array}{rcl}
\ds{n \choose k} & \ds{=} & \ds{n \choose n - k}
\\[2mm]
\ds{\sum_{k = 0}^{n}a_{k}} & \ds{=} & \ds{\sum_{k = 0}^{n}a_{n - k}}
\end{array}\right.}$

A: Note that 
$C_r=\binom nr$. 
It is a well-known result that $\sum_{r=0}^n\binom nr^2=\binom {2n}n$ which can be proven easily using the Vandermonde identity. 
For even $n$:
The number elements is odd, index from $0$ to $(\frac n2-1)$, $n$, and from $(\frac n2+1)$ to $n$
Since $\binom nr=\binom n{n-r}$, then $\sum_{r=0}^{\frac n2-1}\binom nr^2=\frac 12 \binom {2n}n$.
The summation in the question can then be written as
$$\begin{aligned}
&\begin{array}r
1\binom n0^2
&+3\binom n1 ^2
&+\cdots
&+(n-1)\binom n{\frac n2-1}^2\\
& & & & +(n+1) \binom n{\frac n2} ^2\\
+(2n+1)\binom nn^2
&+(2n-1)\binom n{n-1}^2
&+\cdots
&+(n+3)\binom n{\frac n2+1}^2
\\
=(2n+2)\binom n0^2
&+(2n+2)\binom n1^2
&+\cdots
&+(2n+2)\binom n{\frac n2-1}^2
&+(n+1)\binom n{\frac n2}^2
\\
\end{array}\\
&=(2n+2)\cdot \displaystyle\sum_{r=0}^{\frac n2-1}\binom nr^2+(n+1)\binom n{\frac n2}\\
&=(2n+2)\cdot \frac 12 \left[\displaystyle\sum_{r=0}^{n}\binom nr^2-\binom n{\frac n2}\right]+(n+1)\binom n{\frac n2}\\
&=(n+1)\left[\binom {2n}n-\binom n{\frac n2}\right]+(n+1)\binom n{\frac n2}\\
&=\color{red}{(n+1)\binom {2n}n}
\end{aligned}$$
__
For odd $n$:
The number elements is even, index from $0$ to $\frac {n-1}2$, and from $\frac {n+1}2$ to $n$
Since $\binom nr=\binom n{n-r}$, then $\sum_{r=0}^\frac {n-1}2 \binom nr^2=\frac 12 \binom {2n}n$.
The summation in the question can then be written as
$$\begin{aligned}
&\begin{array}r
1\binom n0^2
&+3\binom n1 ^2
&+\cdots
&+n\binom n{\frac {n-1}2}^2\\
+(2n+1)\binom nn^2
&+(2n-1)\binom n{n-1}^2
&+\cdots
&+(n+2)\binom n{\frac {n+1}2}^2
\\
=(2n+2)\binom n0^2
&+(2n+2)\binom n1^2
&+\cdots
&+(2n+2)\binom n{\frac{n-1}2}^2\\
\end{array}\\
&=(2n+2)\displaystyle\sum_{r=0}^{\frac {n-1}2}\binom nr^2\\
&=(2n+2)\cdot \frac 12\displaystyle\sum_{r=0}^{n}\binom nr^2\\
&=(2n+2)\cdot \frac 12 \binom {2n}n\\
&=\color{red}{(n+1)\binom {2n}n}
\end{aligned}$$
