1. ## Nonlinear recurrence relations

Hi. This is my first post here so I hope I've posted in the right place. My question concerns finding closed forms of nonlinear recurrence relations such as the following:

$a_1=a$
$a_{n+1}=a_n^2-1\ \mbox{for}\ n\geqslant1$

This one is both nonlinear and nonhomogeneous. The even terms do form a homogeneous recurrence relation, which is nonetheless still nonlinear. Are there general methods for solving particular types of nonlinear recurrence relations? I've tried googling but the results aren't very helpful.

2. ## Re: Nonlinear recurrence relations

Generally Ricatti equations can be useful in solving nonlinear recurrence relations; however, I don't think they apply to your problem. I had a similar problem to solve for my thesis. I solved it as follows:

$x\cdot f(x+1) - f^2(x) +1 = 0$

This is a first order, non-linear difference equation with variable coefficients. Commonly used solution methods such as Ricatti Equations do not seem to work nicely for this example. However, by inspection, it seems that the solution is a linear function $f(x)=mx+b$. From the definition, $f(0)=1$. This gives that $f(0)=0+b=1$; hence, $b=1$. Thus we have $f(x)=mx+1$. Substituting this into the difference equation, we get

$x\cdot (m(x+1)+1)-(mx+1)^2+1$
$=mx^2+mx+x-m^2x^2 -2mx -1 +1$
$=mx^2-mx+x-m^2x^2=0$

Furthermore, the above holds for all $x \in \mathbb{R}$, so we can choose an $x$ to solve for $m$. Take $x=1$ to get

$m(1)^2-m(1)+(1)-m^2(1)^2$
$=m-m+1-m^2$
$=1-m^2=0$
$\Longrightarrow 1=m^2 \Longrightarrow m=\pm 1.$

Taking $m=-1$ would yield negative solutions which is not possible; hence, $m=1$ and $f(x)=x+1$. Thus we have that $x+1$ is a particular solution to the difference equation. Hence, we get $\sqrt{1+2\sqrt{1+3\sqrt{1+...}}}=f(2)=2+1=3.$