# Closed Form of Recursion $a_n = \frac{6}{a_{n-1}-1}$

Given that $a_0=2$ and $a_n = \frac{6}{a_{n-1}-1}$, find a closed form for $a_n$.

I tried listing out the first few values of $a_n: 2, 6, 6/5, 30, 6/29$, but no pattern came out.

• How are you supposed to guess this, totally escapes me. – Git Gud Sep 21 '14 at 3:17
• @GitGud: The best that I can suggest is that there's an attracting fixed point at $a=-2$, which might inspire writing $$a_n+2=\dfrac{2a_{n-1}+4}{a_{n-1}-1}=\dfrac{2(a_{n-1}+2)}{(a_{n-1}+2)-3} {\implies} \dfrac{1}{a_n+2}=\dfrac{1}{2}-\dfrac{3/2}{a_{n-1}+2}.$$ But while that does give a soluble form, I don't trust that I would have noticed it without having seen the answer first! – Semiclassical Sep 21 '14 at 3:59
• @Semiclassical. This makes the problem really simple. Thanks. – Claude Leibovici Sep 21 '14 at 5:18

The function $f(x) = \dfrac{6}{x-1}$ is a fractional linear transformation.
Composition of these corresponds to matrix multiplication: $$\text{if}\ T(x) = \dfrac{a_{11} x + a_{12 }}{a_{21} x + a_{22}} \ \text{and} \ S(x) = \dfrac{b_{11} x + b_{12}}{b_{21} x + b_{22}}$$ $$\text{then}\ T(S(x)) = \dfrac{c_{11} x + c_{12}}{c_{21} x + c_{22}}\ \text{where}\ \pmatrix{c_{11} & c_{12}\cr c_{21} & c_{22}\cr} = \pmatrix{a_{11} & a_{12}\cr a_{21} & a_{22}\cr} \pmatrix{b_{11} & b_{12}\cr b_{21} & b_{22}\cr}$$ In your case the matrix is $$M = \pmatrix{0 & 6\cr 1 & -1\cr}$$ and we'd like to find a closed form for its powers. We diagonalize the matrix as $M = E D E^{-1}$ where $$E = \pmatrix{-2 & 3\cr 1 & 1\cr}, \ D = \pmatrix{-3 & 0\cr 0 & 2\cr},\ E^{-1} = \dfrac{1}{5}\pmatrix{-1 & 3\cr 1 & 2\cr}$$ so $$M^n = E D^n E^{-1} =\dfrac{1}{5} \left( \begin {array}{cc} 2\, \left( -3 \right) ^{n}+3\cdot{2}^{n}&-6\, \left( -3 \right) ^{n}+6\cdot{2}^{n}\\ - \left( -3 \right) ^{n}+{2}^{n}&3\, \left( -3 \right) ^{n}+2\cdot{2}^{n} \end {array} \right)$$ i.e. $$a_n = \left(\dfrac{ (2 \left( -3 \right) ^{n}+3\cdot{2}^{n}) \cdot 2 -6 \left( -3 \right) ^{n}+6\cdot{2}^{n}}{ \left(- \left( -3 \right) ^{n}+{2}^{n}\right) \cdot 2 + 3 \left( -3 \right) ^{n}+2\cdot{2}^{n} } \right) = \dfrac{-2(-3)^n + 12 \cdot 2^n}{(-3)^n + 4 \cdot 2^n}$$

• Alternatively, notice that all matrices satisfy their own characteristic polynomial, so that means $M^2=6I-M\implies M^{n+2}=6M^n-M^{n+1}$. The solution of that recurrence relation is $M^n=\frac15 2^n(M+3I)-(-3)^n(M-2I)$ – Pauly B Sep 21 '14 at 5:09

I think that Semiclassical proposed a very nice solution rewriting $$a_n = \frac{6}{a_{n-1}-1}$$ $$\dfrac{1}{a_n+2}=\dfrac{1}{2}-\dfrac{3/2}{a_{n-1}+2}$$ So, let us define $$b_n=\dfrac{1}{a_n+2}$$ (with $b_0=\dfrac{1}{4}$); so the recurrence equation is simply $$b_n=\dfrac{1}{4}-\dfrac{3}{2}b_{n-1}$$ from which $$b_n=\frac{1}{20} \left(4+\left(-\frac{3}{2}\right)^n\right)$$ and then $$a_n=\frac{20}{4+\left(-\frac{3}{2}\right)^n}-2$$ as shown by Git Gud.

• I'm of two minds with this proof, as my comment above indicated: While it definitely works as a very direct proof, I can't convince myself I'd have noticed it without seeing the final result, which is dissatisfying... – Semiclassical Sep 21 '14 at 5:21
• Isn't a form of genius ? Be sure I am not kidding ! Cheers :-) – Claude Leibovici Sep 21 '14 at 5:30

Start with $a_n=\frac6{a_{n-1}-1}$, and replace $a_{n-1}$ with $\frac6{a_{n-2}-1}$. We obtain

$$a_n=\frac6{\frac6{a_{n-2}-1}-1}=\frac{6(1-a_{n-2})}{a_{n-2}-7}$$

Doing this again with $a_{n-2}=\frac6{a_{n-3}-1}$ and so forth, we get

$$a_n=\frac{6(7-a_{n-3})}{7a_{n-3}-13}=\frac{6(13-7a_{n-4})}{13a_{n-4}-55}=\frac{6(55-13a_{n-5})}{55a_{n-5}-133}$$

It would seem then, that

$$a_n=\frac{6(F_{k-1}-F_{k-2}a_{n-k})}{F_{k-1}a_{n-k}-F_k}$$

For some coefficients $F_k$. But what is $F_k$? To find out replace $a_{n-k}$ with $\frac6{a_{n-k-1}-1}$, then

$$a_n=\frac{6(F_{k-1}-F_{k-2}a_{n-k})}{F_{k-1}a_{n-k}-F_k}=\frac{6(F_{k-1}-F_{k-2}\frac6{a_{n-k-1}-1})}{F_{k-1}\frac6{a_{n-k-1}-1}-F_k}=\frac{6((6F_{k-2}+F_{k-1})-F_{k-1}a_{n-k-1})}{F_{k}a_{n-k-1}-(6F_{k-2}+F_{k-1})}=\frac{6(F_{k}-F_{k-1}a_{n-k-1})}{F_{k}a_{n-k-1}-F_{k+1}}$$

So it would seem that $F_k=F_{k-1}+6F_{k-2}$. By noting that $F_1=1,F_2=7$, we have the solution (I presume you can solve it yourself) $$F_k=\frac25(-2)^k+\frac353^k$$

By plugging in $k=n$, we now have

$$a_n=\frac{6(F_{n-1}-F_{n-2}a_{0})}{F_{n-1}a_{0}-F_n}=\frac{6(F_{n-1}-2F_{n-2})}{2F_{n-1}-F_n}$$

which eventually simplifies to $$a_n=3-\frac{5}{4\left(-\frac23\right)^n+1}$$

which fits both $a_0=2$ and $a_n=\frac6{a_{n-1}-1}$, so the expression is indeed correct.