Guessing a non-recursive formula for a mathematical sequence I am stuck on a question, I'm not sure if I'm going about it correctly.
The question: Suppose $a_0, a_1, a_2, \ldots$ is a sequence such that $a_0 = a_1 = 1$ and, for $n \ge 2$, $a_{n+1} = n(a_n +  a_{n-1})$.
For the sequence I determined that:
$a_0 =  1, a_1 = 1, a_2 = 2, a_3 = 6, a_4 = 24$ and $a_5 = 120$.
I am trying to guess the non-recursive formula for this problem, but I am lost.
I know it should be easy, but is there a method or strategy that I should use to narrow down my formula or is it complete guesswork?
 A: We will prove that $a_k=k!$ by induction.
$k=0$ and $k=1$ - the formula is true, you already checked it.
Assume $a_{n-1}=(n-1)!$ and $a_n=n!$.
Then
$$a_{n+1}=n(a_{n-1}+a_n)=n((n-1)!+n!)=n\cdot(n-1)!(1+n)=n!(n+1)=(n+1)!$$
so, by induction, $a_n=n!$ for all $n$.
A: Similar to larry01's answer, but I prove $$a_n=n\cdot a_{n-1}$$ by induction
For $n=1$ and $n=2$, the claim is true.
Suppose, the claim is true for $n$ and $n+1$
We have $$a_{n+2}=(n+1)(a_{n+1}+a_n)=(n+1)((n+1)a_n+a_n)=(n+2)(n+1)a_n=(n+2)a_{n+1}$$
Using the recurrence relation $a_1=1$ , $a_n=n\cdot a_{n-1}$ it is easy to guess that $a_n=n!$
A: Write the recurrence as $a_{n+1} - (n+1) \,a_n= -(a_n -  n\,a_{n-1})\,$. Applying repeatedly:
$$a_{n+1} - (n+1) a_n= -(a_n -  na_{n-1})=(-1)^2(a_{n-1} -  (n-1)a_{n-2})=\cdots =(-1)^n (a_1 - 1 \cdot a_0)$$
But the RHS is $0$ because $a_0=a_1=1\,$, therefore $a_{n+1}-(n+1)\,a_n=0\,$, so in the end $a_n=n!\,$.

[ EDIT ]   May be worth noting that the above $\,a_n=n  a_{n-1} + (-1)^{n-1} (a_1 - a_0)\,$ gives the general solution in terms of arbitrary $\,a_0,a_1\;$ as $\;a_n=n!\,\left(a_0 + (a_1-a_0)\,\sum_{k=1}^{n}\frac{(-1)^{k-1}}{k!}\right)\,$.
