Results 1 to 14 of 14

Math Help - Induction question - combinatorics

  1. #1
    Junior Member
    Joined
    Sep 2010
    Posts
    36

    Induction question - combinatorics

    Prove for all 'm' >=1:

    \sum_{k=0}^m (k*m-choose-k) = m.2^(m-1)

    Im guessing this is an induction problem... and may need to use Pascal's formula but I have got nothing.

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by mathswannabe View Post
    Prove for all 'm' >=1:

    \sum_{k=0}^m (k*m-choose-k) = m.2^(m-1)

    Im guessing this is an induction problem... and may need to use Pascal's formula but I have got nothing.

    Thanks
    In LaTeX:

    Prove for all m \ge 1:

    \displaystyle\sum_{k=0}^m k\cdot\binom{m}{k} = m\cdot2^{m-1}

    If you start with the sum, then rewrite the binomial coefficient with factorials, then divide the sum by m, you should notice something..
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Sep 2010
    Posts
    36
    Sorry,do you think you could help a little mre? What is the binomial coefficient? mchoosek?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by mathswannabe View Post
    Sorry,do you think you could help a little mre? What is the binomial coefficient? mchoosek?
    Yes

    Binomial coefficient - Wikipedia, the free encyclopedia

    You know \binom{n}{k}=\frac{n!}{k!(n-k)!} right?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Sep 2010
    Posts
    36
    Yes I know what that is. Writing it in factorial.... You get the sum of :k*m!/((m-k)!k!) which simplifies to m!/(m-k)!(k-1)! --> dividing by m, --> (m-1)!/(m-k)!(k-1)!.....

    But i don't see what you want me to see. Sorry - have I done something wrong???
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by mathswannabe View Post
    Yes I know what that is. Writing it in factorial.... You get the sum of :k*m!/((m-k)!k!) which simplifies to m!/(m-k)!(k-1)! --> dividing by m, --> (m-1)!/(m-k)!(k-1)!.....

    But i don't see what you want me to see. Sorry - have I done something wrong???
    Let u=m-1.
    Let v=k-1.

    Maybe you see it now?

    Also if you're not aware, \sum_{k=0}^n\binom{n}{k}=2^n.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Sep 2010
    Posts
    36
    Thanks for your help so far....

    So this is what i've got:
    Induction question - combinatorics-screen-shot-2010-10-07-7.21.40-pm.png

    Now im guessing that we can then say that the right hand side = 2^u = 2^(m-1) which is the RHS.

    Awesome. But... for this to be true, wouldn't the sum need to be the sum from v = 0 to u, but its not, its from k=0 to m, which is essentially v+1=0 to u+1? So are you sure this will still work????

    Thanks again for all of your help so far
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by mathswannabe View Post
    Thanks for your help so far....

    So this is what i've got:
    Click image for larger version. 

Name:	Screen shot 2010-10-07 at 7.21.40 PM.png 
Views:	11 
Size:	27.6 KB 
ID:	19212

    Now im guessing that we can then say that the right hand side = 2^u = 2^(m-1) which is the RHS.

    Awesome. But... for this to be true, wouldn't the sum need to be the sum from v = 0 to u, but its not, its from k=0 to m, which is essentially v+1=0 to u+1? So are you sure this will still work????

    Thanks again for all of your help so far
    You're welcome.

    In the original sum, when k=0, the expression you are summing is also 0. You can adjust the start index accordingly.

    While you can start with the equation you want to prove and write a little question mark above the equals sign, I think it's cleaner if you just start with the sum (LHS) and then work your way to the answer. You can multiply by m/m to keep track of your manipulation. And if it were me I would just replace all the m's when substituting, then substitute back afterwards. Here I'll show you.

    \displaystyle \sum_{k=0}^m k\binom{m}{k}


    \displaystyle =\sum_{k=1}^m k\binom{m}{k}


    \displaystyle =\frac{m}{m}\sum_{k=1}^m k\binom{m}{k}


    \displaystyle =m\sum_{k=1}^m \frac{k}{m}\binom{m}{k}


    \displaystyle =m\sum_{k=1}^m \frac{k\cdot m!}{m\cdot k!(m-k)!}


    \displaystyle =m\sum_{k=1}^m \frac{(m-1)!}{(k-1)!(m-k)!}


    \displaystyle =m\sum_{k=1}^m \frac{(m-1)!}{(k-1)!(m-1-(k-1))!}


    Let \,u=m-1,v=k-1. We obtain


    \displaystyle m\sum_{v=0}^u \frac{u!}{v!(u-v)!}


    \displaystyle =m\sum_{v=0}^u \binom{u}{v}


    \displaystyle =m\cdot2^u


    \displaystyle =m\cdot2^{m-1}
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    This question can be solve also using calculus (derivative) or with giving a combinatorial explanation (by finding a word problem that the answer is RIGHT side an the LEFT side).
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Sep 2010
    Posts
    36
    Thanks for all your help. I've just got one more question. Why I it when you sub u and v in are you allowed to change the sum? I get the bottom bit: v = k-1 therefore on the bottom you have v+1=1 -->v=0. But I just don't get the top bit? You had m up there and you just replaced with u but u is m-1 is that allowed? Or does it have something to do with that the subscript has gone back to '=0' not =1??
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by mathswannabe View Post
    Thanks for all your help. I've just got one more question. Why I it when you sub u and v in are you allowed to change the sum? I get the bottom bit: v = k-1 therefore on the bottom you have v+1=1 -->v=0. But I just don't get the top bit? You had m up there and you just replaced with u but u is m-1 is that allowed? Or does it have something to do with that the subscript has gone back to '=0' not =1??
    k goes from 1 to m is the same as (k-1) goes from 0 to (m-1).
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    A Proof By Induction is also possible...

    P(m)

    \displaystyle\sum_{k=0}^mk\binom{m}{k}=m2^{m-1}


    P(m+1)

    \displaystyle\sum_{k=0}^{m+1}k\binom{m+1}{k}=(m+1)  2^m


    Proof

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

    Therefore...

    \displaystyle\sum_{k=0}^{m+1}k\binom{m+1}{k}=\sum_  {k=0}^{m+1}k\left[\binom{m}{k}+\binom{m}{k-1}\right]

    =\displaystyle\sum_{k=0}^mk\binom{m}{k}+\sum_{k=1}  ^{m+1}k\binom{m}{k-1}

    and if P(m) is valid, this will be

    =m2^{m-1}+\displaystyle\sum_{j=0}^m(j+1)\binom{m}{j}=m2^{  m-1}+\sum_{j=0}^mj\binom{m}{j}+\sum_{j=0}^m\binom{m}  {j}

    =m2^{m-1}+m2^{m-1}+2^m

    =2m2^{m-1}+2^m=(m+1)2^m
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Sep 2010
    Posts
    36
    Archie Meade... After your 'therefore step' can you please explain how you got to the second equals sign after that? I thought you would have 4 terms?
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor
    Joined
    Dec 2009
    Posts
    3,120
    Thanks
    1
    Quote Originally Posted by Archie Meade View Post
    A Proof By Induction is also possible...

    P(m)

    \displaystyle\sum_{k=0}^mk\binom{m}{k}=m2^{m-1}


    P(m+1)

    \displaystyle\sum_{k=0}^{m+1}k\binom{m+1}{k}=(m+1)  2^m


    Proof

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

    Therefore...

    \displaystyle\sum_{k=0}^{m+1}k\binom{m+1}{k}=\sum_  {k=0}^{m+1}k\left[\binom{m}{k}+\binom{m}{k-1}\right]

    =\displaystyle\sum_{k=0}^mk\binom{m}{k}+\sum_{k=1}  ^{m+1}k\binom{m}{k-1}

    because we cannot make a selection of m+1 elements from m elements
    and we cannot select -1 elements from m elements
    .

    and if P(m) is valid, this will be

    =m2^{m-1}+\displaystyle\sum_{j=0}^m(j+1)\binom{m}{j}=m2^{  m-1}+\sum_{j=0}^mj\binom{m}{j}+\sum_{j=0}^m\binom{m}  {j}

    =m2^{m-1}+m2^{m-1}+2^m

    =2m2^{m-1}+2^m=(m+1)2^m
    Hi mathswannabe,

    is this the answer you wanted ?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. combinatorics question
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 10th 2011, 10:37 AM
  2. Combinatorics Question
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 28th 2009, 09:55 AM
  3. combinatorics question -- please help
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 30th 2009, 11:10 PM
  4. Combinatorics Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 10th 2008, 10:21 AM
  5. Combinatorics question
    Posted in the Advanced Math Topics Forum
    Replies: 5
    Last Post: December 8th 2007, 02:12 PM

Search Tags


/mathhelpforum @mathhelpforum