# Exponential generating function problem involving product formula

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.

## 2 Answers

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.

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.

• Why are the last two lines so complicated? You could just directly apply the binomial theorem for $(1+x)-(1+y)$ to get $(x-y)^n$? – joriki Jan 12 '20 at 21:37
• @joriki You are correct & it would indeed be easier. But that's the way I calculated it. – Donald Splutterwit Jan 12 '20 at 21:39
• Ah, now I see what you did. Interesting. – joriki Jan 12 '20 at 21:41