Exponential generating function problem involving product formula

Question

For any integer $n\geq0$, let

$f_n=$ $\sum_{k=0}^∞$${n}\choose{k}$${k}\choose{r}$$(-1)^{n-k}$${n-k}\choose{r}$

How do I show that $f_{2r}=(-1)^{r}$${2r}\choose{r}$ and $f_n=0$ if $n\ne2r$?

The only hint I was given was to apply the product formula to calculate the exponential generating function of the sequence $\{f_n\}$, but I am also struggling with this.

Any help would be greatly appreciated, thank you.

Answer 1

I think this is what the question is looking for. Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that

$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$

Therefore with

$$F(z) = \sum_{n\ge 0} \frac{z^n}{n!} \sum_{k=0}^n {n\choose k} {k\choose r} (-1)^{n-k} {n-k\choose r}$$

we have $$F(z) = A(z) B(z)$$ where

$$A(z) = \sum_{n\ge 0} {n\choose r} \frac{z^n}{n!} \quad\text{and}\quad B(z) = \sum_{n\ge 0} {n\choose r} (-1)^r \frac{z^n}{n!}.$$

We get for $A(z)$

$$A(z) = \sum_{n\ge r} {n\choose r} \frac{z^n}{n!} = \frac{1}{r!} \sum_{n\ge r} \frac{1}{(n-r)!} z^n \\ = \frac{z^r}{r!} \sum_{n\ge 0} \frac{1}{n!} z^n = \frac{z^r}{r!} \exp(z).$$

and for $B(z)$

$$B(z) = \sum_{n\ge r} {n\choose r} (-1)^n \frac{z^n}{n!} = \frac{(-1)^r}{r!} \sum_{n\ge r} \frac{(-1)^{n-r}}{(n-r)!} z^n \\ = (-1)^r \frac{z^r}{r!} \sum_{n\ge 0} \frac{(-1)^n}{n!} z^n = (-1)^r \frac{z^r}{r!} \exp(-z).$$

It follows that

$$F(z) = \frac{z^r}{r!} \exp(z) (-1)^r \frac{z^r}{r!} \exp(-z) = (-1)^r \frac{z^{2r}}{r!\times r!}.$$

Therefore

$$f_n = n! [z^n] F(z) = n! [z^n] (-1)^r \frac{z^{2r}}{r!\times r!} \\ = [[n=2r]] n! (-1)^r \frac{1}{r!\times r!} = [[n=2r]] (-1)^r \times {2r\choose r}.$$

This is the claim.

Answer 2

Using the coefficient extractor thingy, Eg. \begin{eqnarray*} \binom{k}{r} = [x^r]: (1+x)^k. \end{eqnarray*} We have \begin{eqnarray*} f_n &=& \sum_{k} (-1)^{n-k} \binom{n}{k} \binom{k}{r} \binom{n-k}{r} \\ &=& [x^r] [ y^r] : \sum_{k} (-1)^{n-k} \binom{n}{k}(1+x)^{k} (1+y)^{n-k} \\ &=& [x^r] [ y^r] : (-1)^{n} (1+y)^{n} \left( 1-\frac{1+x}{1+y} \right)^n \\ &=& [x^r] [ y^r] : (-1)^{n} (y-x)^{n} \\ \end{eqnarray*} And the only way to get a $x^ry^r$ term is if $n=2r$, the result follows.