Solve the recurrence $ T_{n + 1} = T_{n} + nT_{n - 1}$

Question

Solve the recurrence $$ T_{n + 1} = T_{n} + nT_{n - 1}\,, \quad\mbox{for}\quad n \geq 1\quad \mbox{with initial conditions}\ T_{0} = T_{1} = 1 $$ by finding the exponential generating function and extracting the coefficient of $x^{n}/n!$.

So far I was able to reduce it the differential equation: $T'\left(x\right) = T\left(x\right)\left(x + 1\right)$. That has a solution $T\left(x\right) = ce^{t\left(t + 2\right)/2}$. How do I extract the coefficient of $x^{n}/n!$ ?. Thanks.

Answer 1

Well, do you know the power series for the exponential function? Substitute $(1/2)t (t+2)$ for the variable.

Answer 2

The formula $T(x)=\mathrm e^{x+x^2/2}$ is correct and yields $$\sum_{n\geqslant0}\frac{T_n}{n!}x^n=\mathrm e^x\cdot\mathrm e^{x^2/2}=\sum_{i\geqslant0}\frac1{i!}x^i\cdot\sum_{k\geqslant0}\frac1{2^kk!}x^{2k} $$ hence $$ T_n=\sum_{0\leqslant2k\leqslant n}\frac{n!}{2^kk!(n-2k)!}=\sum_{0\leqslant2k\leqslant n}(2k-1)!!\cdot{n\choose2k}. $$ This is sequence A000085 of the OEIS. The formula on the right makes apparent that each $T_n$ is an integer. Note that $T_n$ enumerates, for example, the Young tableaux with $n$ cells, for which no simpler formula is given in the OEIS (a fact which begs the question of the meaning of "extracting the coefficient" in your question).

Answer 3

$T_{n+1}=T_n+nT_{n-1}$

$T_{n+1}-T_n-nT_{n-1}=0$

Let $T_n=\int_Cs^nK(s)~ds$ ,

Then $\int_Cs^{n+1}K(s)~ds-\int_Cs^nK(s)~ds-n\int_Cs^{n-1}K(s)~ds=0$

$\int_Cs^n(s-1)K(s)~ds-\int_CK(s)~d(s^n)=0$

$\int_Cs^n(s-1)K(s)~ds-[s^nK(s)]_C+\int_Cs^n~d(K(s))=0$

$\int_Cs^n(s-1)K(s)~ds-[s^nK(s)]_C+\int_Cs^nK'(s)~ds=0$

$-[s^nK(s)]_C+\int_Cs^n(K'(s)+(s-1)K(s))~ds=0$

$\therefore K'(s)+(s-1)K(s)=0$

$K'(s)=(-s+1)K(s)$

$\dfrac{K'(s)}{K(s)}=-s+1$

$\int\dfrac{K'(s)}{K(s)}ds=\int(-s+1)~ds$

$\ln K(s)=-\dfrac{s^2}{2}+s+c_1$

$K(s)=ce^{-\frac{s^2}{2}+s}$

$\therefore T_n=\int_Ccs^ne^{-\frac{s^2}{2}+s}~ds$

But since the above procedure in fact suitable for any complex number $s$ ,

$\therefore {T_n}^m=\int_{a_m}^{b_m}c_m(k_mt)^ne^{-\frac{(k_mt)^2}{2}+k_mt}~d(k_mt)={k_m}^{n+1}c_m\int_{a_m}^{b_m}t^ne^{-\frac{{k_m}^2t^2}{2}+k_mt}~dt$

For some $n$-independent real number choices of $a_m$ and $b_m$ and $n$-independent complex number choices of $k_m$ such that:

$\lim\limits_{t\to a_m}t^ne^{-\frac{{k_m}^2t^2}{2}+k_mt}=\lim\limits_{t\to b_m}t^ne^{-\frac{{k_m}^2t^2}{2}+k_mt}$

$\int_{a_m}^{b_m}t^ne^{-\frac{{k_m}^2t^2}{2}+k_mt}~dt$ converges

For $m=1$, the best choice is $a_1=-\infty$ , $b_1=\infty$ , $k_1=\pm1$ when $n=0$ ; $a_1=0$ , $b_1=\infty$ , $k_1=\pm1$ when $n\geq1$

$\therefore T_n=\begin{cases}C_1\int_{-\infty}^\infty e^{-\frac{t^2}{2}+t}~dt~\text{or}~C_1\int_{-\infty}^\infty e^{-\frac{t^2}{2}-t}~dt&\text{when}~n=0\\C_1\int_0^\infty t^ne^{-\frac{t^2}{2}+t}~dt~\text{or}~C_1\int_0^\infty t^ne^{-\frac{t^2}{2}-t}~dt&\text{when}~n\geq1\end{cases}$

Hence $T_n=\begin{cases}C_1\int_{-\infty}^\infty e^{-\frac{t^2}{2}}\sinh t~dt+C_2\int_{-\infty}^\infty e^{-\frac{t^2}{2}}\cosh t~dt&\text{when}~n=0\\C_1\int_0^\infty t^ne^{-\frac{t^2}{2}}\sinh t~dt+C_2\int_0^\infty t^ne^{-\frac{t^2}{2}}\cosh t~dt&\text{when}~n\geq1\end{cases}$