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$
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$
  • $\begingroup$ The relation $a_n=n\cdot a_{n-1}$ is not difficult to see using the given values. $\endgroup$ – Peter Mar 2 '17 at 23:18
  • $\begingroup$ That makes it clear, thanks. $\endgroup$ – jtujague Mar 2 '17 at 23:21
2
$\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$
  • $\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 '17 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 '17 at 23:08
  • 1
    $\begingroup$ there is a universal method of solving linear recurrences, but this one in not linear. $\endgroup$ – larry01 Mar 2 '17 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 '17 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 '17 at 23:23
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$

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.