Combinatorial proof or interpretation of Bezout relation between $(1-p)^n$ and $p^m$?

53 Views Asked by At

Let $T_{n,m}(p)=\sum_{j=0}^{m-1} \binom{n+j-1}{j}p^j$. In answering a recent question, I discovered the identity

$$ (1-p)^n T_{n,m}(p)+ p^m T_{m,n}(1-p)=1 \tag{1} $$

Is there a nice combinatorial proof or interpretation of (1) ? ($p$ looks a lot like the probablity of something in this formula, doesn't it.) I've got a feeling that this question is a duplicate of an already existing question, but my search was unsuccessful.

UPDATE : as explained in orangeskid's answer to the abovelinked question, (1) can be nicely derived by expanding Newton's binomial in $(p+(1-p))^{n+m-1}=1$. But this is still more computational than really combinatoric/probabilistic, I'm still waiting for a more direct interpretation of $T_{n,m}(p)$ and (1).

1

There are 1 best solutions below

2
On BEST ANSWER

If we take $p$ as the probability of success of a sequence of i.i.d. Bernoulli trials, then

$$ (1 - p)^nT_{n, m}(p) = \sum_{j=0}^{m-1} \binom {n + j - 1} {j}p^j(1-p)^n$$

is the probability that having less than $m$ successes before the $n$-th failures. Similarly,

$$ p^mT_{m, n}(1 - p) = \sum_{j=0}^{n-1} \binom {m + j - 1} {j}(1-p)^jp^m$$

is the probability that having less than $n$ failures before the $m$-th successes.

These two are complementary events - you either reach the $m$-th success first, or the $n$-th failure first, and you cannot have them together in the same trial. So their probabilities sum up to $1$.

P.S. These are well known negative binomial CDFs.