Finding two sequences from certain conditions.

Question

$t_n=(n+4)t_{n-1}-4nt_{n-2}+(4n-8)t_{n-3}$ holds for $n\geq 3$. Certain terms starting from $t_0$ are $2,3,6,14,40,...$ (three more terms are given I didn't write). Find $a_n,b_n$ such that they are well known sequences such that $t_n=a_n+b_n$.$$\text{Attempt}$$ I couldn't do anything as the only thing given is a recursion. Tried some basic manipulation with it but it didn't help. When I saw the solution it stated that some $\text{guess work }$ reveals the sequences are $n!,2^n$. I know certain terms of sequences like $n,n^2,n^3,n^2+n,n!,2^n$. Pascals triangle (all independently). There are many combination of those.I personally can't tell the start of the sequence $n!+2^n$ without some arithmetic. So wanted to know if there was an elegant way of solving it dodging this guess work.

Answer 1

The obvious first guess is an $n!$ somewhere, because the coefficients on the RHS has an extra $n$ (i.e., $\underbrace{n}_{t_{n-1}}-\underbrace{4n}_{t_{n-2}}+\underbrace{4n}_{t_{n-3}}=n$. This is a feature of all such polynomial-coefficient equations as long as there is the largest nontrivial degree appears with $t_{n-1}$ and isn't cancelled by other coefficients that a solution has to grow like $\prod p(n)$). Then a naive subtraction yields the guess $t_n=n!+2^n$.

And you can prove this formula satisfies the recurrence relation: \begin{align*}\require{color} RHS & = (n+4)[(n-1)!+2^{n-1}] - 4n[(n-2)!+2^{n-2}] + (4n-8)[(n-3)!+2^{n-3}]\\ &=n!+{\color{red}4(n-1)!}+({\color{blue}n}+4)2^{n-1} - {\color{red}4n(n-2)!}-{\color{blue}n2^n} + {\color{red}4(n-2)!}+({\color{blue}n}-2)2^{n-1}\\ &=n!+2^n=LHS \end{align*}