Sequence of natural numbers

Suppose $a_1,a_2,\dots, a_n,\dots$ is a sequence of natural numbers that satisfy:

$$a_{a_n} = 6n - a_n$$

for all $n$. Find $a_{2011}$.

Solution

For a fixed $n$, let $x_0 = n$
$$x_1 = a_n$$
$$x_2 = a_{x_1}$$
$$x_3 = a_{x_2}$$
$$\cdots$$
$$x_n = a_{x_{n-1}}$$

Then:
$$x_2 = a_{x_1} = a_{a_n} = 6n - a_n = 6x_0 - x_1$$
$$x_3 = a_{x_2} = a_{a_{x_1}} = 6x_1 - a_{x_1} = 6x_1 - x_2$$
In general:
$$x_{n+2} = a_{x_{n+1}} = a_{a_{x_n}} = 6x_n - a_{x_n} = 6x_n - x_{n+1}$$
$$x_{n+2} + x_{n+1} - 6x_n = 0$$

This is a second order recursion with characteristic equation $t^2 + t - 6 = 0$ with solutions $t = -3, t = 2$.

So the general term for $x_n$ is:
$$x_n = P.2^n + Q.(-3)^n$$ .
However, for $x_n$ to be positive for all $n$, then $Q$ must be zero, otherwise with large enough $n$, $x_n$ could eventually be negative. Thus $x_n = P.2^n$ for some $P$.

$a_n = x_1 = 2P = 2.P = 2x_0 = 2n$

After substituting back, we find that $a_n = 2n$ satisfies all the constraints, so we have $a_n = 2n$ for all $n$.