2
$\begingroup$

Let $C_n = {2n \choose n}\frac{1}{n+1} = \frac{(2n)!}{n!(n+1)!}$ be the $n$th Catalan number. Then there is a recursion formula: $C_{n+1} = \sum_{i=0}^n C_i C_{n-i}$. Now let $C_{n,k} = {2n+k-1 \choose n}\frac{k}{n+k}$. Then $C_{n,1}=C_n$. Are there some recursion formulas known for $C_{n,k}$? Thank you very much.

$\endgroup$

2 Answers 2

5
$\begingroup$

Here is one way to use the generating function to get a recurrence. Let $y=f(x)^k$. Then $f(x)y'=kf'(x)y$. We can equate coefficients of $x^n$ to get a recurrence involving Catalan numbers. This can be simplified using $$ \frac{f'(x)}{f(x)} = \sum_{n\geq 0}{2n+1\choose n}x^n=g(x), $$ say, so $y'=kyg(x)$. Again equate coefficients of $x^n$.

$\endgroup$
4
$\begingroup$

Let the generating function of $C_n$ be $f(x)$. The g.f. of $C_{n,k}$ is $f(x)^k$ so we can derive recursion formulas. The coefficient array of $C_{n,k}$ is OEIS sequence A009766 which has many references to the literature. Using $f(x)^{j+k}=f(x)^jf(x)^k$ gives $C_{n,j+k}$ as the discrete convolution product of $C_{n,j}$ and $C_{n,k}$. For example, with $j=k=1$, then $\;C_{n+1,1}=C_{n,2}=\sum_{i=0}^nC_{i,1}C_{n-i,1}.$

Use the equation $\;1=1/f(x)+xf(x)$ to derive $\;C_{n,k}=C_{n,k-1}+C_{n-1,k+1}\;$ for all $\;k>0$.

$\endgroup$
1
  • $\begingroup$ thank you very much. I know how to use generating function to solve recursion relation. But how to using generating function to derive recursion relation? $\endgroup$ Sep 27, 2017 at 15:38

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.