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!

  • $\begingroup$ Did they solve similar problems? $\endgroup$ – Mhenni Benghorbal Sep 3 '14 at 0:45
  • $\begingroup$ Do you think the answers can also be used here...? $\endgroup$ – 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 .......$$

  • $\begingroup$ Oh, of course! I can identify that now as the n-th coefficient of a product of formal power series (namely exp(x+x²/2) and exp(-x)). Thank you, that's a good hint. $\endgroup$ – Fimpellizieri Sep 3 '14 at 1:05

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

  • $\begingroup$ Do you think the answer can also be used here...? $\endgroup$ – draks ... Apr 24 '17 at 20:25

Here is your $f(n)$

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

Related problems.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for?Browse other questions tagged or ask your own question.