Combinatorial identity: $\sum_{i=0}^{k}\binom{n}{i}p^{i}q^{n-i}+ \sum_{i=k}^{n-1}\binom{i}{k}p^{k+1}q^{i-k}=1$.

Question

While answering a recent question I came across an unexpected identity:

$$ \sum_{i=0}^{k}\binom{n}{i}p^{i}q^{n-i}+ \sum_{i=k}^{n-1}\binom{i}{k}p^{k+1}q^{i-k}=1.\tag1 $$ valid provided that $p+q=1$.

The identity (1) can be also written as: $$ \sum_{i=k}^{n}\binom{n}{i}p^{i}q^{n-i-1}=\sum_{i=k}^{n}\binom{i-1}{k-1} p^{k}q^{i-k}.\tag2 $$

Is there a simple combinatorial (probabilistic) explanation of the result for $k<n$?

Answer 1

Let's assume $0<k<n$, and let me rearrange a bit. We have

$$\sum_{i=0}^{k}\binom{n}{i} p^{i} q^{n-i} +p \sum_{i=k}^{n-1}\binom{i}{k} p^{k} q^{i-k}=1\tag1$$

Let $X$ be a Binomial$(n,p)$ random variable, which we can regard as the sum (count) of $n$ Bernoulli$(p)$ rv $X=Y_0+Y_1 +\cdots Y_{n-1}$

The first term cleary corresponds to $P(X\le k)$.

Now, to compute $P(X > k)$ , let's denote by $i$ the index of the $k+1$-th success ($Y_i=1$, $\sum_{j=0}^{i} Y_j=k+1$). Then

$$P(X>k) = \sum_{i=k}^{n-1} \binom{i}{k} p^k q^{i-k} p $$