# Nonlinear recurrence sequence systems of order one

We wish to study integer recurrence systems of the form:

\left\{\begin{align} f_1(n) & = P_1\big(f_1(n-1), f_2(n-1), \ldots, f_k(n-1)\big)\\ f_2(n) & = P_2\big(f_1(n-1), f_2(n-1), \ldots, f_k(n-1)\big)\\ \vdots\\ f_k(n) & = P_k\big(f_1(n-1), f_2(n-1), \ldots, f_k(n-1)\big) \end{align}\right.

where the $P_i$'s are polynomials in $\mathbb{N}[x_1, x_2, \ldots, x_k]$, and given initial values for $f_i(0) \in \mathbb{N}$.

Question: Does there exist a characterization of the functions $f_1$ that can be obtained this way? Tools to show that some functions are not expressible?

Examples: The factorial function $n \mapsto n!$ is the function $f_1$ in:

\left\{\begin{align} f_1(n) & = f_2(n - 1) \times f_1(n - 1) & \text{ and } f_1(0) = 1\\ f_2(n) & = f_2(n-1) + 1 & \text{ and } f_2(0) = 1 \end{align}\right.

The square function is easy too, taking $f_1(n) = (f_2(n-1))^2$, but we believe that the function $n \mapsto (n^2)!$ is not doable.

We can have (double) exponential behaviors, for instance $n \mapsto 2^{2^n}$:

$$f_1(n+1) = f_1(n)^2 \text{ and } f_1(0) = 2\enspace,$$

or $n \mapsto 2^{n^2}$.

• I'm not sure I understand. What does it mean $n\mapsto n!$ is expressible by the system $(f_1,f_2)$? – T. Amdeberhan Oct 5 '16 at 12:33
• @T.Amdeberhan: It means it is the $f_1$ function defined by the system. I've edited the question, thanks. – Michaël Oct 5 '16 at 12:39