13
$\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$

5 Answers 5

38
$\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$ Feb 6, 2021 at 22:17
13
$\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$ Feb 9, 2021 at 15:01
12
$\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$ Feb 6, 2021 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$ Feb 7, 2021 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, 2021 at 4:01
  • $\begingroup$ @AlexanderBurstein: it'd be nice for the record and clarity to give it as an answer. $\endgroup$ Feb 7, 2021 at 14:24
  • $\begingroup$ @AlapanDas:it'd be nice for the record and clarity to give it as an answer. $\endgroup$ Feb 7, 2021 at 14:24
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$ Feb 9, 2021 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$ Feb 9, 2021 at 15:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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