Given $a_1=1, a_2=2, a_{n+1}=n(a_n+a_{n-1})$ find the general term

Question

Given recursively defined sequence $(a_n)$: $$a_1=1$$ $$a_2=2$$ $$a_{n+1}=n(a_n+a_{n-1}), n\geq 2$$

Find the formula for the general term $a_n$.

This is what I did:

So the first few terms are: $a_1=1, a_2=2,a_3=6,a_4=24,a_5=120,...$ I guess the general term can be written as $n!$. Let's prove it by mathematical induction:

Base case: $a_1=1!=1$ so it's true for $n=1$. Let's assume it's true for some $n$,i.e. $a_n=n!$. Then $$a_{n+1}=n(a_n+a_{n-1})=n(n!+(n-1)!)=n(n(n-1)!+(n-1)!)=n(n-1)!(n+1)=(n+1)n(n-1)!=(n+1)!$$

Using the principle of mathematical induction we've proved that the general term of this sequence is $n!$.

Is this proof valid? I'm not sure whether it's allowed to put $a_{n-1}=(n-1)!$ here.

Answer 1

$$ a_n=n! $$

This can be shown using induction of the form: Check for $n=1$ and $n=2$, and then assuming that the statement is true for $n=k$ and $n=k+1$, where $k$ arbitrary, show that it is true for $n=k+2$.

So, indeed, $a_1=1!$ and $a_2=2!$. Assume that $a_k=k!$ and $a_{k+1}=(k+1)!$, then $$ a_{k+2}=(k+1)(a_k+a_{k+1})=(k+1)k!+(k+1)(k+1)!=(k+1)!+(k+1)(k+1)!=(k+2)!. $$ QED