I want to prove the following statement:

$$ \beta(t,x)=C(1+t,x)= \frac {C((1+t)x)} {1-xC((1+t)x)} $$

Where $C(x)$ is the generating function for the Catalan Numbers and $ \beta(x) $ is the Borel generating function.

I know I have to use the fact that $$ C(t,x)= \frac {C(tx)} {1-xC(tx)}$$ But unsure what other statements i need to use. Any help would be great thanks.


We assume \begin{align*} C(t,x)&=\sum_{n=0}^\infty\sum_{k=0}^n C_{n,k}t^kx^n=\frac{C(tx)}{1-xC(tx)}\tag{1}\\ B_{n,k}&=\sum_{s=k}^n\binom{s}{k}C_{n,s}\tag{2} \end{align*}

We obtain from (2) \begin{align*} \color{blue}{\sum_{k=0}^nB_{n,k}t^k}&=\sum_{k=0}^n\sum_{s=k}^n\binom{s}{k}C_{n,s}t^k\\ &=\sum_{s=0}^nC_{n,s}\sum_{k=0}^s\binom{s}{k}t^k\tag{3}\\ &\,\,\color{blue}{=\sum_{s=0}^nC_{n,s}(1+t)^s}\tag{4} \end{align*}


  • In (3) we use $\sum_{k=0}^n\sum_{s=k}^n a_{k,s}=\sum_{\color{blue}{0\leq k\leq s\leq n}} a_{k,s}=\sum_{s=0}^n\sum_{k=0}^s a_{k,s}$.

  • In (4) we apply the binomial theorem.

We finally obtain from (4) \begin{align*} \color{blue}{\mathcal{B}(t,x)}&=\sum_{n=0}^\infty\sum_{k=0}^n B_{n,k}t^kx^n\\ &=\sum_{n=0}^\infty\sum_{s=0}^nC_{n,s}(1+t)^s x^n\tag{$4 \leftarrow$}\\ &\,\,\color{blue}{=\frac{C((1+t)x)}{1-xC((1+t)x)}}\tag{$1 \leftarrow $} \end{align*} and the claim follows.


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.