A combinatorial sum involving binomial coefficients Let $p \in (0,1)$, let $n \in \mathbb{N}$ and let $0 \leq k \leq n$. Is it true that
$$
\sum_{j=0}^n p^j {n \choose j}{j \choose n-k}(-1)^{j-(n-k)} = {n \choose k}p^{n-k}(1-p)^{k}?
$$
Thanks.
 A: $$\begin{align}
\sum_{j=0}^n\color{green}{p^j}\color{blue}{\binom nj\binom j{n-k}}(-1)^{j-(n-k)}
&=\color{green}{p^{n-k}}\sum_{j=0}^n \color{green}{p^{j-(n-k)}}\color{blue}{\binom n{n-k}\binom {k}{j-(n-k)}}(-1)^{j-(n-k)}\\
&=p^{n-k}\sum_{j=0}^n \color{purple}{p^{j-(n-k)}}\color{orange}{\binom n{k}}\binom {k}{j-(n-k)}\color{purple}{(-1)^{j-(n-k)}}\\
&=\color{orange}{\binom nk} p^{n-k}\sum_{j=n-k}^n \binom {k}{j-(n-k)}\color{purple}{(-p)^{j-(n-k)}}\\
&=\binom nk p^{n-k}\sum_{r=0}^{k}\binom kr(-p)^r\qquad\qquad (r=j-(n-k))\\
&=\binom nk p^{n-k}(1-p)^k\quad\blacksquare
\end{align}$$
A: Since
$$\binom{n}{j} \binom{j}{n-k} = \begin{cases}
\binom{n}{n-k} &\text{if } n-k \leq j \leq n\\
0 &\text{otherwise}\end{cases},$$
the left hand side can be simplified to
$$\binom{n}{n-k} \sum_{j=n-k}^{n} {p^j (-1)^{j-(n-k)}}.$$
As $\binom{n}{n-k} = \binom{n}{k}$ matches, it remains to compare the sum
$$\sum_{j=n-k}^{n} p^j (-1)^{j-(n-k)} = \sum_{i=0}^{k} p^{(n-k) + i} (-1)^i = p^{n-k} (-1)^k \underbrace{\sum_{i=0}^{k} p^{i} (-1)^{k-i}}_{(p-1)^k} = p^{n-k} (1-p)^k$$
by binomial theorem. So your formula is correct.
A: Suppose we seek to simplify
$$\sum_{j=0}^n p^j {n\choose j}
{j\choose n-k} (-1)^{j-(n-k)}$$
where $0\le k \le n.$
Introduce
$${j\choose n-k} =
\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{n-k+1}} (1+z)^j \; dz.$$
This yields for the sum
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{n-k+1}} (-1)^{n-k}
\sum_{j=0}^n {n\choose j} (-1)^j p^j (1+z)^j
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{n-k+1}} (-1)^{n-k}
(1-p(1+z))^n
\; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon}
\frac{1}{z^{n-k+1}} (-1)^{n-k}
(1-p-pz)^n
\; dz.$$
Extracting coefficients we get
$$(-1)^{n-k} {n\choose n-k} (1-p)^k (-1)^{n-k}p^{n-k}
= {n\choose k} (1-p)^k p^{n-k}.$$
