Formula for $a_n$ where $a_n = n(a_{n-1}+a_{n-2})$

Question

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.

Answer 1

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)!$$