I am learning the concept of generating functions and am working on the following problem:
Let $r(n)$ be the number of $n$-permutations whose square is the identity permutation. We proved that $$r(n+2)=r(n+1)+(n+1)r(n)$$ if $n\geq 0$, while $r(0)=r(1)=1$. Use this recurrence relation to find an explicit formula for the generating function $R(x)=\sum_{n\geq 0} r(n)\frac{x^n}{n!}$.
I have two questions:
How do we know when to use an exponential generating function vs. when to use an ordinary generating function? I'm guessing it has something to do with $n\cdot r(n)$ vs. $c\cdot r(n)$ where $c$ is some constant.
I followed the usual routine of multiplying both sides of the recurrence relation by $\frac{x^n}{n!}$ and summing over all $n\geq 0$ to get $$\sum_{n\geq 0}r(n+2)\frac{x^n}{n!}=\sum_{n\geq 0}r(n+1)\frac{x^n}{n!}+\sum_{n\geq 0}(n+1)r(n)\frac{x^n}{n!}$$ which can be written as $$\sum_{n\geq 0}r(n+2)\frac{x^n}{n!}=\sum_{n\geq 0}r(n+1)\frac{x^n}{n!}+\sum_{n\geq 0}nr(n)\frac{x^n}{n!}+\sum_{n\geq 0}r(n)\frac{x^n}{n!}$$ Notice that $$R'(x)=\sum_{n\geq 1} r(n)\frac{nx^{n-1}}{n!}=\sum_{n\geq 0} r(n+1)\frac{(n+1)x^{n}}{(n+1)!}=\sum_{n\geq 0} r(n+1)\frac{x^{n}}{n!}$$ and $$R''(x)=\sum_{n\geq 2} r(n)\frac{n(n-1)x^{n-2}}{n!}=\sum_{n\geq 0} r(n+2)\frac{(n+2)(n+1)x^{n}}{(n+2)!}=\sum_{n\geq 0} r(n+2)\frac{x^{n}}{n!}$$ and $$xR'(x)=x\sum_{n\geq 1} r(n)\frac{nx^{n-1}}{n!}=\sum_{n\geq 0} r(n)\frac{nx^{n}}{n!}$$ Hence, $$R''(x)=R'(x)+xR'(x)+R(x)$$ $$R''(x)-(1+x)R'(x)-R(x)=0$$ This differential equation can be solved using the power series method. Indeed, suppose $R(x)=\sum_{k\geq 0}a_kx^k$. Substitution into the differential equation gives, $$\sum_{k\geq 2}a_kk(k-1)x^{k-2}-(1+x)\sum_{k\geq 1}a_kkx^{k-1}-\sum_{k\geq 0}a_kx^k=0$$ which can be simplified to $$\sum_{k\geq 0}\left[a_{k+2}(k+2)(k+1)-a_{k+1}(k+1)-a_kk-a_k\right] x^k=0$$ Hence we must have $$a_{k+2}(k+2)(k+1)-a_{k+1}(k+1)-a_kk-a_k=0$$ for $k\geq 0$. In other words, $$a_{k+2}=\frac{a_{k+1}(k+1)+a_k(k+1)}{(k+2)(k+1)}$$ for $k\geq 0$.
Now I computed (I think $a_0=a_1=1$ because $r(0)=r(1)=1$) $$k=0 \to a_2=1$$ $$k=1 \to a_3=\frac{2}{3}$$ $$k=2 \to a_4=\frac{5}{12}$$ $$k=3 \to a_5=\frac{13}{60}$$ which are exactly the coefficients of the series expansion of $e^{x+\frac{x^2}{2}}$. How can I show this? I was thinking to compute some values of $k$ (as I did above) and attempt to recognize a pattern. However, I am stuck on this part. Can I get some guidance?