Formula for $a_n$ where $a_n = n(a_{n-1}+a_{n-2})$ Formula for $a_n$ if $a_0=1$ and $a_1=2$ and n greater than equal to 2
$a_n = n \times (a_{n-1}+a_{n-2})$.
Attempt: $ a_2 =6, a_3=24, a_4=120, a_5=720 , a_6 = 5040 $ It so looks like $a_n= (n+1)!$
I tried to open $n \times (n-1 \times (a_{n-2}+a_{n-3}) + a_{n-2})$.
Unable to get formula in factorial terms.
 A: Once you've noticed the pattern, it can be proved using induction on $n$: 
For the base case, $a_0=1!$, $a_1=2!$. 
For the induction step, if $n>1$ and $a_k=(k+1)!$ for $0\leq k\leq n-1$, then
$$ a_n=n(a_{n-1}+a_{n-2})=n(n!+(n-1)!)=n(n-1)!(n+1)=(n+1)!$$
A: There is a way to solve this using generating functions and solving
ordinary differential equations. The use of ordinary generating
functions is more complicated due to convergence failure, but
exponential generating functions work in this case.
Suppose $\,a_n\,$ is a sequence of numbers. Then $\,y =E[a_n] := \sum_{n=0}^\infty a_n x^n/n!\,$ is its exponential generating function. The two properties we need are $\, E[na_n] = xy'\,$ and $\,E[a_{n+1}] = y'.\,$ The recursion is $\,a_n = n \times (a_{n-1}+a_{n-2}).\,$
We modify the recursion to be $\,a_{n+2} = (n+2)(a_{n+1} + a_n).\,$ Now $E[a_{n+2}] = y'',\,$
$\,E[a_{n+1}+a_n] = (y+y').\,$ The recursion becomes
$$ y'' = 2(y+y') + x(y+y')' = 2y + (x+2)y' + xy''. $$
Solving this differential equation with the initial conditions $\,y(0) = 1,\, y'(0) = 2\,$ gives the solution $\, y(x) = 1/(1-x)^2.\,$ Now $\, y = 1 + 2x + 3x^2 + \cdots = \sum_{n=0}^\infty (n+1)x^n $ and thus $\,y = E[(n+1)n!]\,$ or simply $\,a_n = (n+1)!.$
