# What is the value of $a_{2009}$

I have the following sequence :

$a_0 = 3$

$a_n = 2 + a_0 a_1 a_2\text{ ...}a_{n-1}$

How can I find the value of $a_{2009}$ ?

-
HINT: $a_{n+1}=a_n(a_n-2)+2$ – LeeNeverGup Nov 29 '13 at 9:32
I have find this relation . But after that I cant proceed – Way to infinity Nov 29 '13 at 9:34
@LeeNeverGup, how did you find this relation? – Silent Nov 29 '13 at 9:35
@Sush Hint: It's immediate from the recurrence relation (subtract 2, from it, to begin with) – Jean-Claude Arbaut Nov 29 '13 at 9:36
@Sush $a_n-2=a_0a_1...a_{n-1}$. Then $a_n(a_n-2)+2=a_0a_1...a_{n-1}a_n+2=a_{n+1}$ – LeeNeverGup Nov 29 '13 at 9:37

Rewrite $a_{n+1} = a_n(a_n-2) + 2$ as $a_{n+1} - 1 = (a_n -1)^2$

To clarify further.

If $b_n = a_n -1$, then we have $b_{n+1} = (b_n)^2$, and so $b_{n} = (b_0)^{2^n}$.

-
And then put $b_n=a_n-1$? – LeeNeverGup Nov 29 '13 at 9:40
@LeeNeverGup: Yes... – Aryabhata Nov 29 '13 at 9:42
@Aryabhata, how did you derive from $b_{n+1} = (b_n)^2$ the $b_{n} = (b_0)^{2^n}$? – Silent Nov 29 '13 at 10:11
@Sush: induction – Jean-Claude Arbaut Nov 29 '13 at 10:18
@arbautjc, thanks. – Silent Nov 29 '13 at 10:26

First, you can prove $a_{n+1}=a_n(a_n-2)+2$, this way:

The recurrence formula gives you

$$a_n-2=a_0a_1...a_{n-1}$$

Thus, multiplying by $a_n$,

$$a_n(a_n-2)=a_0a_1...a_n=a_{n+1}-2$$

Then, you can prove $a_n=2^{2^n}+1$ (that is, they are Fermat numbers), by induction.

It's true for $a_0=3=2^{2^0}+1$.

If it's true for $a_n$, then

$$a_{n+1}=a_n(a_n-2)+2=\left(2^{2^n}+1\right) \left(2^{2^n}-1\right) + 2$$ $$=2^{2^n\cdot 2}-1+2=2^{2^{n+1}}+1$$

Hence it's true for all $n$.

Note: you can deduce immediately that Fermat numbers are coprime to each other, using the recurrence formula. Indeed, it proves that a common divisor of $a_n$ and $a_k$ for $k<n$, must be also a divisor of $2$, thus it's $1$, since they are odd.

-
Your answer is too much good . Thanks – Way to infinity Nov 29 '13 at 10:02

\begin{aligned} a_0 &= 3\\ a_1 &= 2 + a_0 = 2 + 3\\ a_2 &= 2 + a_1 a_0 = 2 + ( 2 + a_0)a_0 = 2 + 2a_0 +a_0^2\overset{a_0 = 3}{=}2+ 2\cdot 3 +3^2\\ a_3 &= 2 + a_2 a_1 a_0 = \dots = 2 + ( 2+ (2 +a_0)a_0)a_0 \\&= 2 + 2 a_0 + 2 a_0^2 + a_0^3 \overset{a_0 = 3}{=} 2 + 2 \cdot 3 + 2 \cdot 3^2 + 3^3 \overset{(*)}{=} 2\sum_{k=0}^2 3^k+3^3 \end{aligned} Look at the last equation marked with the asterisk $(*)$. Think of a formula for induction... I'll leave this to you. Shouldn't be hard ;). To be more precise: $$a_3 = 2\sum_{k=0}^2 3^k+3^3$$ and analogous equations should hold for $a_n,\,n\geq 1$. The inductive proof will follow easily if you look at the mapping $x\in\mathbb{R}\mapsto f(x):=2 + x 3$, because as you can see above, for $n\geq1$, $a_n$ has a form easily expressed with $f$.

Very late edit:
Once you have proven the analogous formula, getting $a_{2009}$ is as simple as pasting into the formula and calculating the result.

-