, 2011

For generality, let $x = 2011$. Expanding the first few terms of the sequence with the recurrence $u_n = x u_{n-1} - u_{n-2}$ we find
$$\begin{aligned} u_0 &= 0, \quad u_1 = 1, \quad u_2 = x \\ u_3 &= x^2 - 1 = u_2^2 - u_1^2 \\ u_4 &= x^3 - 2x = 2u_3u_2 - x u_2^2 \\ u_5 &= x^4 - 3x^2 + 1 = u_3^2 - u_2^2 \\ u_6 &= x^5 - 4x^3 + 2x = 2u_4u_3 - x u_3^2. \end{aligned}$$
From this we can conjecture that $u_{2n} = 2u_n u_{n+1} - x u_n^2$ and $u_{2n+1} = u_{n+1}^2 - u_n^2$ for $n > 0$. We now prove this by induction. Firstly note that it holds for $n = 1$. Now assume it holds up to $n$, and we will show that it holds for $n + 1$.
$$\begin{aligned} u_{2n+2} &= x u_{2n+1} - u_{2n} \\ &= x(u_{n+1}^2 - u_n^2) - (2u_n u_{n+1} - x u_n^2) \\ &= x u_{n+1}^2 - 2u_n u_{n+1} + x u_n^2 \\ &= 2u_{n+1}(x u_{n+1} - u_n) - x u_{n+1}^2 \\ &= 2u_{n+1}u_{n+2} - x u_{n+1}^2 \end{aligned}$$
and
$$u_{2n+3} = x u_{2n+2} - u_{2n+1}$$
$$\begin{align*} &= x(2u_{n+1}u_{n+2} - x u_{n+1}^2) - (u_{n+1}^2 - u_n^2) \\ &= -x^2 u_{n+1}^2 + x(2u_{n+1}u_{n+2}) + u_n^2 - u_{n+1}^2 \\ &= x^2 u_{n+1}^2 - 2x u_{n+1}u_n + u_n^2 - u_{n+1}^2 \\ &= (x u_{n+1} - u_n)^2 - u_{n+1}^2 \\ &= u_{n+2}^2 - u_{n+1}^2. \end{align*}$$
The result thus follows by induction.

The above identities suggest that we may be able to find explicit factorisations, but for a factorisation to prove that a number is not prime it is necessary for the factors to be greater than 1. So let us show that $u_i - u_{i-1} \ge 2$ for all $i \ge 2$. For $i = 2$ the result holds by inspection. Suppose it holds for some $i$. Then $u_{i+1} - u_i = 2011u_i - u_{i-1} - u_i = 2010u_i - u_{i-1} \ge u_i - u_{i-1} \ge 2$. The result again follows by induction.

Inspecting the first few terms, we see that $u_2 = 2011$ is prime. Let us show that there are no other primes. $u_0$ and $u_1$ are non-prime by inspection. For $n \ge 1$, $u_{2n+1} = u_{n+1}^2 - u_n^2 = (u_{n+1} - u_n)(u_{n+1} + u_n)$. By the inequality above, both factors are at least 2 and so $u_{2n+1}$ is not prime. For $n > 1$, $u_{2n} = u_n(2u_{n+1} - 2011u_n)$. The first term is clearly greater than 1, and the second equals $u_{n+1} - u_{n-1} \ge u_{n+1} - u_n \ge 2$.

Thus, $u_2 = 2011$ is the only prime in the sequence.