Finding $a_n$ if $a_0=a_1=1,a_{n+1}=n(a_n+a_{n-1})\ \ (n\ge 1).$

Question

The problem states:

Suppose $a_0,a_1,a_2,...$ is a sequence such that $$a_0=a_1=1,\ \ \ a_{n+1}=n(a_n+a_{n-1})\ \ \ (n\ge 1).$$

Guess a formula for $a_n$, valid for $n\ge 1$, and use mathematical induction to prove that your guess is correct.

I used this equation (and check with WolframAlpha) to find the results of a few different cases.

$$a_2=2,\ a_3=6,\ a_4=24,\ a_5=120.$$

Unfortunately, I'm not really sure how I can prove this. I would appreciate any help in solving this!

Answer 1

Since $a_0=0!,a_1=1!,\cdots, a_4=4!,a_5=5!$, I guess that $a_n=n!$ for all non-negative integers $n$.

In the following, let us prove that $a_n=n!$ for all non-negative integers $n$.

For $n=0,1$, it holds trivially.

Assume that it holds for $n=k-1,k$, i.e. $$a_{k-1}=(k-1)!,\ \ \ \ a_k=k!.$$ Then, we have $$\begin{align}a_{k+1}&=k(a_k+a_{k-1})\\&=k(k!+(k-1)!)\\&=k(k\cdot (k-1)!+(k-1)!)\\&=k\cdot (k-1)!\cdot(k+1)\\&=(k+1)!.\end{align}$$ Hence, it holds for $n=k+1$.

Hence, $a_n=n!$ for all non-negative integers $n$. Q.E.D.

Answer 2

You can also have an induction on "$a_n=n\,a_{n-1}$".

It is true for $a_1=1=1\times a_0$ and $a_2=2=2\times a_1$.

Then $a_{n+1}=n(a_n+a_{n-1})=n\,a_n+n\,a_{n-1}=n\,a_n+a_n=(n+1)\,a_n$ and induction proof follows.

Finally $a_n=n!$