Let $C_n=\frac1{n+1}\binom{2n}n$ be the familiar Catalan numbers.
QUESTION. Is there a combinatorial or conceptual justification for this identity? $$\sum_{k=1}^n\left[\frac{k}n\binom{2n}{n-k}\right]^2=C_{2n-1}.$$
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityBy the ballot theorem, $\frac{k}{n} \binom{2n}{n+k}$ is the number of Dyck paths, i.e. $(1,1), (1,-1)$-walks in the quadrant, from the origin to $(2n-1, 2k-1)$. You need to concatenate a pair of those to get a Dyck path to $(4n-2,0)$, and $k$ takes values between 1 and $n$.
Not sure if this is what you look for, but still:
$$\sum_{k=1}^n\left[\frac{k}n\binom{2n}{n-k}\right]^2= \sum_{k=1}^n \big[1-\frac{(n+k)(n-k)}{n^2}\big]\binom{2n}{n+k}\binom{2n}{n-k}$$ $$=\sum_{k=1}^n \binom{2n}{n+k}\binom{2n}{n-k} - 4\sum_{k=1}^{n-1} \binom{2n-1}{n+k-1}\binom{2n-1}{n-k-1}$$ $$=\frac{1}{2}\left[\binom{4n}{2n}-\binom{2n}n^2\right] - 2\left[\binom{4n-2}{2n-2}-\binom{2n-1}{n-1}^2\right]$$ $$=C_{2n-1}.$$
More generally, $$\sum_{k\ge1} \frac{k}{m}\binom{2m}{m-k}\cdot\frac{k}{n} \binom{2n}{n-k} = C_{m+n-1}.$$ This can be proved by the same reasoning as in Timothy Budd's answer.
This formula gives the LDU (or in this case, LU) factorization of the Hankel matrix for Catalan numbers $(C_{m+n-1})_{m,n\ge1}$. There is a similar formula for the Hankel matrix $(C_{m+n-2})_{m,n\ge1}$, involving the remaining ballot numbers. More generally, there are explicit formulas for LDU factorizations of Hankel matrices of moments of other orthogonal polynomials. (The Catalan numbers are moments of Chebyshev polynomials.)
Let, $$\sum_{k=1}^{n} (\frac{k}{n}\binom{2n}{n-k})^2 =A_{n}$$
Now, using the fact that $(n+k)^2+(n-k)^2=2(n^2+k^2)$ and $\binom{2n}{n-k}=\binom{2n}{n+k}$, we get the following
$$\frac{1}{n^2}(\sum_{a=0}^{2n} a^2\binom{2n}{a}^2 -n^2\binom{2n}{n}^2)=\frac{1}{n^2}[\sum_{k=1}^n (n-k)^2\binom{2n}{n-k}^2+(n+k)^2\binom{2n}{n+k}^2]=(\sum_{k=0}^{2n} \binom{2n}{k}^2- \binom{2n}{n}^2)+2A_{n}$$ $\cdots (1)$
Now, $$\frac{1}{n^2}(\sum_{a=0}^{2n} a^2\binom{2n}{a}^2-n^2\binom{2n}{n}^2)=4\binom{4n-2}{2n-1}-\binom{2n}{n}^2$$
and $$(\sum_{k=0}^{2n} \binom{2n}{k}^2- \binom{2n}{n}^2)=\binom{4n}{2n}-\binom{2n}{n}^2$$
Hence,$$A_{n}=2\binom{4n-2}{2n-1}-\frac{4n-1}{2n}\binom{4n-2}{2n-1}$$...from equation (1)
$$=\frac{1}{2n}\binom{4n-2}{2n-1}=C_{2n-1}$$
Expanding my previous comment into an answer at the OP's request. We can write $$ \frac{k}{n}\binom{2n}{n-k}=A_k-B_k, $$ where $$ A_k=\binom{2n-1}{n-k}=\binom{2n-1}{n+k-1}, \qquad B_k=\binom{2n-1}{n+k}=\binom{2n-1}{n-k-1}. $$ Then $$ \sum_{k=1}^{n}\left(\frac{k}{n}\binom{2n}{n-k}\right)^2=\sum_{k=1}^{n}(A_k^2+B_k^2)-\sum_{k=1}^{n}(A_kB_k+B_kA_k). $$ The first sum on the right is $$ \sum_{k=1}^{n}\left(\binom{2n-1}{n-k}\binom{2n-1}{n+k-1}+\binom{2n-1}{n+k}\binom{2n-1}{n-k-1}\right)=\\ =\left(\sum_{k=0}^{2n-1}\binom{2n-1}{k}\binom{2n-1}{2n-1-k}\right)-\binom{2n-1}{n}\binom{2n-1}{n-1}=\binom{4n-2}{2n-1}-\binom{2n-1}{n}^2, $$ and the second sum on the right is $$ \sum_{k=1}^{n}\left(\binom{2n-1}{n-k}\binom{2n-1}{n+k}+\binom{2n-1}{n+k}\binom{2n-1}{n-k}\right)=\\ =\left(\sum_{k=0}^{2n-1}\binom{2n-1}{k}\binom{2n-1}{2n-k}\right)-\binom{2n-1}{n}^2=\binom{4n-2}{2n}-\binom{2n-1}{n}^2, $$ so $$ \sum_{k=1}^{n}\left(\frac{k}{n}\binom{2n}{n-k}\right)^2=\binom{4n-2}{2n-1}-\binom{4n-2}{2n}=C_{2n-1}. $$