Guessing a non-recursive formula for a mathematical sequence

Question

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?

Answer 1

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

Answer 2

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$.

Answer 3

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)\,$.