Thread: Induction question - combinatorics

1. 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

2. Originally Posted by mathswannabe
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 $\displaystyle m \ge 1$:

$\displaystyle \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..

3. Sorry,do you think you could help a little mre? What is the binomial coefficient? mchoosek?

4. Originally Posted by mathswannabe
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 $\displaystyle \binom{n}{k}=\frac{n!}{k!(n-k)!}$ right?

5. 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???

6. Originally Posted by mathswannabe
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, $\displaystyle \sum_{k=0}^n\binom{n}{k}=2^n$.

7. Thanks for your help so far....

So this is what i've got:

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

8. Originally Posted by mathswannabe
Thanks for your help so far....

So this is what i've got:

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

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

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

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

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

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

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

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

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

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

$\displaystyle \displaystyle =m\cdot2^u$

$\displaystyle \displaystyle =m\cdot2^{m-1}$

9. 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).

10. 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??

11. Originally Posted by mathswannabe
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).

12. A Proof By Induction is also possible...

P(m)

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

P(m+1)

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

Proof

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

Therefore...

$\displaystyle \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 =\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

$\displaystyle =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}$

$\displaystyle =m2^{m-1}+m2^{m-1}+2^m$

$\displaystyle =2m2^{m-1}+2^m=(m+1)2^m$

13. 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?

14. Originally Posted by Archie Meade
A Proof By Induction is also possible...

P(m)

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

P(m+1)

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

Proof

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

Therefore...

$\displaystyle \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 =\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

$\displaystyle =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}$

$\displaystyle =m2^{m-1}+m2^{m-1}+2^m$

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

is this the answer you wanted ?