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

Thank you in advance!

• Did they solve similar problems? – Mhenni Benghorbal Sep 3 '14 at 0:45
• Do you think the answers can also be used here...? – draks ... Apr 24 '17 at 20:23

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