1
$\begingroup$

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?

$\endgroup$
0

3 Answers 3

3
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Great, thank you for this. As far as determining the formula $\Bbb a_k$ = $\Bbb k!$ , is that guesswork? I know in this problem I missed the glaring fact that it was a factorial, but what about otherwise? $\endgroup$
    – jtujague
    Mar 2, 2017 at 23:04
  • 1
    $\begingroup$ yeah, first compute some values, then try to guess the general formula and next prove it (for example by induction) $\endgroup$
    – larry01
    Mar 2, 2017 at 23:08
  • 1
    $\begingroup$ there is a universal method of solving linear recurrences, but this one in not linear. $\endgroup$
    – larry01
    Mar 2, 2017 at 23:10
  • $\begingroup$ @larry01 You should have explained how to guess the formula. Nevertheless, +1 for the formula and the proof. $\endgroup$
    – Peter
    Mar 2, 2017 at 23:16
  • 1
    $\begingroup$ I guessed it just looking at the values that jtujague computed, $1,2,6,24,120$ are not so random numbers ;) $\endgroup$
    – larry01
    Mar 2, 2017 at 23:23
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ The relation $a_n=n\cdot a_{n-1}$ is not difficult to see using the given values. $\endgroup$
    – Peter
    Mar 2, 2017 at 23:18
  • $\begingroup$ That makes it clear, thanks. $\endgroup$
    – jtujague
    Mar 2, 2017 at 23:21
0
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .