4
$\begingroup$

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 \begin{equation} \binom{2n}{n} + \binom{2n}{n-1} = \sum_{i=0}^{n-1} (4i+3)C_i C_{n-i-1} \enspace. \quad (1) \end{equation}

(2) For any $n\geq 1$ and $k=n,n+1,\ldots,2n-1$ we have \begin{equation} \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) \end{equation}

For the special case $k=n$ equation (2) is the well-known relation \begin{equation} C_n=\sum_{i=0}^{n-1} C_{n-1-i} C_i \enspace. \quad (2') \end{equation} 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.!

$\endgroup$
  • 1
    $\begingroup$ (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. $\endgroup$ – darij grinberg Jul 3 '15 at 1:29
  • $\begingroup$ Thanks Darij, if this was a regular post, I would vote it as a top answer. $\endgroup$ – Torsten Mütze Jul 7 '15 at 14:21
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So what is the identity, I don't see an equality sign? Could you please post the Mathematica code you used to verify this identity, thanks! $\endgroup$ – Torsten Mütze Jul 2 '15 at 23:19
  • $\begingroup$ Your RHS equals the expression in the answer... $\endgroup$ – Igor Rivin Jul 3 '15 at 1:28
1
$\begingroup$

Maple 18 manages the following for the right side of the second identity:

$$ {\frac { \left( 2\,k-2\,n+1 \right) {\mbox{$_4$F$_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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.