Explicit Formula From Recurrence Relation

Question

I can't seem to figure out how to find the explicit formula for recurrence relation $a_n=2na_{n-1}$, $a_0=1$.

So here is what I have. $a_0 = 1$, $a_1 = 2$, $a_2 = 8$, $a_3 = 48$, $a_4 = 384$.

So from $a_1 = 2$ to $a_2 = 8$, we take 2 * 4 which is 8 for $a_2$. We take 8 * 6 which is 48 for $a_3$ and so on. So each time we are taking the previous value and multiply it by an increment of 2, 4, 6, 8, 10 etc. Like $a_1$ * 4, $a_2$ * 6, $a_3$ * 8, etc. I just can't figure out how to write the explicit formula as I don't see a common different here. It not going up by a common different.

Can someone help me with the rest of this problem? Thank you.

Answer 1

If we think of the two relations $a_n=na_{n-1}$ with solution $a_n=n!$ and $a_n=2a_{n-1}$ with solution $a_n=2^n$, yours is $a_n=2^nn!$

Answer 2

No, it isn’t an arithmetic sequence. A useful technique with a first order recurrence like this one is to ‘unwind’ it:

$$\begin{align*} a_n&=2na_{n-1}\\ &=2n\big(2(n-1)a_{n-2}\big)\\ &=2^2n(n-1)a_{n-2}\\ &=2^2n(n-1)\big(2(n-2)a_{n-3}\big)\\ &=2^3n(n-1)(n-2)a_{n-3}\\ &\;\;\vdots\\ &=2^kn(n-1)\ldots(n-k+1)a_{n-k}\\ &=\;\;\vdots\\ &=2^nn(n-1)(n-2)\ldots(n-n+1)a_{n-n}\\ &=2^nn(n-1)(n-2)\ldots(1)a_0\\ &=2^nn(n-1)(n-2)\ldots(1) \end{align*}$$

Can you see a simpler way to write that last expression?

Answer 3

Note

$$a_n = 2n a_{n-1} =2^2n(n-1) a_{n-2} =2^3n(n-1)(n-2) a_{n-3} =...= 2^n n!$$