Find an explicit formula for the recurrence $a_n = n(a_{n-1} + a_{n-2})$ knowing that $ a_0=1$ and $a_1=2$.

Question

What i've tried to do is define a formal power series such that $$A(x)=\sum_{n=0}^{\infty}a_n \dfrac{x^n}{n!}$$ Using my recurrence relation I find that $A(x)-1-2x = x(A(x)-1)+ \displaystyle\sum_{n=2}^{\infty}na_{n-2} \dfrac{x^n}{n!}$ I do not know how to proceed after this.

Answer 1

Often, using exponential generating functions to solve a recurrence boils down to solving a differential equation.

You can rewrite your last sum in terms of $\int A(x)\,dx$: $$\sum_{n=2}^\infty na_{n-2}\frac{x^n}{n!}=x\sum_{n=2}^\infty a_{n-2}\frac{x^{n-1}}{(n-1)!}=x\sum_{n=0}^\infty a_{n}\frac{x^{n+1}}{(n+1)!}=x\cdot\int A(x)\,dx$$ This gives you a differential equation in $A(x)$: $$ A(x)-1-2x=x(A(x)-1)+x\int A(x)\,dx $$ To make this look like a more standard first-order linear equation, let $B(x)=\int A(x)\,dx$, so $$ B'(x)-1-2x = x(B'(x)-1)+xB(x) $$ then use the standard method to solve (integrating factor, etc).