Given sequence $(x_n)$ such that $x_0 = 0, x_1 = 1, x_2 = 1, x_3 = 4$ and $$x_{n + 3} = \frac{(n + 1)(n^2 + n + 1)}{n}x_{n + 2} + (n^2 + n + 1)x_{n + 1} - \frac{n + 1}{n}x_n, \forall n \ge 1$$
Prove that $x_n$ is a perfect square for $\forall n \ge 0$.
Right, we could theoretically determine the functions $g(n), h(n)$ and $f(n)$ such that $$x_n = x_3f(n) + x_2g(n) + x_1h(n) = 4f(n) + g(n) + h(n), \forall n \ge 1$$
whereas we could find the regression condition of sequence $(\sqrt{x_n})$ if possible.
Consider sequence $(y_n)$ such that $y_0 = 0, y_1 = 1, y_2 = 1$ and $$y_{n + 2} = ny_{n + 1} + y_n, y \ge 1$$
We obtain that $y_3 = 2$ and $y_n \in \mathbb N, \forall n \ge 0$.
We have that $$y_{n + 3}^2 = [(n + 1)y_{n + 2} + y_{n + 1}]^2 = (n + 1)^2y_{n + 2}^2 + 2(n + 1)y_{n + 2}y_{n + 1} + y_{n + 1}^2$$
$$ \implies ny_{n + 3}^2 = n(n + 1)^2y_{n + 2}^2 + 2n(n + 1)y_{n + 2}y_{n + 1} + ny_{n + 1}^2$$
$$ = n(n + 1)^2y_{n + 2}^2 + (n + 1)[(y_{n + 2}^2 + n^2y_{n + 1}^2) - (y_{n + 2} - ny_{n + 1})^2] + ny_{n + 1}^2$$
$$ = (n + 1)(n^2 + n + 1)y_{n + 2}^2 + n(n^2 + n + 1)y_{n + 1}^2 - (n + 1)y_n^2$$
$$ \implies y_{n + 3}^2 = \frac{(n + 1)(n^2 + n + 1)}{n}y_{n + 2}^2 + (n^2 + n + 1)y_{n + 1}^2 - \frac{n + 1}{n}y_n^2$$
It could be reasoned that $(x_n)$ and $(y_n^2)$ satisfy the same regression condition.
Furthermore, it is true that $x_0 = y_0^2 = 0, x_1 = y_1^2 = 1, x_2 = y_2^2 = 1, x_3 = y_3^2 = 4$.
$\implies x_n$ is a perfect square for $\forall n \ge 0$.