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 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.
Let . We obtain
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??