# Finding the 'closed' form of this exponential generating function

The exponential generating function of this recurrence relation, $$T_n=T_{n-1}\;+(n-1)\cdot T_{n-2}\;$$, is

$$f(x)=e^{x + \frac{x^2}{2}}$$

Multiplying the exponential generating functions for each term, we get, $$=\ \sum_{j\geq0}\;\frac{1}{j!}x^j\cdot\sum_{k\geq0}\;\frac{1}{2^kk!}x^{2k}$$ $$=\ \sum_{j,\ \ k\geq0}\;\frac{1}{j!}\cdot\frac{1}{2^kk!}x^{j+2k}$$

Taking $$n\ =\ j\ +\ 2k$$, $$=\ \sum_{n-2k,\ \ k\geq0}\;\frac{1}{(n-2k)!}\cdot\frac{1}{2^kk!}x^n$$

What steps can I take from here to get to the 'closed' form of the exponential generating function, i.e.,

$$\;\sum_{n\ge0}\Big(\sum_{k=0}^{[n/2]}\frac{n!}{(n-2k)!2^kk!}\Big)\frac{x^n}{n!}.$$

If you set $$a_{2k} = \frac{1}{{2^k k!}},\quad a_{2k + 1} = 0$$ for $$k\geq 0$$, then $$\!\left( {\sum\limits_{j = 0}^\infty {\frac{1}{{j!}}x^j } } \right)\!\left( {\sum\limits_{k = 0}^\infty {\frac{1}{{2^k k!}}x^{2k} } } \right) = \left( {\sum\limits_{j = 0}^\infty {\frac{1}{{j!}}x^j } } \right)\!\left( {\sum\limits_{k = 0}^\infty {a_k x^k } } \right) = \sum\limits_{n = 0}^\infty {\left( {\sum\limits_{k = 0}^n {\frac{1}{{(n - k)!}}a_k } } \right)x^n } .$$ Now it remains to simplify $$\sum\limits_{k = 0}^n {\frac{1}{{(n - k)!}}a_k }.$$ Since the terms corresponding to even $$k$$'s contribute only, we put $$k=2m$$ where $$m$$ runs between $$0$$ and $$\left[ n/2 \right]$$ (in this way we took into account all the even $$k$$'s between $$0$$ and $$n$$). Thus, $$\sum\limits_{k = 0}^n {\frac{1}{{(n - k)!}}a_k } = \sum\limits_{m = 0}^{\left[ {n/2} \right]} {\frac{1}{{(n - 2m)!}}a_{2m} } = \sum\limits_{m = 0}^{\left[ {n/2} \right]} {\frac{1}{{(n - 2m)!}}\frac{1}{{2^m m!}}} .$$ Hence, the exponential generating function is $$\sum\limits_{n = 0}^\infty {\left( {\sum\limits_{m = 0}^{\left[ {n/2} \right]} {\frac{1}{{(n - 2m)!2^m m!}}} } \right)x^n } = \sum\limits_{n = 0}^\infty {\left( {\sum\limits_{m = 0}^{\left[ {n/2} \right]} {\frac{{n!}}{{(n - 2m)!2^m m!}}} } \right)\frac{{x^n }}{{n!}}} .$$

• Since the terms with $a_{2k}$ contribute only, replace $k$ with, say, $2m$ in my last expression. If $0\leq k\leq n$, then $0\leq m \leq\ldots$ Can you see it? Also you have to divide $x^n$ by $n!$ in your very last line. Otherwise it is not an exponential generating function.
– Gary
Mar 4, 2021 at 9:32
• I just had another question, how did $$\left( {\sum\limits_{j = 0}^\infty {\frac{1}{{j!}}x^j } } \right)\!\left( {\sum\limits_{k = 0}^\infty {\frac{1}{{2^k k!}}x^{2k} } } \right)$$ change to this $$= \sum\limits_{n = 0}^\infty {\left( {\sum\limits_{k = 0}^n {\frac{1}{{(n - k)!}}a_k } } \right)x^n }$$ What happened to $x^{2k}\;$? I'm a bit new to summation, so it'll be great if you could help me out... Mar 5, 2021 at 6:11
• There is an extra step inbetween. Take that into account and then apply the Cauchy product of the two series: en.wikipedia.org/wiki/… This answer of mine was accepted and upvoted before, wan't it?
– Gary
Mar 5, 2021 at 6:33
• I do not really understand what the issue is here. Just use $$\left( {\sum\limits_{j = 0}^\infty {\alpha _j x^j } } \right)\left( {\sum\limits_{k = 0}^\infty {\beta _k x^k } } \right) = \sum\limits_{n = 0}^\infty {\left( {\sum\limits_{k = 0}^n {\alpha _{n - k} \beta _k } } \right)x^n } .$$ In our case $\alpha_j=1/j!$ and $\beta_k =a_k$.
– Gary
Mar 8, 2021 at 14:56
• Because for odd $k$, $a_k=0$ (by definition).
– Gary
Mar 11, 2021 at 17:01