Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Relation between Catalan numbers

  1. Oct 22, 2007 #1
    Hello all,

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

    [tex]C_n = \frac{1}{n+1}\left(\stackrel{2n}{n}\right)[/tex]

    The relation reads:

    [tex]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}[/tex]

    Does anybode have an idea how to prove this? Numerically, I convinced myself that it is true for [tex]n\leq 100 000[/tex] or so:smile:

    I tried induction but it didn't work out.


    Btw.: Is there a better way to display binomial coefficients....? I used \stackrel ...
    Last edited: Oct 22, 2007
  2. jcsd
  3. Oct 24, 2007 #2


    User Avatar
    Gold Member

    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.
  4. Oct 27, 2007 #3
    Thanks for your answer. I finally managed to prove the relation - using Generating Functions.

    If we let

    [tex]a_k = \sum_{l=1}^{k}{(-1)^{l-1}C_{l-1}\left(\stackrel{l+k-1}{k-l}\right)}[/tex]

    we need to show

    [tex]\sum_{k=1}^\infty{a_k x^k} = \frac{x}{1-x}[/tex]

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

    I then continued as follows:

    [tex]\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}}}[/tex]

    Where the relation

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

    can easiliy be shown by induction on m.

    So I continued

    [tex]\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)[/tex]

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

    For [tex]-1\leq x\leq1[/tex]

    We then have

    [tex]\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}[/tex]

    Looks correct to me...? Any objections?;-)
    Last edited: Oct 27, 2007
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook