recursive to explicit sequence

Question

I am trying to find the explicit formula for the following recursion:

$$a_{1}=3,\quad a_{n}=3- \frac{1}{a_{n-1}},\quad n \in \mathbb N,n>1$$

I tried in many ways but I cannot find any solution.

Can you help me?

Answer 1

Here is a straightforward (if somewhat ugly) approach. Start by gathering some data to see what’s going on:

$$\begin{align*} a_n&=3-\frac1{a_{n-1}}\\\\ &=\frac{3a_{n-1}-1}{a_{n-1}-0}=\frac{\frac{9a_{n-2}-3}{a_{n-2}}-1}{\frac{3a_{n-2}-1}{a_{n-2}}}\\\\ &=\frac{8a_{n-2}-3}{3a_{n-2}-1}=\frac{\frac{24a_{n-3}-8}{a_{n-3}}-3}{\frac{9a_{n-3}-3}{a_{n-3}}-1}\\\\ &=\frac{21a_{n-3}-8}{8a_{n-3}-3}=\frac{\frac{63a_{n-4}-21}{a_{n-4}}-8}{\frac{24a_{n-4}-8}{a_{n-4}}-3}\\\\ &=\frac{55a_{n-4}-21}{21a_{n-4}-8} \end{align*}$$

The four coefficients in those simplified fractions are clearly growing in a very regular fashion: ignoring signs, they are $0,1,3,8,21$, and $55$. If we call these $c_0,c_1,c_2,c_3,c_4$, and $c_5$, it should be reasonably clear that in general $c_{n+1}=3c_n-c_{n-1}$, and

$$a_n=\frac{c_{k+1}a_{n-k}-c_k}{c_ka_{n-k}-c_{k-1}}\;.$$

Having guessed this formula, you can then prove it by induction and then take $k=n-1$ and get

$$a_n=\frac{3c_n-c_{n-1}}{3c_{n-1}-c_{n-2}}\;.$$

A closed form for $a_n$ can then be found by solving the recurrence

$$\left\{\begin{align*} &c_0=0,c_1=1\\ &c_n=3c_{n-1}-c_{n-2}\text{ for }n\ge 2 \end{align*}\right.$$

to get a closed form. That’s a much more straightforward problem.

Answer 2

$$\dfrac{a_n - p}{a_n - q} = \dfrac{3- \dfrac{1}{a_{n-1}} - p}{3- \dfrac{1}{a_{n-1}} - q} = \dfrac{(3-p)a_{n-1} - 1}{(3-q)a_{n-1}-1} = \dfrac{3-p}{3-q}\dfrac{a_{n-1} -\dfrac{1}{3-p}}{a_{n-1} -\dfrac{1}{3-q}}$$

Take $p = \frac{1}{3-p}$ and $q = \frac{1}{3-q}$, i.e. take $p,q$ as the two different solutions of $x^2 - 3x + 1 = 0$

we get $$\dfrac{a_n - p}{a_n - q} = \left(\dfrac{3-p}{3-q}\right)^{n-1}\dfrac{a_1 - p}{a_1 - q}$$

Now solve for $a_n$ as function of $p,q,n$ and plug in the values of $p$ and $q$

Answer 3

3
2.666666667
2.625
2.619047619
2.618181818
2.618055556
2.618037135
2.618034448
2.618034056
2.618033999
2.61803399
2.618033989
2.618033989
2.618033989
2.618033989
2.618033989
2.618033989
2.618033989
2.618033989
2.618033989
2.618033989
2.618033989
2.618033989
2.618033989
2.618033989
2.618033989
2.618033989
2.618033989
it seems to be converge