Equality of sums 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.
 A: 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.
A: 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.
A: $$
\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}$
A: 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.
