Results 1 to 4 of 4

Thread: 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:
    $\displaystyle \binom{m+n}{k} = \sum_{i=0}^{k}\binom{m}{i} \binom{n}{k-i}$

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

    I considered $\displaystyle (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? $\displaystyle \binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$

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

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

    $\displaystyle =\binom{n}{k} + \binom{n}{k-1} + \binom{n}{k-1} + \binom{n}{(k-1)-1}$
    $\displaystyle =\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

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

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

    $\displaystyle (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; Nov 8th 2011 at 05:09 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,742
    Thanks
    2814
    Awards
    1

    Re: Proof of binomial sums

    Quote Originally Posted by CuriosityCabinet View Post
    Prove:
    $\displaystyle \binom{m+n}{k} = \sum_{i=0}^{k}\binom{m}{i} \binom{n}{k-i}$
    for $\displaystyle m, n \geq 0$ and$\displaystyle \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 $\displaystyle 0\le k\le\min\{m,n\}$

    We can do a combinational proof.
    $\displaystyle \binom{m+n}{k}$ is the number of ways to choose k items from m+n.
    If $\displaystyle 0\le j\le k$ then $\displaystyle \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
    $\displaystyle \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: Feb 1st 2011, 12:12 AM
  2. An Equality of Binomial Sums
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Aug 16th 2010, 12:25 AM
  3. squaring sums, expand the given binomial sum.
    Posted in the Algebra Forum
    Replies: 1
    Last Post: Apr 9th 2010, 11:50 PM
  4. Sums of Binomial Coefficients - proof by induction
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Jan 22nd 2010, 07:44 AM
  5. Induction proof involving sums of consecutive powers
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Sep 2nd 2009, 06:01 AM

Search Tags


/mathhelpforum @mathhelpforum