Results 1 to 6 of 6

Math Help - [SOLVED] Prove the following combinatorial identity?

  1. #1
    Super Member fardeen_gen's Avatar
    Joined
    Jun 2008
    Posts
    539

    [SOLVED] Prove the following combinatorial identity?

    By expanding (x/(1 - x))^n , 0<x<1 , in 2 ways, prove that:

    nC0(2n-1)Cn - nC1(2n - 2)Cn + nC2(2n - 3)Cn - ... = 1

    NOTE: nC0 represents n choose 0.
    nC0(2n-1)Cn represents (n choose 0) multiplied by (2n - 1 choose n)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by fardeen_gen View Post
    By expanding (x/(1 - x))^n , 0<x<1 , in 2 ways, prove that:

    nC0(2n-1)Cn - nC1(2n - 2)Cn + nC2(2n - 3)Cn - ... = 1

    NOTE: nC0 represents n choose 0.
    nC0(2n-1)Cn represents (n choose 0) multiplied by (2n - 1 choose n)
    Use the binomial expansion (1-x)^{-k} = 1 + kx + \tfrac{k(k+1)}{2!}x^2 + \tfrac{k(k+1)(k+2)}{3!}x^3 + \ldots = \sum_{j=0}^\infty{k+j-1\choose j}x^j.

    Then \Bigl(\tfrac x{1-x}\Bigr)^n = x^n(1+nx+\ldots). But also \tfrac x{1-x} = -\bigl(1-\tfrac1{1-x}\bigr), and so

    \begin{aligned}\Bigl(\tfrac x{1-x}\Bigr)^n = (-1)^n\Bigl(1-\tfrac1{1-x}\Bigr)^n &= (-1)^n\sum_{k=0}^n{n\choose k}\Bigl(\tfrac{-1}{1-x}\Bigr)^k \\ &= (-1)^n\sum_{k=0}^n{n\choose k}(-1)^k\sum_{j=0}^\infty{k+j-1\choose j}x^j\end{aligned}
    (using the above expansion for (1-x)^{-k}).

    Now compare the coefficients of x^n in the two expansions of \Bigl(\tfrac x{1-x}\Bigr)^n.
    Last edited by Opalg; February 10th 2009 at 02:11 AM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member fardeen_gen's Avatar
    Joined
    Jun 2008
    Posts
    539
    That gave me:
    1 = nC0.(n-1)Cn - nC1.nCn + nC2.(n + 1)Cn + ...
    Which is obviously wrong.
    What am I missing?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by fardeen_gen View Post
    That gave me:
    1 = nC0.(n-1)Cn - nC1.nCn + nC2.(n + 1)Cn + ...
    Which is obviously wrong.
    What am I missing?
    It's not wrong. It's a finite series, which looks like
    1 = \textstyle(-1)^n\Bigl({n\choose0}{n-1\choose n} - {n\choose1}{n\choose n} + {n\choose2}{n+1\choose n} - \ldots + (-1)^{n-1}{n\choose n-1}{2n-2\choose n} + (-1)^n{n\choose n}{2n-1\choose n}\Bigr).
    Now write the terms in reverse order, and use the fact that \textstyle{n\choose k} = {n\choose n-k}.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member fardeen_gen's Avatar
    Joined
    Jun 2008
    Posts
    539
    What is (n - 1)Cn?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by fardeen_gen View Post
    What is (n - 1)Cn?
    I think you have to interpret that as 0. You can check that by tracing this term back to where it came from in the expansion of \Bigl(\tfrac{-1}{1-x}\Bigr)^k.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove the identity using a combinatorial proof
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 25th 2011, 06:51 PM
  2. Combinatorial proof for an identity
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: April 23rd 2011, 04:12 PM
  3. combinatorial identity problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 23rd 2010, 10:46 PM
  4. (Basic) Combinatorial Identity.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 1st 2010, 10:12 PM
  5. [SOLVED] Prove the identity, Stuck?
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: August 7th 2009, 06:51 AM

Search Tags


/mathhelpforum @mathhelpforum