Equality of sums

Question

How does one show that $$\sum_{j=k}^n\binom{j-1}{k-1}q^{j-k}=\sum_{j=k}^n\binom{n}{j}p^{j-k}q^{n-j},$$ where $p+q=1$? I suppose one needs to substitute $p=1-q$ on the right side and then use the binomial theorem, but it gets messy and I cannot get it done.

Answer 1

$$ \begin{align} \sum_{j=k}^n\binom{n}{j}(1-q)^{j-k}q^{n-j} &=\sum_{j=k}^n\sum_{i=0}^{j-k}\binom{n}{j}\binom{j-k}{i}(-q)^{j-k-i}q^{n-j}\tag{1}\\ &=\sum_{j=k}^n\sum_{i=0}^{j-k}\binom{n}{j}\binom{j-k}{i}(-1)^{j-k-i}q^{n-k-i}\tag{2}\\ &=\sum_{j=k}^n\sum_{i=k}^j\binom{n}{j}\binom{j-k}{i-k}(-1)^{j-i}q^{n-i}\tag{3}\\ &=\sum_{j=k}^n\sum_{i=k}^j\binom{n}{j}\binom{j-k}{j-i}(-1)^{j-i}q^{n-i}\tag{4}\\ &=\sum_{i=k}^n\sum_{j=i}^n\binom{n}{n-j}\binom{k-i-1}{j-i}q^{n-i}\tag{5}\\ &=\sum_{i=k}^n\binom{n+k-i-1}{n-i}q^{n-i}\tag{6}\\ &=\sum_{i=k}^n\binom{i-1}{i-k}q^{i-k}\tag{7}\\ &=\sum_{i=k}^n\binom{i-1}{k-1}q^{i-k}\tag{8} \end{align} $$ Explanation:
$(1)$: expand $(1-q)^{j-k}$ using the Binomial Theorem
$(2)$: separate powers of $-1$ and $q$
$(3)$: substitute $i\mapsto i-k$
$(4)$: $\binom{j-k}{i-k}=\binom{j-k}{j-i}$
$(5)$: $\binom{n}{j}=\binom{n}{n-j}$ and $\binom{j-k}{j-i}(-1)^{j-i}=\binom{k-i-1}{j-i}$
$(6)$: Vandermonde's Identity
$(7)$: substitute $i\mapsto n+k-i$
$(8)$: $\binom{i-1}{i-k}=\binom{i-1}{k-1}$

Answer 2

It follows from summation by parts and the identity: $$ \sum_{n=k}^{N}\binom{n}{k}=\binom{N+1}{k+1}$$ that is straightforward to prove by induction.

Answer 3

Using complex variables we have the following result.

Suppose we are trying to compare (LHS) $$\sum_{j=k}^n {j-1\choose k-1} q^{j-k}$$ and (RHS) $$\sum_{j=k}^n {n\choose j} (1-q)^{j-k} q^{n-j}.$$

Introduce the integral representation $${j-1\choose k-1} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^k} (1+z)^{j-1} \; dz.$$

This gives for the LHS $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1+z)z^k q^k} \sum_{j=k}^n (1+z)^{j} q^j \; dz$$

Simplify to obtain for the LHS $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1+z)z^k q^k} \frac{(1+z)^{n+1} q^{n+1} - (1+z)^k q^k}{(1+z)q-1} \; dz$$ or $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1+z)z^k q^k} \frac{(1+z)^{n+1} q^{n+1} - (1+z)^k q^k}{q-1+zq} \; dz$$

There are two pieces call them $A_1$ and $A_2$ given by $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1+z)z^k q^k} \frac{(1+z)^{n+1} q^{n+1}}{q-1+zq} \; dz$$ and $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{(1+z)z^k q^k} \frac{(1+z)^k q^k}{q-1+zq} \; dz.$$

We evaluate these with the substitution $z=1/w$ to get for $A_1$ $$\frac{1}{2\pi i} \int_{|w|=R} \frac{1}{(1+1/w) q^k /w^k} \frac{(1+1/w)^{n+1} q^{n+1}}{q-1+q/w} \; \frac{dw}{w^2} \\ = \frac{1}{2\pi i} \int_{|w|=R} \frac{1}{(1+1/w) q^k w^{n+1-k}} \frac{(1+w)^{n+1} q^{n+1}}{q-1+q/w} \; \frac{dw}{w^2} \\ = \frac{1}{2\pi i} \int_{|w|=R} \frac{1}{(1+w) q^k w^{n+1-k}} \frac{(1+w)^{n+1} q^{n+1}}{w(q-1)+q} \; dw \\ = q^{n+1-k} \frac{1}{2\pi i} \int_{|w|=R} \frac{1}{w^{n+1-k}} \frac{(1+w)^{n}}{w(q-1)+q} \; dw \\ = q^{n-k} \frac{1}{2\pi i} \int_{|w|=R} \frac{1}{w^{n+1-k}} \frac{(1+w)^{n}}{w(q-1)/q+1} \; dw.$$

There are two contributions here from the poles at $w=q/(1-q)$ and at $w=0.$ The first one can be extracted from $$\frac{q^{n-k+1}}{q-1} \frac{1}{2\pi i} \int_{|w|=R} \frac{1}{w^{n+1-k}} \frac{(1+w)^{n}}{w+q/(q-1)} \; dw$$ to get $$\frac{q^{n-k+1}}{q-1} \frac{(1-q)^{n+1-k}}{q^{n+1-k}} \frac{1}{(1-q)^n} = -\frac{1}{(1-q)^k}.$$

The second contribution is $$q^{n-k} \sum_{m=0}^{n-k} {n\choose n-k-m} \frac{(1-q)^m}{q^m} = q^{n-k} \sum_{m=0}^{n-k} {n\choose m+k} \frac{(1-q)^m}{q^m} \\ = q^{n-k} \sum_{m=k}^{n} {n\choose m} \frac{(1-q)^{m-k}}{q^{m-k}} = \sum_{m=k}^{n} {n\choose m} (1-q)^{m-k} q^{n-m}.$$

We get for $A_2$ $$\frac{1}{2\pi i} \int_{|w|=R} \frac{1}{(1+1/w) q^k /w^k} \frac{(1+1/w)^{k} q^{k}}{q-1+q/w} \; \frac{dw}{w^2} \\ = \frac{1}{2\pi i} \int_{|w|=R} \frac{1}{(1+w) q^k /w^k} \frac{(1+1/w)^{k} q^{k}}{w(q-1)+q} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=R} \frac{1}{(1+w) q^k} \frac{(1+w)^{k} q^{k}}{w(q-1)+q} \; dw \\ = \frac{1}{2\pi i} \int_{|w|=R} \frac{(1+w)^{k-1}}{w(q-1)+q} \; dw \\ = \frac{1}{q-1} \frac{1}{2\pi i} \int_{|w|=R} \frac{(1+w)^{k-1}}{w+q/(q-1)} \; dw.$$

This has no pole at zero and a pole at $w=q/(1-q)$ which contributes $$\frac{1}{q-1} \frac{1}{(1-q)^{k-1}} = - \frac{1}{(1-q)^{k}}.$$

Subtracting the contribution from $A_2$ from the one for $A_1$ we finally obtain $$\sum_{m=k}^{n} {n\choose m} (1-q)^{m-k} q^{n-m} - \frac{1}{(1-q)^{k}} - \left(-\frac{1}{(1-q)^{k}}\right) \\ = \sum_{m=k}^{n} {n\choose m} (1-q)^{m-k} q^{n-m}$$ which is precisely the result we were trying to prove, QED.

Answer 4

Let's rewrite your identity slightly:

$$ \sum_{j=k}^n \binom{j-1}{k-1} p^k q^{j-k} = \sum_{j=k}^n \binom{n}{j} p^j q^{n-j}. $$

Imagine $n$ coins are tossed, each coin coming up heads with probability $p$. The right-hand side is the probability that at least $k$ coins came up heads. Each summand on the left-hand side is the probability that the $k$th head was on the $j$th toss; if there were at least $k$ heads, then such a $j$ must exist and is unique.