Prove $\sum\limits_{k=0}^n \frac{(C_n^k)^2}{k+1} = \frac{(2(n+1))!}{2(n+1)^3(n!)^2}$

Question

Wolfram says that $$ \sum\limits_{k=0}^n \frac{(C_n^k)^2}{k+1} = \frac{(2(n+1))!}{2(n+1)^3(n!)^2}, $$ but I don't know how to prove it.

Answer 1

Here's a combinatorial proof. First rewrite as $$\sum_{k=0}^n \frac{1}{k+1}\binom{n}{k}^2 = \frac{1}{n+1}\binom{2n+1}{n+1}$$ Now multiply both sides by $n+1$: $$\sum_{k=0}^n \frac{n+1}{k+1}\binom{n}{k}^2 = \binom{2n+1}{n+1}$$ Now apply absorption: $$\sum_{k=0}^n \binom{n+1}{k+1}\binom{n}{k} = \binom{2n+1}{n+1}$$ Now apply symmetry: $$\sum_{k=0}^n \binom{n+1}{n-k}\binom{n}{k} = \binom{2n+1}{n} \tag1\label1$$ To prove \eqref{1} combinatorially, count the $n$-subsets of $\{1,\dots,2n+1\}$ by conditioning on the number $k$ of elements from $\{1,\dots,n\}$. The remaining $n-k$ elements come from the $(n+1)$-set $\{n+1,\dots,2n+1\}$. This is a special case of Vandermonde's Identity.

Answer 2

We need to prove

$$ \sum\limits_{k=0}^n \frac{(C_n^k)^2}{k+1} = \frac{(2(n+1))!}{2(n+1)^3(n!)^2}. $$

Note that the RHS is $\frac{1}{n+1} \binom{2n+1}{n+1}$, and you can rewrite LHS using $\binom{n}{k} = [x^n] x^k (1+x)^n$ as $$\begin{align} \sum\limits_k \frac{1}{k+1} \binom{n}{k}^2 &= [x^n](1+x)^n\sum\limits_k \binom{n}{k} \frac{x^{k}}{k+1} \\ &= [x^{n+1}] (1+x)^n \sum\limits_k \binom{n}{k} \frac{x^{k+1}}{k+1} \\ &= [x^{n+1}] (1+x)^n \int (1+x)^n dx \\ &= [x^{n+1}] (1+x)^n \frac{(1+x)^{n+1}}{n+1} \\ &= \frac{1}{n+1} \binom{2n+1}{n+1}. \square \end{align}$$