Prove $\sum_{k=i}^{n} {k-1 \choose i-1} p^i (1-p)^{k-i} = \sum_{k=i}^{n} {n \choose k} p^k (1-p)^{n-k}$

Question

Prove that the following two summations are equal for any positive integers $i\leq n$, and any real number $p$ between $0$ and $1$:

$$ \sum_{k=i}^{n} {k-1 \choose i-1} p^i (1-p)^{k-i} = \sum_{k=i}^{n} {n \choose k} p^k (1-p)^{n-k} $$

I know the equation is originated from Binomial distribution and its insight. That is, $$ P\{X(i,p) > n\} = P\{B(n,p) < i\}, $$ which implies $$ 1 - \sum_{k=i}^{n} {k-1 \choose i-1} p^i (1-p)^{k-i} = \sum_{k=0}^{i-1} {n \choose k} p^k (1-p)^{n-k}. $$

But I do not know how to prove it mathematically using some transformations in combinatorics.

Answer 1

We show the identity \begin{align*} \color{blue}{\sum_{k=i}^{n} \binom{k-1}{i-1} p^i (1-p)^{k-i} = \sum_{k=i}^{n} \binom{n}{k}p^k (1-p)^{n-k}}\tag{1} \end{align*} is valid. We consider (1) as equality of polynomials of order $i$ and degree $n$ in the variable $p$. It is therefore sufficient to show equality of coefficients $[p^q], i\leq q\leq n$.

We use the coefficient of operator $[z^q]$ to denote the coefficient of series in $z$. We can write this way \begin{align*} [z^q](1+z)^n=\binom{n}{q}\tag{2} \end{align*}

Coefficient left part: We obtain for $i\leq q\leq n$: \begin{align*} \color{blue}{[p^q]}&\color{blue}{\sum_{k=i}^n\binom{k-1}{i-1}p^i(1-p)^{k-i}}\\ &=\sum_{k=i}^{n}\binom{k-1}{i-1}[p^{q-i}](1-p)^{k-i}\tag{3}\\ &=\sum_{k=q}^n\binom{k-1}{i-1}\binom{k-i}{q-i}(-1)^{q-i}\tag{4}\\ &=(-1)^{q-i}\binom{q-1}{i-1}\sum_{k=q}^n\binom{k-1}{k-q}\tag{5}\\ &=(-1)^{q-i}\binom{q-1}{i-1}\sum_{k=0}^{n-q}\binom{k+q-1}{q-1}\tag{6}\\ &=(-1)^{q-i}\binom{q-1}{i-1}\sum_{k=0}^{n-q}[z^{q-1}](1+z)^{k+q-1}\tag{7}\\ &=(-1)^{q-i}\binom{q-1}{i-1}[z^{q-1}](1+z)^{q-1}\sum_{k=0}^{n-q}(1+z)^k\\ &=(-1)^{q-i}\binom{q-1}{i-1}[z^{q-1}](1+z)^{q-1}\left(\frac{(1+z)^{n-q+1}-1}{(1+z)-1}\right)\tag{8}\\ &=(-1)^{q-i}\binom{q-1}{i-1}[z^{q}](1+z)^n\\ &\,\,\color{blue}{=(-1)^{q-i}\binom{q-1}{i-1}\binom{n}{q}}\tag{9} \end{align*}

Comment:

• In (3) we apply the rule $[p^{a-b}]A(p)=[p^a]p^bA(p)$.

• In (4) we select the coefficient of $[p^{q-i}]$ according to (2). Note the sum starts with $k=q$ since smaller indices do not contribute due to the factor $\binom{k-1}{k-q}$.

• In (5) we use the binomial identity \begin{align*} \binom{k-1}{i-1}\binom{k-i}{q-i}=\frac{(k-1)!}{(i-1)!(k-i)!}\,\frac{(k-i)!}{(q-i)!(k-q)!}=\binom{q-1}{i-1}\binom{k-1}{k-q} \end{align*}

• In (6) we shift the index and start with $k=0$. We also use $\binom{n}{k}=\binom{n}{n-k}$.

• In (7) we apply (2) again and do some rearrangements in the next step.

• In (8) we use the finite geometric series formula and observe that only the left term in parenthesis contributes to $[z^{q-1}]$.

Coefficient right part: We obtain similarly as above for $i\leq q\leq n$: \begin{align*} \color{blue}{[p^q]}&\color{blue}{\sum_{k=i}^n\binom{n}{k}p^k(1-p)^{n-k}}\\ &=\sum_{k=i}^q\binom{n}{k}[p^{q-k}](1-p)^{n-k}\\ &=\sum_{k=i}^q\binom{n}{k}\binom{n-k}{q-k}(-1)^{q-k}\\ &=\binom{n}{q}\sum_{k=i}^{q}\binom{q}{k}(-1)^{q-k}\\ &=(-1)^q\binom{n}{q}\sum_{k=0}^{q-i}\binom{q}{q-k-i}(-1)^{k+i}\\ &=(-1)^{q-i}\binom{n}{q}\sum_{k=0}^{q-i}[z^{q-k-i}](1+z)^q(-1)^{k}\\ &=(-1)^{q-i}\binom{n}{q}[z^{q-i}](1+z)^ q\sum_{k=0}^{q-i}(-z)^k\\ &=(-1)^{q-i}\binom{n}{q}[z^{q-i}](1+z)^q\frac{1-(-z)^{q-i+1}}{1-(-z)}\\ &=(-1)^{q-i}\binom{n}{q}[z^{q-i}](1+z)^{q-1}\\ &=(-1)^{q-i}\binom{n}{q}\binom{q-1}{q-i}\\ &\,\,\color{blue}{=(-1)^{q-i}\binom{n}{q}\binom{q-1}{i-1}}\tag{10} \end{align*}

Since (9) and (10) are equal the claim (1) follows.

Answer 2

We seek to prove that with $1\le q\le n$ and $0\le p\le 1$ that

$$\sum_{k=q}^n {k-1\choose q-1} p^q (1-p)^{k-q} = \sum_{k=q}^n {n\choose k} p^k (1-p)^{n-k}.$$

We start on the LHS with

$$p^q \sum_{k=0}^{n-q} {k+q-1\choose q-1} (1-p)^k \\ = p^q [z^{n-q}] \frac {1}{1-z} \sum_{k\ge 0} {k+q-1\choose q-1} (1-p)^k z^k \\ = p^q [z^{n-q}] \frac {1}{1-z} \frac{1}{(1-(1-p)z)^q}.$$

This is

$$(-1)^q \frac{p^q}{(1-p)^q} \; \underset{z}{\mathrm{res}} \; \frac{1}{z^{n-q+1}} \frac{1}{1-z} \frac{1}{(z-1/(1-p))^q}.$$

Now residues sum to zero and the residue at infinity is zero so this is minus the residue at $z=1$ plus minus the residue at $z=1/(1-p).$ The former is one by inspection. For the latter we need the Leibniz rule:

$$\frac{1}{(q-1)!} \left(\frac{1}{z^{n-q+1}} \frac{1}{1-z}\right)^{(q-1)} \\ = \frac{1}{(q-1)!} \sum_{k=0}^{q-1} {q-1\choose k} \frac{(-1)^k}{z^{n-q+1+k}} (n-q+1)^{\overline{k}} \frac{1}{(1-z)^{1+q-1-k}} 1^{\overline{q-1-k}} \\ = \frac{1}{(q-1)!} \sum_{k=0}^{q-1} {q-1\choose k} \frac{(-1)^k}{z^{n-q+1+k}} {n-q+k\choose k} k! \frac{1}{(1-z)^{q-k}} (q-1-k)! \\ = \sum_{k=0}^{q-1} \frac{(-1)^k}{z^{n-q+1+k}} {n-q+k\choose k} \frac{1}{(1-z)^{q-k}}.$$

Evaluate at $z=1/(1-p)$ to get

$$\sum_{k=0}^{q-1} (-1)^k (1-p)^{n-q+1+k} {n-q+k\choose k} \frac{(1-p)^{q-k}}{(-1)^{q-k} p^{q-k}}.$$

Collecting the two contributions we find

$$1 - (1-p)^{n-(q-1)} \sum_{k=0}^{q-1} {n-q+k\choose k} p^k \\ = 1 - (1-p)^{n-(q-1)} [z^{q-1}] \frac{1}{1-z} \sum_{k\ge 0} {n-q+k\choose k} p^k z^k \\ = 1 - (1-p)^{n-(q-1)} [z^{q-1}] \frac{1}{1-z} \frac{1}{(1-pz)^{n-q+1}}$$

On the other hand we get for the RHS

$$1 - \sum_{k=0}^{q-1} {n\choose k} p^k (1-p)^{n-k}$$

so we need to show that the coefficient extractor term is equal to the sum, which yields

$$[z^{q-1}] \frac{1}{1-z} \sum_{k\ge 0} {n\choose k} p^k (1-p)^{n-k} z^k = \; \underset{z}{\mathrm{res}} \; \frac{1}{z^q} \frac{1}{1-z} (pz+1-p)^n.$$

Now put $z/(pz+1-p) = w$ so that $z = (1-p) w / (1 - pw)$ and $dz = (1-p)/(1-pw)^2 \; dw$ as well as $pz+1-p = (1-p) / (1-pw)$ to obtain

$$\; \underset{w}{\mathrm{res}} \; \frac{1}{w^q} \frac{1-pw}{1-w} \frac{(1-p)^{n-q}}{(1-pw)^{n-q}} \frac{1-p}{(1-pw)^2} \\ = (1-p)^{n-(q-1)} \; \underset{w}{\mathrm{res}} \; \frac{1}{w^q} \frac{1}{1-w} \frac{1}{(1-pw)^{n-q+1}}.$$

This is the claim.