Results 1 to 4 of 4

Math Help - Proof of binomial sums

  1. #1
    Junior Member CuriosityCabinet's Avatar
    Joined
    Aug 2010
    From
    UK
    Posts
    32
    Thanks
    1

    Proof of binomial sums

    Prove:
    \binom{m+n}{k} = \sum_{i=0}^{k}\binom{m}{i} \binom{n}{k-i}

    for m, n \geq 0 and  0 \leq k\leq m+n.

    I considered (1+x)^m(1+x)^n but got stuck at manipulating double sums. Please help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Sep 2009
    Posts
    112

    Re: Proof of binomial sums

    Have you looked at this property? \binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}

    So for example: \binom{n+2}{k} =\binom{(n+2)-1}{k} + \binom{(n+2)-1}{k-1}

    = \binom{n+1}{k} + \binom{n+1}{k-1}

    =\binom{n}{k} + \binom{n}{k-1} + \binom{n}{k-1} + \binom{n}{(k-1)-1}
    =\binom{n}{k} + 2\binom{n}{k-1} + \binom{n}{k-2}

    This may help a little.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2011
    From
    Awetuouncsygg
    Posts
    182
    Thanks
    12

    Re: Proof of binomial sums

    \binom{m+n}{k} = \sum_{i=0}^{k}\binom{m}{i} \binom{n}{k-i}

    The second sum is the coefficient of x^{i+k-i}=x^{k} from (1+x)^m \cdot (1+x)^n= (1+x)^{m+n}.

    (1+x)^{m+n}=\sum_{k=0}^{m+n} \binom{m+n}{k} \cdot 1^{m+n-k} \cdot x^k=\sum_{k=0}^{m+n} \binom{m+n}{k} \cdot x^k
    Last edited by veileen; November 8th 2011 at 05:09 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1

    Re: Proof of binomial sums

    Quote Originally Posted by CuriosityCabinet View Post
    Prove:
    \binom{m+n}{k} = \sum_{i=0}^{k}\binom{m}{i} \binom{n}{k-i}
    for m, n \geq 0 and \color{red} 0 \leq k\leq m+n.
    FIRST, it must be pointed out that the is a mistake in the question.
    This is Vandermonde's Theorem it should be 0\le k\le\min\{m,n\}

    We can do a combinational proof.
    \binom{m+n}{k} is the number of ways to choose k items from m+n.
    If 0\le j\le k then \binom{m}{j}\binom{n}{k-j} is the number of ways to choose those k items with j coming from the m group and k-j coming from the n group.
    Now it us easy to see that
    \binom{m+n}{k} = \sum_{i=0}^{k}\binom{m}{i} \binom{n}{k-i}.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. marginal moment for random sums - question about proof
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: February 1st 2011, 12:12 AM
  2. An Equality of Binomial Sums
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 16th 2010, 12:25 AM
  3. squaring sums, expand the given binomial sum.
    Posted in the Algebra Forum
    Replies: 1
    Last Post: April 9th 2010, 11:50 PM
  4. Sums of Binomial Coefficients - proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 22nd 2010, 07:44 AM
  5. Induction proof involving sums of consecutive powers
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 2nd 2009, 06:01 AM

Search Tags


/mathhelpforum @mathhelpforum