A combinatorial sum involving binomial coefficients

Question

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.

Answer 1

$$\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}$$

Answer 2

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.

Answer 3

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}.$$