Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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? –  Sush 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
2  
@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
add comment

3 Answers

up vote 6 down vote accepted

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

share|improve this answer
3  
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}$? –  Sush Nov 29 '13 at 10:11
1  
@Sush: induction –  Jean-Claude Arbaut Nov 29 '13 at 10:18
    
@arbautjc, thanks. –  Sush Nov 29 '13 at 10:26
add comment

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.

share|improve this answer
1  
Your answer is too much good . Thanks –  Way to infinity Nov 29 '13 at 10:02
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.