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}$.

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.