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!

  • $\begingroup$ I always suggest the use of oeis.org, if one is stuck with a sequence, to get some inspiration. You can find great information for many sequences there in the comments. $\endgroup$ – andre Oct 8 '14 at 19:56

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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.