Suppose you have a formula $$ \sum_{n\geq 0}f(n)\frac{x^n}{n!}=\exp\left(x+\frac{x^2}{2}\right). $$

There is a recurrence for $f(n)$ found by differentiation, $$ \sum_{n\geq 1}f(n)\frac{x^{n-1}}{(n-1)!}=(1+x)e^{x+x^2/2}=(1+x)\sum_{n\geq 0}f(n)\frac{x^n}{n!}. $$ So equating coefficients gives $f(n+1)=f(n)+nf(n-1)$ for $n\geq 1$.

Moreover, and explicit formula is found by noting $$ \sum_{n\geq 0}f(n)\frac{x^n}{n!}=e^xe^{x^2/2}=\left(\sum_{n\geq 0}\frac{x^n}{n!}\right)\left(\sum_{n\geq 0}\frac{x^{2n}}{2^nn!}\right) $$ and so $$ f(n)=\sum_{i\geq 0\atop\text{$i$ even}}\binom{n}{i}\frac{i!}{2^{i/2}(i/2)!}=\sum_{j\geq 0}\binom{n}{2j}\frac{(2j)!}{2^jj!}. $$

Based on this, what is a nice expression for $\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}f(i)$? (I am grateful for Sasha's current answer, but is it possible to derive such an expression more combinatorially without reference to random variables and moments? If not, that is no problem. I'm just glad to see and answer.)


(I should note that this is motivated by a passage in Richard Stanley's Enumerative Combinatorics following example 1.1.15.)

  • $\begingroup$ Is there a typo? $(-1)^{n-i}$ instead of $(-1)^{n-1}$? $\endgroup$ – Aryabhata Jan 24 '12 at 22:10
  • $\begingroup$ Sorry, yes, I have now fixed the typo. $\endgroup$ – Waldott Jan 25 '12 at 0:00

The function $\mathcal{M}(t) = \exp(t+t^2/2)$ is the moment generating function for the normal random variable $Z$ with mean $\mu =1$ and variance $\sigma^2 = 1$. This makes $f(n) = \mathbb{E}(Z^n)$ moments of $Z$.

The expression (asumming $(-1)^{n-1}$ was meant to be $(-1)^{n-r}$): $$ g(n) = \sum_{r=0}^n (-1)^{n-r} \binom{n}{r} f(r) = \mathbb{E}((Z-1)^n) $$ which is a multiple of the central moment of $Z$. But these are well know to be zero for $n=2m-1$ and for $n=2m$ equal to $(n-1)!!$. Thus $$ g(n) = \frac{(-1)^{n}+1}{2} (n-1)!! $$ If, however, there is no typo in your expression and that is you meant $$ \tilde{g}(n) =(-1)^{n-1} \sum_{r=0}^n \binom{n}{r} f(r) = (-1)^{n-1} \mathbb{E}((Z+1)^n) $$ But $Z+1$ is again a normal variable with $\mu=2$ and $\sigma^2=1$, hence $$ g(n) = (-1)^{n-1} n! [t]^n \mathrm{e}^{2t + t^2/2} = (-1)^{n-1} \sum_{j \geqslant 0 } \frac{n}{2j} 2^{n-2j} \frac{(2j)!}{2^j j!} $$

  • $\begingroup$ Thank you Sasha. I did make a typo, I apologize, and the correct form is what you initially assumed it to be. $\endgroup$ – Waldott Jan 25 '12 at 0:03
  • $\begingroup$ @Waldott Alternative way is to use $\sum _{k=0}^n (-1)^{n-k} \binom{n}{k} \binom{k}{m} = \delta_{n,m}$. This would give $g(n) = \sum_{j \geqslant 0} \delta_{n,2j}\frac{(2j)!}{2^j j!} = \sum_{j \geqslant 0} \delta_{n, 2j} (2j-1)!!$. $\endgroup$ – Sasha Jan 25 '12 at 2:46
  • $\begingroup$ Many thanks Sasha! $\endgroup$ – Waldott Jan 27 '12 at 21:32

Note: OP is asking for a more combinatorially answer. This one is based upon binomial inverse pairs.

According to OPs question the exponentially generating function (egf)

\begin{align*} F(x)=\sum_{n\geq 0}f_n\frac{x^n}{n!}=e^{x+\frac{x^2}{2}} \end{align*} has coefficients of the form \begin{align*} f_n=\sum_{k\geq 0}\binom{n}{2k}\frac{(2k!)}{2^kk!}\tag{1} \end{align*} and we are looking for a simple expression for \begin{align*} \sum_{k=0}^n(-1)^{n-k}\binom{n}{k}f_k\tag{2} \end{align*}

The following is valid for $n\geq 0$

\begin{align*} \sum_{k=0}^n(-1)^{n-k}\binom{n}{k}f_k= \begin{cases} {\displaystyle \frac{n!}{2^{\frac{n}{2}}\left(\frac{n}{2}\right)!}}&\qquad n \text{ even}\\ \tag{3}\\ 0&\qquad n \text{ odd}\\ \end{cases} \end{align*} which leads to the binomial identity \begin{align*} \sum_{k=0}^{2n}(-1)^k\binom{2n}{k}\sum_{j=0}^{\lfloor\frac{k}{2}\rfloor}\binom{k}{2j}\frac{(2j)!}{2^jj!}=\frac{(2n)!}{2^nn!} \qquad\qquad (n\geq 0)\tag{4} \end{align*}

In order to show this relationship we create a binomial inverse pair by multiplying exponential generating functions (egfs).

Let $F(x)=\sum_{n\ge0}f_{n}\frac{x^n}{n!}$ and $G(x)=\sum_{n\ge0}g_{n}\frac{x^n}{n!}$ egfs with $F(x)=G(x)e^x$. Comparing coefficients gives the following

Binomial inverse pair: \begin{align*} F(x)&=G(x)e^x&G(x)&=F(x)e^{-x}\\ f_n&=\sum_{k=0}^{n}\binom{n}{k}g_k&g_n&=\sum_{k=0}^{n}\binom{n}{k}(-1)^{n-k}f_k\qquad \tag{5} \end{align*}

This simple one and many other examples of binomial inverse pairs can be found e.g. in the classic Combinatorial Identities by John Riordan ($1968$).

We observe that $g_n$ has already the shape we are looking for in (2) and we also see that $$F(x)=e^{x+\frac{x^2}{2}}=G(x)e^x$$ with $G(x)=e^{\frac{x^2}{2}}$. We obtain according to (5) \begin{align*} G(x)&=F(x)e^{-x}=e^{\frac{x^2}{2}}=\sum_{n\geq 0}\frac{x^{2n}}{2^nn!} =\sum_{n\geq 0}\frac{(2n)!}{2^nn!}\frac{x^{2n}}{(2n)!}\tag{6}\\ \end{align*} and \begin{align*} G(x)&=\sum_{n\geq 0}^{n}g_n\frac{x^n}{n!}\\ &=\sum_{n\geq 0}\left(\sum_{k=0}^n\binom{n}{k}(-1)^{n-k}f_j\right)\frac{x^n}{n!}\tag{7}\\ &=\sum_{n\geq 0}\left(\sum_{k=0}^n\binom{n}{k}(-1)^{n-j} \sum_{j=0}^{\lfloor\frac{k}{2}\rfloor}\binom{k}{2j}\frac{(2j!)}{2^jj!}\right)\frac{x^n}{n!}\tag{8}\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\Box \end{align*}


  • In (7) we substitute $g_n$ according to (4)

  • In (8) we substitue $f_n$ according to (2)


  • According to (6) the coefficients of even powers of $G(x)$ are $\frac{(2n)!}{2^nn!}$ and zero otherwise. So, the claim (3) holds.

  • Comparing the coefficients of $G(x)$ in (6) and (8) show the binomial identity in (4) is valid.


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.