Find the general term of the sequence defined by $x_0 = 3, x_1 = 4$ and $x_{n+1} = x_{n-1}^2 - nx_n$ Question:
Find the general term of the sequence defined by $x_0 = 3, x_1 = 4$ and $x_{n+1} = x_{n-1}^2 - nx_n$.
Attempt:
If I'm not mistaken this does not match any linear homogeneous pattern, nor does it match linear nonhomogenous recurrence relation with constant coefficient. Out of desperation, I resort to finding a descent conjecture,
$$x_2 = 5\\x_3 = 6\\\vdots$$
I then conjectured,
$$x_n = n+3$$
I proved this using induction.
After solving this problem, lots of question arised,


*

*Other than Linear Homogeneous Recurrence Relation, and Linear non Homogeneous relation with constant coefficients, what other solvable types of Linear Relations are out there.

*Other than making conjecture like what I did above, can someone else recommend a technique of attacking the question above?

 A: Here's an another approach solving the recurrrence relation 
\begin{align*}
x_0&=3\\
x_1&=4\tag{1}\\
x_{n+1}&=x_{n-1}^2-nx_n\qquad\qquad n\geq 2
\end{align*}
But first a few words to your classification of this recurrence relation. You're right when you're saying it's neither a linear nor  a non-linear homogeneous recurrence relation with constant coefficient. You could argue:

Type of recurrence relation:



*

*Since the constant term is 0 it's a homogeneous recurrence relation

*Since $x_{n-1}$ occurs squared it's a non-linear recurrence relation

*Since the coefficent of $x_{n}$ is $n$ it's a recurrence relation with non-constant coefficients

*Since $x_{n+1}$ is specified with the help of $x_n$ and $x_{n-1}$ there are two degrees of freedom and so it is a recurrence relation of order 2. We therefore need two initial values to fully specify the recurrence relation.


So, we can specify:

The recurrence relation (1) is a quadratic, homogeneous recurrence relation of order 2 with non-constant coefficients.

Now an alternative approach in three steps.

1.) Ansatz: $x_n$ is a polynomial $P$ in $n$

Since the initial values are constants and $x_{n+1}$ is defined as square of a former term and $n$ times another former term we could check if $x_n$ is a polynomial in $n$.
Attention: As @ChristianBlatter pointed out with a counter example in a comment below, it's not always the case that $x_n$ is a polynomial. It depends on the structure of the recurrence relation.

2.) The degree deg P

So, let's consider $x_n$ to be a polynomial $P(n)$ and try to determine the degree $d=\text{deg}P(n)$ of the polynomial $x_n$=$P(n)$. In order to do so, we rewrite the recurrence relation $(1)$ conveniently as
\begin{align*}
x_{n+1}+nx_n&=x_{n-1}^2\\
\text{or}\tag{2}\\
P(n+1)+nP(n)&=P^2(n-1)
\end{align*}
We observe
\begin{array}{rl}
\text{LHS has degree}&d+1\\
\text{RHS has degree}&2d
\end{array}
Since $d+1=2d$ we get $\text{deg}P=1$ and so we can choose the

3.) Ansatz: $x_n=P(n)$ with $\text{deg}P(n)=1$

\begin{align*}
x_n=an+b\qquad\qquad a,b\in\mathcal{R}
\end{align*}
With the help of the initial conditions $x_0=3$ and $x_1=4$ we find
\begin{align*}
x_0&=a\cdot0+b=3\\
x_1&=a\cdot1+b=4
\end{align*}
with the solution $a=1$ and $b=3$.
So, a closed form of the recurrence relation $(1)$ is

\begin{align*}
x_n=n+3\qquad\qquad n\geq 0
\end{align*}

