Relation between Catalan numbers

[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)$$


The relation reads:

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

 

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

sorry that i can't help you more.

 

[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?;-)