This question already has an answer here:

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. Falcon Jan 7 '17 at 17:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 3
    $\begingroup$ It cannot be more valid. $\endgroup$ – marwalix Jan 7 '17 at 14:50
  • $\begingroup$ You can make the statement hold for $k\in\mathbb{N},k<n+1$ and discuss the case like what you did above. $\endgroup$ – tommy xu3 Jan 7 '17 at 14:51
  • 2
    $\begingroup$ 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)$. $\endgroup$ – Blencer Jan 7 '17 at 14:53
  • 1
    $\begingroup$ 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). $\endgroup$ – 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


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