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
Yes
Binomial coefficient - Wikipedia, the free encyclopedia
You know $\displaystyle \binom{n}{k}=\frac{n!}{k!(n-k)!}$ right?
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}$
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??
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$