# Identities involving sums of Catalan numbers

The $n$-th Catalan number is defined as $C_n:=\frac{1}{n+1}\binom{2n}{n}=\frac{1}{n}\binom{2n}{n+1}$.

I have found the following two identities involving Catalan numbers, and my question is if anybody knows them, or if they are special cases of more general results (references?):

(1) For any $n\geq 1$ we have $$\binom{2n}{n} + \binom{2n}{n-1} = \sum_{i=0}^{n-1} (4i+3)C_i C_{n-i-1} \enspace. \quad (1)$$

(2) For any $n\geq 1$ and $k=n,n+1,\ldots,2n-1$ we have $$\frac{k-n+1}{n}\binom{2n}{k+1}=\sum_{i=0}^{2n-1-k} \frac{2k-2n+1}{k-i}\binom{2(n-i-1)}{k-i-1} \cdot C_i \enspace. \quad (2)$$

For the special case $k=n$ equation (2) is the well-known relation $$C_n=\sum_{i=0}^{n-1} C_{n-1-i} C_i \enspace. \quad (2')$$ For the special case $k=n+1$ equation (2) yields \begin{equation*} C_n=\frac{n+2}{2(n-1)} \sum_{i=0}^{n-2} \frac{3(n-1-i)}{n+1-i} \cdot C_{n-1-i} C_i \enspace, \quad (2'') \end{equation*} a weighted sum with one term less than (2').

I appreciate any hints, pointers etc.!

• (1) is a fairly simple equivalent form of the standard recurrence $C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$. Indeed, the right hand side of (1) does not change if I replace $4i+3$ by $4\left(n-1-i\right)+3$ (because this is tantamount to substituting $n-1-i$ for $i$ in the sum). Therefore it also does not change if I replace $4i+3$ by $\left(4i+3\right)+\left(4\left(n-1-i\right)+3\right) = 4n+2$ and then divide the whole sum by $2$. But if I do that, the right hand side becomes $\left(4n+2\right) \sum_{i=0}^{n-1} C_i C_{n-1-i}$, and then everything boils down to the standard recurrence. – darij grinberg Jul 3 '15 at 1:29
• Thanks Darij, if this was a regular post, I would vote it as a top answer. – Torsten Mütze Jul 7 '15 at 14:21

The first identity is know to Mathematica, in a weird form. $$\frac{2^{2 n} (2 n+1) \Gamma \left(\frac{1}{2} (2 n+1)\right)}{\sqrt{\pi } (n+1) \Gamma (n+1)}.$$ The second, it seems to have trouble with, but this should be standard hypergeometric summation (Gosper or W-Z).
$${\frac { \left( 2\,k-2\,n+1 \right) {\mbox{_4F_3}(1/2,1,-k,-2\,n+1+k;\,2,-n+1,-n+3/2;\,1)}\Gamma \left( 2\,n-1 \right) }{\Gamma \left( 1+k \right) \Gamma \left( 2\, n-k \right) }}$$ which does appear to be correct for $2n-1 \ge k > n$ but not for $k=n$.
The case $k=n+1$ can be verified with generating functions: $$C(z) = \sum_{i=0}^\infty c_i z^i .$$ For the Catalan numbers such function is given by $$C(z) = \frac{1-\sqrt{1-4z}}{2z} .$$ Given any two generating functions $A$ and $B$ their product is the generating function for the convolution of the two sequences $(a_i)$ and $(b_i)$ $$A(z)\,B(z) = \sum_{i=0}^\infty a_i z^i \sum_{j=0}^\infty b_j z^j = \sum_{n=0}^\infty z^n \sum_{i=0}^n a_i b_{n-i} .$$ The terms in the summation in (2'') look like a convolution of $c_i$ and $\frac{j}{j+2}c_j$. To get the necessary form one can differentiate and integrate. For instance \begin{multline*} z^2 \frac{d}{dz} \left( \frac{1}{z^2} \int_0^z t C(t)\, dt \right) = z^2 \frac{d}{dz} \left( \frac{1}{z^2} \int_0^z t \sum_{i=0}^\infty c_i t^i \, dt \right) = z^2 \frac{d}{dz} \left( \sum_{i=0}^\infty \frac{1}{z^2} \int_0^z c_i t^{i+1} \, dt \right) \\ = z^2 \frac{d}{dz} \left( \sum_{i=0}^\infty \frac{1}{z^2} \frac{c_i}{i+2} z^{i+2} \right) = z^2 \frac{d}{dz} \left( \sum_{i=0}^\infty \frac{c_i}{i+2} z^{i} \right) = \sum_{i=1}^\infty \frac{i}{i+2} c_i z^{i+1} \enspace . \end{multline*} First few terms are $$\frac{1}{3}\cdot z^2 + 1\cdot z^3 + 3\cdot z^4 + \frac{28}{3}\cdot z^5 + 30\cdot z^6 + 99\cdot z^7 + \frac{1001}{3}\cdot z^8 + \cdots .$$ Thus \begin{multline*} \sum_{i=0}^\infty c_i z^i \sum_{j=1}^\infty \frac{j}{j+2} c_j z^{j+1} = c_0 \frac{1}{3} c_1 z^2 + \left(c_0 \frac{2}{4} c_2+ c_1 \frac{1}{3} c_1 \right) z^3 + \cdots \\ = \sum_{n=2}^\infty z^n \sum_{k=0}^{n-2} c_k c_{n-k-1} \frac{n-k-1}{n-k+1} . \end{multline*} Continuing in this fashion we arrive at the following equation, equivalent to identity (2'') $$\frac{3}{2z}\cdot \frac{d}{dz} \left( z^3 \int_0^z \left( C(z) \cdot\frac{d}{dz} \left( \frac{1}{z^2} \int_0^z z\cdot C(z) \, dz \right) \right) \, dz \right) = C(z) - z - 1 ,$$ which can be easily verified.