12
$\begingroup$

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

$\endgroup$
37
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ This is cute. Thanks. $\endgroup$ – T. Amdeberhan Feb 6 at 22:17
11
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Although not combinatorial, still it is enjoyable to see it. $\endgroup$ – T. Amdeberhan Feb 6 at 22:17
  • 3
    $\begingroup$ As a slight variation of this proof, we can write $\frac{k}{n}\binom{2n}{n-k}=A-B$, where $A=\binom{2n-1}{n-k}=\binom{2n-1}{n+k-1}$ and $A=\binom{2n-1}{n+k}=\binom{2n-1}{n-k-1}$, then expand $(A-B)^2=A^2-2BA+B^2$ so as to have $k$ cancel out in the lower arguments of each pair of the binomial factors, then sum over $k$ to get $\binom{4n-2}{2n-1}-\binom{4n-2}{2n}=C_{2n-1}$. $\endgroup$ – Alexander Burstein Feb 7 at 2:31
  • 2
    $\begingroup$ Also, we can use $(n+k)^2+(n-k)^2=2(n^2+k^2)$ to prove the identity. $\endgroup$ – Alapan Das Feb 7 at 4:01
  • $\begingroup$ @AlexanderBurstein: it'd be nice for the record and clarity to give it as an answer. $\endgroup$ – T. Amdeberhan Feb 7 at 14:24
  • $\begingroup$ @AlapanDas:it'd be nice for the record and clarity to give it as an answer. $\endgroup$ – T. Amdeberhan Feb 7 at 14:24
11
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Great. Thank you. $\endgroup$ – T. Amdeberhan Feb 9 at 15:01
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you for the details. $\endgroup$ – T. Amdeberhan Feb 9 at 15:02
3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you for the details. $\endgroup$ – T. Amdeberhan Feb 9 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.