Combinatorics/Probability problem.

[gumi_kr]

Homework Statement

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}

and give it's combinatorical idea.

I'm trying to solve this for 3 days - please help..

 

[Diffy]

What do you have so far? What have you tried?

 

[gumi_kr]

It was an usual exercise in probability theory course. It looks easy
but I'm trying to solve this for a long time without success.

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'

4) typing R^{M}_{P} with Gamma and hypergeometric function is not a
good option - too many calculations

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
---
well, i can show you some easy calculations (but i don't think that it makes the problem easier):
\sum_{q=0}^{M}R^{M}_{q}\cdot R^{M}_{M-q}= \sum_{q=0}^{M}R^{M}_{q}\cdot (2^{M+1} - R_{q}^{M}) = 2^{M+1}\cdot \sum_{q=0}^{M}(M+1-q)\cdot {M+1 \choose q} - \sum_{q=0}^{M} (R^{M}_{q})^{2} = 2^{M+1}\cdot \sum_{q=0}^{M+1}q\cdot {M+1 \choose q} - \sum_{q=0}^{M} (R^{M}_{q})^{2} =
=2^{2M+1}\cdot (M+1) - \sum_{q=0}^{M} (R^{M}_{q})^{2}

On the other hand: (Banach's matchbox problem and it's expecting value):
(2M+1)\cdot {2M \choose M} = 2^{2M} + \sum_{q=0}^{M} q\cdot {2M-q \choose M}\cdot 2^{q}

 

[Avodyne]

Well, I took a look and couldn't get any farther than you did, sorry! Definitely does not look easy ...