1
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Gary
    Mar 4, 2021 at 9:32
  • $\begingroup$ 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... $\endgroup$
    – JonDoe
    Mar 5, 2021 at 6:11
  • 1
    $\begingroup$ 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? $\endgroup$
    – Gary
    Mar 5, 2021 at 6:33
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Gary
    Mar 8, 2021 at 14:56
  • 1
    $\begingroup$ Because for odd $k$, $a_k=0$ (by definition). $\endgroup$
    – Gary
    Mar 11, 2021 at 17:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .