Recurrence relation problem

If $a$ is a sequence defined recursively by $a_{n+1} = \frac{a_n-1}{a_n+1}$ and $a_1=1389$ then can you find what $a_{2000}$ and $a_{2001}$ are?

it would be really appreciated if you could give me some pointers on how to solve this mathematically.

(Obviously using the formula to find the values one by one is possible but is extremely tedious, actually i wrote a simple piece of software to calculate it and the answers were a little odd, $a_{2000}=-1.0014409$ and $a_{2001}=1389.0381$)

By the way here is the code i used for calculating the answers (it's in java) :

float answer = 1389;

for (int i = 2; i <= 2001; i++) {

answer = (answer - 1) / (answer + 1);

}

(i ran it two times the first time i set the loop condition to 2000.)

• Through $a_1$, you know the first term 'a' of the AP. find $a_2$ from the formula $a_{n+1}=\frac{a_n-1}{a_n+1}$ and compare it with $a_2=a+d$ to find the common difference d. Then find the term you want to find – Dinesh Oct 6 '14 at 12:11
• Or else, solve the given recurrence to find its general term – Dinesh Oct 6 '14 at 12:12
• oh, I'm really sorry it may not be an arithmetic progression, it's just a progression the type is not defined.(English is not my native language, sorry) – Ashkan Oct 6 '14 at 12:13
• OK, You can just solve the recurrence . Hope you know how to solve them ? – Dinesh Oct 6 '14 at 12:14
• It is definitely not an arithmetic progression. $a_2 \approx 0.99856$, which would make $a_3$ either $\approx -1387$ or $\approx -0.00075$, depending on how you decide to calculate the next term. – Deepak Oct 6 '14 at 12:15

3 Answers

The fixed points of the recursion $$a\to\frac{a-1}{a+1},$$ are $\mathrm i$ and $-\mathrm i$. Even if the whole sequence $(a_n)$ is real valued, this suggests to look at the dynamics of the modified (complex) variable $$b_n=\frac{a_n-\mathrm i}{a_n+\mathrm i}.$$ Behold! It happens that $$b_{n+1}=-\mathrm i\,b_n,$$ hence $b_{n+1}=(-\mathrm i)^nb_1$ for every $n$. Furthermore, $(-\mathrm i)^4=1$ hence the sequences $(a_n)$ and $(b_n)$ have period $4$.

In particular, $a_{2001}=a_1=1389$. It remains to note that $$\frac{a_4-1}{a_4+1}=a_5=a_1,$$ to deduce $$a_{2000}=a_4=-\frac{a_1+1}{a_1-1}=-\frac{695}{694}.$$

Edit: Likewise, the recursion $$a\to\frac{a-u}{a+v},$$ is periodic with period $n$ for every starting point if and only if there exists some integer $k$ such that $$\cos^2\left(\frac{k\pi}n\right)=\frac14\frac{(1+v)^2}{u+v}.$$ If $u=v=1$, $n=4$ and $k=1$ solve this.

• Thanks for your answer but I just don't understand how we reached the conclusion that $b_{n+1}=-ib_n$, could you make your answer a little more descriptive, I'm in high school (and the education system here is not great). Thanks – Ashkan Oct 6 '14 at 12:56
• Ashkan: I am absolutely certain that you are able to reach yourself the expression $b_{n+1}=-ib_n$ from the expression of $b_n$ and the dynamics of $(a_n)$. Just grab a sheet of paper, a pencil, shut the radio or whatever... There, already half the job is done! – Did Oct 6 '14 at 13:02
• yup you were right, I get it now (it was actually pretty easy, i was just working on this question for too long I was a little frustrated with it), Thank you so much for your answer it is much appreciated. – Ashkan Oct 6 '14 at 13:31
• Is there some kind of generalization for this kind of periodic quotient recursion? – DanielV Oct 11 '14 at 6:15
• @DanielV See Edit. – Did Oct 11 '14 at 7:16

Hint: This sequence is periodic with a short period. Once you figure out the pattern for one period, you can easily jump far ahead in the sequence.

This is a simple attempt using basic algebra.

• Would the downvoter care to comment? There's probably a valid reason and I look forward to learning from it, whether it's an error or anything else. Thank you. – hypergeometric Oct 11 '14 at 17:34