Recurrence relations with multiplication

Question

I have a recurrence relation and I am not quite sure if I am solving it correctly.

The relation is this: $$t_n = 2n~t_{n-1}$$ where $t_0 = 1$

Here is how I went about solving this:

First step is to substitute $n$ with $n-1$ in my original relation so I get: $t_{n-1} = 2(n-1)t_{n-1-1}$ so $t_{n-1} = 2(n - 1)t_{n-2}$. Then substitute this in for $t_{n-1}$ in my original equation.

So far: $$t_n = 2n \cdot 2(n-1)t_{n-2}$$

Then take the original equation again this time substituting $n-2$ in for $n$. We get: $$t_{n-2} = 2(n-2)t_{n-3}$$

So far: $$t_n = 2n \cdot 2(n-1) \cdot 2(n-2)t_{n-3}$$

From here I see the pattern.

If we continue the series we will get:

$$t_n = 2n \cdot 2(n-1) \cdot 2(n-2) \cdot 2(n-3) \cdot \ldots $$ $$ \ldots \cdot 2(n-(n-3)) \cdot 2(n-(n-2)) \cdot 2(n-(n-1)) \cdot 2(n-n) \cdot t_0$$

So from here it looks like we got $$t_n = 2n \cdot \ldots \cdot 6 \cdot 4 \cdot 2 \cdot 0 \cdot 1$$

So this whole relation is $0$? Am I right when I am multiplying everything together? Seems like I did all this work only to get $0$ so I am not quite sure in my answer.

Answer 1

Let $u_n=\dfrac{t_n}{2^n}$.

Then $u_n=\dfrac{t_n}{2^n}=\dfrac{2nt_{n-1}}{2^n}=nu_{n-1}$.

Since $u_0=t_0=1$, we have $u_n=n!$ and so $t_n = 2^n u_n = 2^n n!$.

Answer 2

Assume $n>0$ for the recursion.

$$t_1=2\cdot 1\cdot t_0$$ $$t_2=2\cdot 2\cdot t_1=2\cdot 2\cdot 2\cdot 1\cdot t_0 $$ $$t_3=2\cdot 3 \cdot t_2=2\cdot 3 \cdot 2\cdot 2\cdot 2\cdot 1\cdot t_0$$

The pattern should be clearer this way, as for each substitution you get a additional power for $2$ and you get the product of integer numbers (factorial). In general $t_n=2^nn!$