Looking for a combinatorial proof for a Catalan identity

Question

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}.$$

Answer 1

By 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$.

Answer 2

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.)

Answer 3

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}.$$

Answer 4

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}$$

Answer 5

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}. $$