How can the sum of combinations be solved for the given problem?

[gumi_kr]

Hi!

Does anybody know how to solve the following problem:


\sum_{p=0}^{M}\binom{2M+2}{p}(M+1-p)=?

Well, actually i know that the solution is:

(2M+1)\binom{2M}{m}=\frac{2^{2M+1}\Gamma(\frac{3}{2}+M)}{\sqrt{\pi}\Gamma(M+1)}

but i cannot prove it (mathematica calculates the first sum and gives the answer).

Maybe someone knows the simple (combinatorial?) solution?


The original problem was:

Let R ^{M} _{P} = \sum_{s = 0}^{P} {M + 1 \choose s}, for 0 \leqslant P \leqslant M, P,M\in \mathbb{N}

Proove that:
\sum_{q = 0}^{M}R^{M}_{q}\cdot R^{M}_{M - q} = (2M + 1) {2M \choose M}

 

[chaoseverlasting]

Do you have any idea where to start from?

 

[chaoseverlasting]

I nuked it. Its simpler than I thought, though you'll have to get the answer in terms of the gamma function yourself which shouldn't be too hard.

If you take the binomial expansion of (1+x)^n you have

(1+x)^n=\sum_{r=0}^{n}{n\choose r}x^{n-r}

Replacing n=2m+2, differentiating the above equation and put x=1.

Then you have to change the limit of the summation from 2m+2 to m+1, you can do this because the terms from 0 to m+1 are equal to the terms from m+2 to 2m+2, hence the sum on the right is twice the sum from 0 to m+1.

From this you get a solution in terms of the factorial function which you have to convert to the gamma function.

 

[gumi_kr]

Hi!

Big thanks! i will check it later but it looks correct ("you can do this because the terms from 0 to m+1 are equal to the terms from m+2 to 2m+2!" I'm not sure about it yet) It really took me a lot of time trying to solve it.
(as i thought changing this expresion /*with R_M^P)/ to
<br /> \sum_{p=0}^{M}\binom{2M+2}{p}(M+1-p)=?<br />

was making it simplier:) )
btw. the second part of the exercise was 'and give it's combinatorial idea', maybe you see that? (it's about the last form of thie equality with R_{m}^{p}...)

------------
My previous thoughts about this problem: (it coulde give you some hint about combinatorial explanation of that fact):1) I know that trying simply to count it - isn't the right way (even
using some advanced properties of binomial coefficient).2) It could be connected with Banach's modified matchbox problem, but
not neccessery (right side of the formula multiplied by 2^{n-1} is
expected number of matches..)

3) right sight looks like "choosing the leader and it's group" but i
cannot find connection with left side with this 'intuition'

5) It could be connected with properties of 'Bernoulli triangle' but i
couldn't find any materials about that.
(it's The number triangle (Sloane's A008949) composed of the partial
sums of binomial coefficients)

6) I couldn't find anything useful in "Advanced Combinatorics"
(Comtet) or Combinatorics 2nd R. Merris

 

[chaoseverlasting]

I actually don't know what youre talking about. If I had to I would guess its the total number of ways you could select r number of objects from a group of 2m+2 with unequal probability of selection. Dont know about the rest of it, but best of luck.

 

[gumi_kr]

"you can do this because the terms from 0 to m+1 are equal to the terms from m+2 to 2m+2, hence the sum on the right is twice the sum from 0 to m+1."

could you explain it to me. I know it's true before differentiating, but why after? (* well it's not true before differentiating ;), my mistake! this row of pascal triangle has odd number of elements* )

 

[Dick]

I think chaoseverlasting is wrong. It's not that simple. If you take your initial limit of M and move it up to 2M+2 then the sum is zero. Because the mystery parts cancel. Which is not useful. I like the approach of the "choosing a leader and it's group" for the RHS. But like you, I don't see the relation to the LHS. I'm mostly just checking in here so I hear if you've actually found the solution. I've spent way to much time thinking about this, and I still don't see it. Dammit. Everything you've said so far is very accurate.

 

[gumi_kr]

about chaoseverlasting idea:

We want to proove, that:
<br /> \sum_{p=0}^{M}\binom{2M+2}{p}(M+1-p)=(2M+1)\binom{2M}{M}<br />

1) Of course: (2M+1)\binom{2M}{m} = \frac{1}{2}(M+1)\binom{2M+2}{M+1}

So let's change it and multiple both sides by 2:
<br /> \sum_{p=0}^{M}\binom{2M+2}{p}(2M+2-2p)=(M+1)\binom{2M+2}{M+1}<br />

It's equal to :
<br /> \sum_{p=0}^{M}\binom{2M+2}{p}(2M+2-p) - \sum_{p=0}^{M}\binom{2M+2}{p}p=(M+1)\binom{2M+2}{M+1}<br />

and then:

<br /> \sum_{p=M+2}^{2M+2}\binom{2M+2}{p}p - \sum_{p=0}^{M+1}\binom{2M+2}{p}p=0<br />

final form:

<br /> \sum_{p=M+2}^{2M+2}\binom{2M+2}{p}p = \sum_{p=0}^{M+1}\binom{2M+2}{p}p<br />

So he may be right after all, but i do not know why this equality holds..

 

[gumi_kr]

Oh! Thats simple!

<br /> <br /> \sum_{p=M+2}^{2M+2}\binom{2M+2}{p}p = \sum_{p=0}^{M+1}\binom{2M+2}{p}p<br /> <br />We could create a simple bijection between this two sets. Let's simplify it:
We know that:

<br /> <br /> \binom{2M+2}{2M+2 -k}(2M+2-k) = \binom{2M+2}{k+1}(k+1)<br /> <br />

Why?:
1) choose a group of people with a leader
2) leave a leader and take all people that were not chosen
3) now you've got k people and a leader, so k+1 people with a leader
4) you've got the second set:)

do it for k=0,...M, and you've got the answer.

 

[chaoseverlasting]

I got the answer in factorials which you can convert to the Gamma Function.

Another way to check that statement, "you can do this because the terms from 0 to m+1 are equal to the terms from m+2 to 2m+2, hence the sum on the right is twice the sum from 0 to m+1", is that you take the binomial series, put x=-1 which gives you zero on the left side. The odd terms will be negative on the right and the even ones will be positive. This automatically gives you the result that the sum of even terms is equal to the sum of odd terms.

 

[gumi_kr]

Sorry if i misunderstood what you've written but I think you are trying to prove wrong equality.

Your proof is correct for {n\choose k} but we want to proove it for k{n\choose k}.btw1.Notice that because in our example n is even, we've got odd numbers of elements in this row of Pascal's triangle, so proof with odd and even elements is not correct - it works just for odd n) [ i mean that it simply implies value of the sum of half of the elements if a row of pascal's triangle]btw2. converting it to gamma function is indeed very simple. I wrote it just because it's simplier for 'calculations'.

 

[Dick]

Oh! Thats simple!

<br /> <br /> \sum_{p=M+2}^{2M+2}\binom{2M+2}{p}p = \sum_{p=0}^{M+1}\binom{2M+2}{p}p<br /> <br />We could create a simple bijection between this two sets. Let's simplify it:
We know that:

<br /> <br /> \binom{2M+2}{2M+2 -k}(2M+2-k) = \binom{2M+2}{k+1}(k+1)<br /> <br />

Why?:
1) choose a group of people with a leader
2) leave a leader and take all people that were not chosen
3) now you've got k people and a leader, so k+1 people with a leader
4) you've got the second set:)

do it for k=0,...M, and you've got the answer.

That's what I was missing alright! I'm still not quite sure I'm following the 'leader and followers' proof. But there's another way to see it. Both sides are just (2M+2)!/((2M+2-k-1)!*k!).

 

[gumi_kr]

i was too excited to write it properly ;)

1) choose a group of (2M+2-k) people (from 2M+2)
2) choose a leader between them (multiply B(2m+2,2M+2-k) by 2M+2-k)
3) keep a leader and 'give' rest of the people to him (number of people 2M+2 - (2M+2-k) = k)
3) now you've got k people and a leader, so (k+1) people with a leader
4) you've got the second set:)but you are right - you could simply count it, but 'leader and followers' proof gives you intuition - well at least it's how i came to the result.

 

[Dick]

Right. Got it now. Good job.

 

[chaoseverlasting]

Sorry if i misunderstood what you've written but I think you are trying to prove wrong equality.

Your proof is correct for {n\choose k} but we want to proove it for k{n\choose k}.


btw1.Notice that because in our example n is even, we've got odd numbers of elements in this row of Pascal's triangle, so proof with odd and even elements is not correct - it works just for odd n) [ i mean that it simply implies value of the sum of half of the elements if a row of pascal's triangle]


btw2. converting it to gamma function is indeed very simple. I wrote it just because it's simplier for 'calculations'.

Yes youre right. I proved the wrong property. I meant to give you the proof for k{n\choose k} but I was in a rush last night . Anyway, merry christmas.