Results 1 to 3 of 3

Math Help - binomial identities

  1. #1
    Member billym's Avatar
    Joined
    Feb 2008
    Posts
    183

    Red face binomial identities

    \binom{2n}{n} = \sum_{r=0}^{n}\binom{n}{r}^{2}

    Can somebody start me on this? I have the identities in front of me, but I just make a mess. No clue. Like what does:

    \sum_{r=0}^{n}\binom{n}{r}^{2}

    become?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    Quote Originally Posted by billym View Post
    \binom{2n}{n} = \sum_{r=0}^{n}\binom{n}{r}^{2}

    Can somebody start me on this? I have the identities in front of me, but I just make a mess. No clue. Like what does:

    \sum_{r=0}^{n}\binom{n}{r}^{2}

    become?
    It will help if you think of it this way.

    \binom{2n}{n} is asking how many ways can I arrange n objects in 2n spots.


    So lets break this up into a two part problem. For simplicity I will use n=3 and let you generalize

    So we have

    \binom{2\cdot 3}{3}=\binom{6}{3}

    So we have 3 objects and 6 six spots

    _ _ _ , _ _ _

    Now we ask if I put 0 ojects in the first 3 spots I can do this in
    \binom{3}{0} ways, but this forces me to put all 3 in the last 3 spots and I can do this in
    \binom{3}{3} ways

    Now if I put 1 object in the first 3 spots I then have to put 2 in the last 3 I can do this in
    \binom{3}{1},\text{ and } \binom{3}{2} ways respectively

    Next will be 2 objects in the first 3 spots and 1 in the last three with

    \binom{3}{2},\text{ and } \binom{3}{2} ways respectively

    and finally 3 objects in the first 3 spots and none in the last three gives

    \binom{3}{3},\text{ and } \binom{3}{0} ways respectively

    So the total number of ways to do this is

    \binom{3}{0}\binom{3}{3}+\binom{3}{1}\binom{3}{2}+  \binom{3}{2}\binom{3}{1}+\binom{3}{3}\binom{3}{0}

    Now remember that

    \binom{n}{k}=\binom{n}{n-k} using this we get

    \binom{3}{0}^2+\binom{3}{1}^2+\binom{3}{2}^2+\bino  m{3}{3}^2=\sum_{k=0}^{3}\binom{3}{k}^2

    This is the logic you need for the general proof.

    I hope this helps. Good luck.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Bruno J.'s Avatar
    Joined
    Jun 2009
    From
    Canada
    Posts
    1,266
    Thanks
    1
    Awards
    1
    Here is one way to see it.

    We have (1+x)^n=\sum_{j=0}^n{n \choose j}x^j. We can write this backwards as (1+x)^n=\sum_{j=0}^n{n \choose n-j}x^{n-j}. If you multiply both equalities, you have

    (1+x)^{2n}=\left(\sum_{j=0}^n{n \choose j}x^j\right)\left(\sum_{j=0}^n{n \choose n-j}x^{n-j}\right).

    The coefficient of x^n in the left-hand side is {2n \choose n}, and the coefficient of x^n in the right-hand side is seen to be equal to \sum_{j=0}^n{n \choose j}{n \choose n-j}=\sum_{j=0}^n{n \choose j}^2.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: July 15th 2010, 06:33 AM
  2. Replies: 6
    Last Post: June 23rd 2010, 12:59 AM
  3. Replies: 1
    Last Post: November 12th 2009, 01:38 AM
  4. Replies: 1
    Last Post: March 12th 2009, 12:09 AM
  5. Relation between Negative Binomial and Binomial Distros
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: November 5th 2007, 07:59 AM

Search Tags


/mathhelpforum @mathhelpforum