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

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.

## marked as duplicate by Arnaud D., Simply Beautiful Art, kingW3, Henrik, C. FalconJan 7 '17 at 17:35

• You can make the statement hold for $k\in\mathbb{N},k<n+1$ and discuss the case like what you did above. – tommy xu3 Jan 7 '17 at 14:51
• You should use Double induction, it allows you to suppose $P(n)$ and $P(n-1)$ and prove $P(n+1)$, having verified $P(0)$ and $P(1)$. – Blencer Jan 7 '17 at 14:53
• You need $a_k = k!$ for two values of $k$ in the induction step. So you must formulate the induction hypothesis in a way that yields the two needed instances. And you can't use the induction step to prove $a_2 = 2!$, so you need to make that special (include it in the base case or so). – Daniel Fischer Jan 7 '17 at 14:55
$$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