finding an nth term from complex recurrence relations

Question

For simple recurrence relations like, $t_{n} = t_{n-1} + 3$ where $t_0$ is 1 gives the nth term $t_n = 3n + 1$ where $n\geq0$

Or $t_n = xt_{n-1}$ where $t_0 = a$ the nth term is $t_n = ax^n$ where $n\geq0$

how do any of these rules scale up to finding the nth term for more complicated relations like:

$t_n = n^2T_{n-1}$ where $n\geq0$

or a non-linear expressions like:

$t_n = \frac{n^3}{n+2}t_{n-1}$ where $n\geq0$

Answer 1

• If one has a relation of the type $$ t_n = a_n\cdot t_{n-1}, \qquad n=1,2,\cdots, $$ one may in general just deduce that $$ \frac{t_n}{\prod_{k=1}^na_k} = \frac{t_{n-1}}{\prod_{k=1}^{n-1}a_k}, \qquad n=1,2,\cdots, \tag1 $$ leading to the relation $$ u_n=u_{n-1}, \qquad n=1,2,\cdots, \tag2 $$ with $\displaystyle u_n=\frac{t_n}{\prod_{k=1}^na_k}$, the relation $(2)$ is then easier to evaluate.
• Observe that applying it to the particular sequences given in your question, one gets $$ \begin{align} t_n &= n^2 \times t_{n-1} &\text{leads to} \quad &t_n= c_0 \times (n!)^2 \\ t_n &= \frac{n^3}{n+2} \times t_{n-1} &\text{leads to} \quad &t_n= c_1 \times \frac{(n!)^2}{(n+1)(n+2)} \end{align} $$ where $c_0,c_1$ are arbitrary constants.