How to prove $\sum_{k=p}^n (-1)^k\binom{n}{k}\binom{k}{p} = (-1)^p$ by using generating functions

Question

I am learning about generating functions and I tried to prove some identity using it:

$\sum_{k=p}^n (-1)^k\binom{n}{k}\binom{k}{p} = (-1)^p$ for $n=p$ and $=0$ for else.

Let $n =p$, then I don't even need the generating function to see the equality we have $(-1)^n \binom{n}{n} \binom{n}{n}=(-1)^n$ on the LHs and $(-1)^p=(-1)^n$ on the RHS

Let $n \neq p$ The generating function of the LHS would be $(-1)^k\binom{n}{k}\binom{k}{k} + (-1)^{k+1}\binom{n}{k+1}\binom{k+1}{k}x+...+(-1)^n\binom{n}{n}\binom{n}{n}x^{n-1}$

The generating function on the RHS would be $0+0x+0x^2+...$

Here is my first problem, obviously $(-1)^k \binom{n}{k} \neq 0$ so it seems like that I have misunderstood something. Could someone please explain where my mistake is.

Answer 1

It is well known that,

$$\sum_{m=r}^{\infty} \binom{m}{r}x^m = \frac{x^r}{(1-x)^{r+1}}$$

Let $a_{n, p} = \sum_{k=p}^n (-1)^k \binom{n}{k}\binom{k}{p}$ and

\begin{align} F(x) &= \sum_{n=p}^{\infty} a_{n, p} x^n\\ &= \sum_{n=p}^{\infty}\sum_{k=p}^{n} (-1)^k \binom{n}{k}\binom{k}{p} x^n\\ &= \sum_{k=p}^{\infty}(-1)^k \binom{k}{p}\sum_{n=k}^{\infty} \binom{n}{k} x^n\\ &= \sum_{k=p}^{\infty}(-1)^k \binom{k}{p} \frac{x^k}{(1-x)^{k+1}}\\ &= \frac1{1-x}\sum_{k=p}^{\infty}\binom{k}{p}\left(-\frac{x}{1-x}\right)^k\\ &= \frac1{1-x}\left(\frac{\left(-\frac{x}{1-x}\right)^p}{\left(1+\frac{x}{1-x}\right)^{p+1}}\right)\\ &= (-1)^p x^p \end{align}

Answer 2

Set $a_n = (-1)^{n-p}/(n-p)!$ for $n \ge p$, $a_n=0$ for $0 \le n \le p-1$, and $b_n = 1/n!$ for every $n \ge 0$. Then $$\sum_{k=p}^n (-1)^k \binom{n}{k}\binom{k}{p} = \sum_{k=p}^n (-1)^k \frac{n!}{(n-k)!(k-p)!p!} = (-1)^p\frac{n!}{p!} \sum_{k=0}^n a_kb_{n-k}.$$ The last sum is the coefficient of $z^n$ in the power series $$\Big(\sum_{k=0}^\infty a_kz^k\Big)\Big(\sum_{\ell=0}^\infty b_\ell z^\ell\Big) = (z^pe^{-z})e^{z}= z^p.$$ Hence, the sum to be computed is $(-1)^p$ if $n=p$, and $0$ otherwise.

Answer 3

I would rely on the binomial indentity $(1+x)^n=\sum\limits_k \binom{n}{k} x^k$ instead of $\frac{x^k}{(1-x)^{k+1}}=\sum\limits_n \binom{n}{k} x^n$:

$$\begin{align} \sum\limits_k (-1)^k \binom{n}{k} \binom{k}{p} &= \sum\limits_k (-1)^k \binom{n}{k} [x^p](1+x)^k \\&= [x^p] \sum\limits_k \binom{n}{k} (-1)^k(1+x)^k \\&= [x^p](1-(1+x))^n = [x^p](-x)^n. \end{align}$$