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

Question

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.

Thank you in advance!

Answer 1

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 .......$$

Answer 2

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. $$

Answer 3

Here is your $f(n)$

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

Related problems.