What is the value of $ a_{2009}$

Question

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} $ ?

Answer 1

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

Answer 2

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.

Answer 3

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