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.
Best Answer
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}