# Evaluate the sum $\sum_{i=0}^{n} (-1)^{n-i} \binom{n}{i} f(i)$

I need to evaluate the following sum, which depends on $n \in \mathbb N$ (call it $S(n)$ if you will)

$$\sum_{i=0}^{n} (-1)^{n-i} \binom{n}{i} f(i)$$

where $f$ defined over $\mathbb N$ is determined by the identity

$$\sum_{n \geq 0} f(n) \frac{x^n}{n!} = exp \left ( x+\frac{x^2}{2} \right)$$

This is a problem left as an exercise to the reader in Richard Stanley’s “Enumerative Combinatorics”, in the first few pages of Chapter 1, and I assume it should be simple but none of my approaches, including searching for identities involving binomial coefficients, have worked.

#### Solutions Collecting From Web of "Evaluate the sum $\sum_{i=0}^{n} (-1)^{n-i} \binom{n}{i} f(i)$"

Hint: $$\left(\displaystyle \sum_{l \geq 0} f(l) \frac{x^l}{l!}\right).\left(\sum_{m \geq 0} (-1)^m \frac{x^m}{m!} \right) = \quad …….$$

Setting
$$S_n=\sum_{i=0}^n(-1)^{n-i}{n\choose i}f(i),$$
we have
\begin{eqnarray}
\exp\left(\frac{x^2}{2}\right)&=&\exp\left(x+\frac{x^2}{2}\right)\exp(-x)
=
\left(\sum_{n=0}^\infty\frac{f(n)}{n!}x^n\right)\left(\sum_{n=0}^\infty\frac{(-1)^n}{n!}x^n\right)\\
&=&\sum_{n=0}^\infty\left(\sum_{i=0}^n\frac{f(i)}{i!}\cdot\frac{(-1)^{n-i}}{(n-i)!}\right)x^n
=\sum_{n=0}^\infty\left(\frac{1}{n!}\sum_{i=0}^n(-1)^{n-i}{n\choose i}f(i)\right)x^n\\
&=&\sum_{n=0}^\infty\frac{S_n}{n!}x^n,
\end{eqnarray}
i.e.
$$\sum_{n=0}^\infty\frac{S_n}{n!}x^n=\exp\left(\frac{x^2}{2}\right)=\sum_{n=0}^\infty\frac{1}{n!}\left(\frac{x^2}{2}\right)^n=\sum_{n=0}^\infty\frac{x^{2n}}{2^nn!}.$$
It follows that
$$S_{2n+1}=0,\ S_{2n}=\frac{(2n)!}{2^nn!} \quad \forall n\ge 0.$$

Here is your $f(n)$

$$f(n) = n!\sum_{k=0}^{\lfloor n/2 \rfloor}\frac{2^{-k}}{ (n-2k)!\,k! }.$$

Related problems.