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$.

## Wednesday, March 23, 2011

### Sequence of natural numbers

Labels:
Algebra,
integers,
iterative,
natural numbers,
positive integers,
recursion,
sequence

Subscribe to:
Post Comments (Atom)

## No comments:

## Post a Comment