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

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.

• For $n\neq p,$ every $k$ has to be replaced by $p$ here $(-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}.$ Jun 11 at 18:58

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}

• Thank you very much!
– Sigi
Jun 11 at 22:12
• what did you do in this step $\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\\$?
– Sigi
Jun 12 at 2:07
• Did you use here the cauchy product?
– Sigi
Jun 12 at 2:10
• I just interchange the two sums. Jun 12 at 3:20

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.

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}