Generating Explicit function from Recursive Equations with Quadratic

Question

Given the recursive function:

$$ U(0)=2\\ U(n)={U(n-1)}^{2}+1 $$

How do I generate a explicit function? Please and Thank you!

Answer 1

Note the recurrence relation is non-linear (involving $U_{n-1}^2$) and there is no general method for obtaining closed-form solutions of general non-linear relations. In some cases the closed-form solutions depend on the actual relation and do not generalise.

For your example, it is a kind of quadratic map (second-order recurrence relation) and its terms and series are discussed here here as OES A003095 and here

[..]When done, you have $x_{n+1} = x_n^2 + c$. These have predictable behavior as far as size. [..]however, there are only two cases that can be solved in closed form

(..from same..)

For $c=0$ the closed-form solution is

$$U_n = U_0^{2^n}$$

If $U_0 > 2$ and $U_{n+1} = U_n^2 -2$ then $$U_n = A^{2^n} + B^{2^n}$$ with $$A = \frac{U_0 + \sqrt{U_0^2 - 4}}{2}$$ $$B = \frac{U_0 - \sqrt{U_0^2 - 4}}{2}$$ $A+B = U_0$ and $AB = 1$ (by factoring the relation using the quadratic equation)

Follows a reference of general methods:

One of the methods for solving linear-relations and some non-linear relations is using transforms (for example z-transform) or the use of formal series, also called generating functions (one can define a region where the formal series are analytic as well). See for example generatingfunctionology

Then using these methods the process goes as following:

1. Define $F_U(z) = \sum_{n=0}^{\infty}U_nz^n$. The recursive series now corresponds to the coefficients of the formal series (generating function)

2. Transform the recursion relation into a relation involving the generating function $F_U(z)$, i.e

a. $U_{n+1}=U_n^2+1$ (shifted index $n$)

b. $\sum_n U_nz^n = F_U(z)$, $\sum_n U_{n+1}z^n = \sum_n U_{n+1}z^{n+1}/z = F_U(z)/z$, $\sum_n 1 \times z^n = \frac{1}{1-z}$ (geometric series)

c. Here the non-linear term $U_n^2$ is not handled easily.

3. Get the $n$th term of the generating function (e.g using derivatives) and the general $n$th term of the series $U_n$ is given.

Another related method is to assume a form of the general term (which is infered from the recurence relation), e.g $U_n = k \times n^a \times b^n$ and use the relation and initial conditions to find the parameters $k$, $a$, $b$ so as to satisfy all the conditions. In some cases more than one attainable set of parameters may be found (since non-linearity is introduced) and this implies no closed-form solution.