3
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ How are you supposed to guess this, totally escapes me. $\endgroup$ – Git Gud Sep 21 '14 at 3:17
  • 4
    $\begingroup$ @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! $\endgroup$ – Semiclassical Sep 21 '14 at 3:59
  • $\begingroup$ @Semiclassical. This makes the problem really simple. Thanks. $\endgroup$ – Claude Leibovici Sep 21 '14 at 5:18
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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)$ $\endgroup$ – Pauly B Sep 21 '14 at 5:09
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – Semiclassical Sep 21 '14 at 5:21
  • $\begingroup$ Isn't a form of genius ? Be sure I am not kidding ! Cheers :-) $\endgroup$ – Claude Leibovici Sep 21 '14 at 5:30
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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