How do I get the nth term of the following sequence?
$$ x_n = 4n(n-1) \cdot (x_{n-1} + 2 (n-1) x_{n-2}), \, x_1 = 0, \, x_2=16$$I've tried defining the auxiliar sequence $y_n$ as $\frac{x_n}{n!}$ which led to
$$ y_n = 4 \cdot (n-1) \cdot (y_{n-1} + 2 \cdot y_{n-2})$$And then I defined another sequence $z_n$ such that $z_n = \frac{y_n}{2^n}$ from which I got
$$ z_n = 2 (n-1) ( z_{n-1} + z_{n-2})$$and this is very close to the recursive relation for the number of derangements of $n$ terms, which is
$$ D_n = (n-1) ( D_{n-1} + D_{n-2})$$However, I couldn't get any further
Answer: $$x_n=2^nn!(-1)^n\,_2F_0(1/2,-n;\{ \};2)$$
Proof sketch:
Instead of making the substitution $x_n \rightarrow n ! y_n$ like the OP did, you make substitution $x_n \rightarrow(n !)^2 b_n$. The recursion equation becomes $$ n b_n=4(n-1)b_{n-1}+8b_{n-2} $$ Now, we use generating function to solve it. Let $$ F(x)=\sum_{n=1}^\infty b_{n} x^{n} $$ The recursion equation is equivalent to the following differential equation: $$ (1-4 x) \frac{\mathrm{d} F(x)}{\mathrm{d} x}-b_{1}=8 x^{2} F(x) $$ Using boundary conditino $b_{1}=0$ This equation can be solved to give $$ F(x)=\frac{k e^{\frac12-2 x}}{\sqrt{1-4 x}} $$ $k$ is integration constant
Using other condition that $x_{2}=16$, the constant $k$ is fixed to be $e^{-1 / 2}$ Giving the final result $$ F(x)=\frac{e^{-2 x}}{\sqrt{1-4 x}} $$ The coefficient of $x^{n}$ in the expansion of $F(x)$ is $$ \frac{(-2)^{n} {{}_2 F_0}\left(\frac{1}{2},-n ;\{\} ; 2\right)}{n !} $$