# How to solve this nonlinear functional recurrence

I study two similar nonlinear functional recurrence systems, given by

$$P_\pm:\qquad f_n\cdot(1\pm g f_{n-1}) = g\mp(1+2g)f_{n-1} \qquad (n>0)$$ and $$f_0=g$$

Here $f_n$ and $g$ are functions of one variable with

$$g(z)=\frac{z}{1-z}$$

I try to find the solution of $P_+$, but so far, only was able to solve $P_-$. I am grateful for any ideas.

What I tried so far: Although I am not sure if this goes into the right direction, here is how I did $P_-$: Substitute $q_n = (1-gf_n)/(1+g)$ and we obtain

$$q_n = 2-\frac{1}{q_{n-1}}\qquad(n>0)$$ with $$q_0 =1-g$$

Just by "looking at" the first functions $q_n$, it seems that

$q_n(z)=\frac{z(n+2)-1}{z(n+1)-1},$ which can indeed be verified to fulfill the recurrence.

However, for the system $P_+$, the analogous substitution $q_n=(1+gf_n)/(1+g)$ yields the slightly different recurrence $$q_n=\frac{1}{q_{n-1}}-2z$$ with $$q_0 = 1+g-2z.$$

I have no idea how to solve this, but one might exploit the knowledge about $P_-$. Finding a transformation between those very similar problems would allow to express the solutions of $P_+$ by those of $P_-$.

I finally found the answer, one can solve both problems

$$(P_-):\qquad q_n = 2-\frac{1}{q_{n-1}},\qquad q_0=1-g\\ (P_+):\qquad q_n=\frac{1}{q_{n-1}}-2z,\qquad q_0=1+g-2z$$

with a substitution also known from the algebraic Riccati equation (see, e.g. here),

$$q_n=\frac{a_{n+1}}{a_n},\qquad a_1=q_0, \qquad a_0=1.$$

This transforms the problems into linear equations

$$(P_-):\qquad a_n = 2a_{n-1}-a_{n-2},\\ (P_+):\qquad a_n = a_{n-2}-2za_{n-1}.$$

These can be solved by standard methods, e.g., introducing a generating function which in addition to $z$ depends on a new variable, that corresponds to the index $n$. The final solutions are

$$(P_+):\qquad q_n(z)=-\frac{x_+(z)^{n+2}(1-\Gamma(z))-x_-(z)^{n+2}(1+\Gamma(z))}{x_+(z)^{n+1}(1-\Gamma(z))-x_-(z)^{n+1}(1+\Gamma(z))}$$

where $$q_\pm(z) := z\pm\Gamma(z),\qquad \Gamma(z):=\sqrt{1+z^2},$$ and $$(P_-):\qquad q_n(z) = \frac{z(n+2)-1}{z(n+1)-1}.$$