Finding the 'closed' form of this exponential generating function

Question

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

Answer 1

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