Characteristic equation of a recurrence relation?

Question

I am trying to find the general term of the following recurrence relation:

$$a_{n + 1} = \frac{1}{2}(a_{n} + \frac{1}{a_{n}})$$

where $a_1 = 3$. I'm failing to write the characteristic equation.

Answer 1

This is the recurrence relation of the Heron method for computing the square root of $1$, also seen as the application of Newton's method to $a^2=1$.

As is shown by the relation

$$\frac{a_n-1}{a_n+1}=\frac1{2^{2^{n}}},$$

it has quadratic convergence and virtually equals $1$ for all $n$.

---

Indeed,

$$\frac{a_{n+1}-1}{a_{n+1}+1}=\frac{\dfrac{a_n^2-2a_n+1}{2a_n}}{\dfrac{a_n^2+2a_n+1}{2a_n}}=\left(\frac{a_n-1}{a_n+1}\right)^2$$ and by induction

$$\frac{a_{n}-1}{a_{n}+1}=\left(\frac{a_0-1}{a_0+1}\right)^{2^n},$$

and $$a_n=1+\frac2{2^{2^n}-1}.$$

Answer 2

As far as I know, characteristic equations are used for linear recurrence relations. This one is nonlinear.

EDIT: There is, however, a nice closed-form solution.

Hint: $$\coth(2x) = \dfrac{1}{2} \left(\coth(x) + \frac{1}{\coth(x)}\right) $$

Answer 3

Here is what I came upon:

If we have: $a_{n} = \frac{1}{2}(a_{n} + \frac{\lambda^2}{a_{n}})$, then it holds that: $\frac{a_{n} - \lambda}{a_{n} + \lambda} = (\frac{a_{1} - \lambda}{a_{1} + \lambda})^{2^{n-1}}$, solving for $a_{n}$ from the above example we have:

$$\frac{a_{n} - 2}{a_{n} + 2} = (\frac{3 - 2}{3 + 2})^{2^{n-1}}$$

$$a_n - 2 = \frac{a_n + 2}{5^{2^{n-1}}}$$

$$a_n5^{2^{n-1}} - a_n - 2.5^{2^{n-1}} - 2 = 0$$

$$a_n(5^{2^{n-1}} - 1) - 2(5^{2^{n-1}} + 1) = 0$$

$$a_n = 2\frac{5^{2^{n-1}} + 1}{5^{2^{n-1}} - 1}$$