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

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,

1. Other than Linear Homogeneous Recurrence Relation, and Linear non Homogeneous relation with constant coefficients, what other solvable types of Linear Relations are out there.
2. Other than making conjecture like what I did above, can someone else recommend a technique of attacking the question above?

Answer 1

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*}