2
$\begingroup$

Possible Duplicate:
Help on a rational recursive relation: $T\[n+1\]=\frac{E\[n+1\](D+T\[n\])}{E\[n+1\]+D+T\[n\]}$

I'm trying to understand how one solves the recurrence relation in the title:

$a_n = \frac{g}{1-g \, a_{n-1}}$

with $a_0 = x$.

I know the solution is

$a_n = a \, \frac{1- xa + a^{2n-1}(x-a)}{1- xa + a^{2n+1}(x-a)}$

where $a$ is the fixed point of the iteration for any $x \in (-1,1)$, but I am having trouble deriving this solution.

I have that $|g|<1/2$ and $|x|<1$, and with this you can prove that $f(x) = a_1(x)$ is a contraction mapping on $(-1,1)$ and thus has the unique fixed point

$a = \frac{1- \sqrt{1-4g^2}}{2g}$.

But I do not know what to do from there as I do not have any experience with non-linear recurrence relations.

  • 0
    This is a Ricatti recurrence. The substitution $x_{n + 1}/x_n = 1 - g a_n$ (use $x_0 = 1$, it really doesn't matter, get $x_1 = a_0$) reduces it to a linear second order recurrence, easy to solve.2013-05-26

0 Answers 0