Relation between Catalan numbers

1. Oct 22, 2007

Pere Callahan

Hello all,

I am studying some problems in Free Probability and need to prove a relation between the Catalan numbers

$$C_n = \frac{1}{n+1}\left(\stackrel{2n}{n}\right)$$

$$1 = \sum_{l=1}^{k}{(-1)^{l-1}C_{l-1}\left(\stackrel{l+k-1}{k-l}\right)}\quad\quad\forall\quad 1\leq k\in\mathbb{N}$$

Does anybode have an idea how to prove this? Numerically, I convinced myself that it is true for $$n\leq 100 000$$ or so

I tried induction but it didn't work out.

Thanks
Pere

Btw.: Is there a better way to display binomial coefficients....? I used \stackrel ...

Last edited: Oct 22, 2007
2. Oct 24, 2007

MathematicalPhysicist

well i don't have the head for this but one way you could do is write the generating function of the sum and then equating coefficients, where you should multiply the generating function of (-1)^(l-1)C_l-1 with the generating function of C(2k-l-1,l), and check any descent combinatorics book on catalan number in generating functions as to how to find the generating function of this.

3. Oct 27, 2007

Pere Callahan

Hi,
Thanks for your answer. I finally managed to prove the relation - using Generating Functions.

If we let

$$a_k = \sum_{l=1}^{k}{(-1)^{l-1}C_{l-1}\left(\stackrel{l+k-1}{k-l}\right)}$$

we need to show

$$\sum_{k=1}^\infty{a_k x^k} = \frac{x}{1-x}$$

because the right hand side would also be the generating function of the constant sequence $$(\alpha_i)_{i=1}^\infty=(1)_{i=1}^\infty$$.

I then continued as follows:

$$\sum_{k=1}^\infty{a_k x^k} = \sum_{k=1}^\infty{\sum_{l=1}^{k}{(-1)^{l-1}C_{l-1}\left(\stackrel{l+k-1}{k-l}\right)}x^k}= \sum_{l=1}^\infty{\sum_{k=l}^{\infty}{(-1)^{l-1}C_{l-1}\left(\stackrel{l+k-1}{2l-1}\right)}x^k}= \sum_{l=1}^\infty{{(-1)^{l-1}C_{l-1}x^l\sum_{k=0}^{\infty}\left(\stackrel{k+2l-1}{2l-1}\right)}x^k}=\sum_{l=1}^\infty{{(-1)^{l-1}C_{l-1}\frac{x^l}{(1-x)^{2l}}}$$

Where the relation

$$\sum_{k=0}^{\infty}\left(\stackrel{k+m}{m}\right)}x^k} = \frac{1}{(1-x)^{m+1}}$$

can easiliy be shown by induction on m.

So I continued

$$\sum_{l=1}^\infty{{(-1)^{l-1}C_{l-1}\frac{x^l}{(1-x)^{2l}}} = \frac{x}{(1-x)^2}\sum_{l=0}^\infty{{C_{l}\left(\frac{-x}{(1-x)^{2}}\right)^l} = \frac{x}{(1-x)^2} C\left(\frac{-x}{(1-x)^{2}}\right)$$

Where $$C(x)=\frac{1-\sqrt{1-4x}}{2x}$$ is the generating function of the Catalan numbers.

For $$-1\leq x\leq1$$

We then have

$$\frac{x}{(1-x)^2} C\left(\frac{-x}{(1-x)^{2}}\right)=\frac{x}{(1-x)^2}\frac{1-\sqrt{1+\frac{4x}{(1-x)^{2}}}}{2\frac{-x}{(1-x)^{2}}}=\frac{\sqrt\frac{(1+x)^2}{(1-x)^2}-1}{2}=\frac{1+x-1+x}{2(1-x)}=\frac{x}{1-x}$$

Looks correct to me...? Any objections?;-)

Last edited: Oct 27, 2007