Explicit expression for recursively defined functions

Question

Consider a function $w(i)$, $i \in \mathbb{N}$, defined recursively by:

$w(0)=w(1)=1$, and

$w(i)={i}^{n}-\sum_{j=1}^{i-1}{i \choose j}w(j)$ for $i>1$.

Is it possible to write $w(i)$ out explicitly as a function of $i$ (i.e., with only $i$ on the right hand side), for $i>1$ ?

In general, given a recursively defined total computable function say, $f(n)$, is it always possible, in principle, to write out $f(n)$ explicitly as a function of $n$, for $n$ large enough? I suspect it's impossible. If so, what is the real reason that prevents us from doing so?

Another well known example that comes to my mind is:

$f(0)=f(1)=c$, and

$f(i)=5f(i-1)(1-f(i-1))$

where we can choose some value of $c \in (0,1)$ so that the trajectory of $f(i)$ becomes chaotic in $(0,1)$. If we could really express any recursively defined total computable function explicitly, then we could write out the chaotic trajectory in a finite, flat and non-dynamic formula, which seems strange to me. (or can we?)

---

Edit: Thank you very much for all the answers. They are really helpful.

@Joel: Is the recursive formation essential when the resulting recursive function doesn't grow faster than it's component functions ${g}_{i}$ (in your notation)? i.e., is it true that given ${g}_{i}$ and recursive function $f$ defined on them, as long as $f$ doesn't grow faster than the fastest of ${g}_{i}$, the recursive formation can be dispensed with?

@Carl: By "...it is not possible to come up with a completely explicit form for every computable function, in some fixed signature" , did you mean to write out the functions symbolically using finite, fixed set of symbols? In @Joel's interpretation, he didn't distinguish between we being able to symbolically write out exponential functions as, say ${2}^{n}$, and just taking the recursive function on multiplication as another "known" basic function ${g}_{i}$. Of course, one may just dismiss ${2}^{n}$ as a "shorthand" for the whole recursive formation, but I do feel they are not quite the same ("${2}^{n}$" is closer to what I had in mind by "explicit". I'd like to know if the distinction makes any sense in any sense).

Another question I have concerns about this "...because then by enumerating all possible forms we would get a numbering ϕ as in the theorem" But just because we can write a completely explicit form for each computable function doesn't mean we can enumerate these forms effectively, does it? If we can't, this does not contradict the theorem. Can you be more specific about this? Thanks!

Answer 1

The class of primitive recursive functions is the smallest class of functions containing the basic primitive recursive functions (zero, successor, projection) and closed under the two operations:

• composition: if $h$ and $g_1,\ldots,g_k$ are primitive recursive, so is the function $$\vec x\mapsto h(g_1(\vec x),g_2(\vec x),\ldots,g_k(\vec x)).$$
• primitive recursion: if $h$ and $g$ are primitive recursive, then so is the function $f$ defined by $$f(0,\vec x)=h(\vec x),$$ $$f(n+1,\vec x)=g(n,\vec x, f(n,\vec x)).$$

This class is extremely robust and includes all of the functions that you mention in your question (but it falls short of the class of all Turing computable functions). I interpret your question as being about the extent to which we might hope to eliminate the recursion scheme, and still arrive at the same class of functions.

One easy observation, of course, is that we cannot simply eliminate the recursion scheme as is and still get all primitive recursive functions. For example, even if we add addition and multiplication as basic functions, then the composition scheme will remain inside the class of polynomial functions. But we can easily define the exponential function $n\mapsto 2^n$ by recursion over that class, and this does not have polynomial growth.

More generally, let us consider whether we might add finitely many additional, powerful primitive recursive functions $g_1,\ldots,g_k$ as basic, and then close only under composition. This interpretation of the question would be: can we arrange that this class is closed under definition by recursion? In other words, is every function definable by recursion using those functions and their compositions already expressible as a term in the language using only those functions (that is, as a composition)?

The answer to this more general version of the question is still no. For any finitely many primitive recursive functions $g_1,\ldots,g_k$, the closure of it under composition is strictly smaller than the closure of it under composition and definition by recursion. Specifically, there will be a primitive recursive function $f$, defined by one or more recursions over those $g_i$ and the usual basic functions, which has a higher growth rate than any individual term in those functions. This can be proved by using a high enough level function $A_n$ of the Ackermann function, because whenever a collection of functions is dominated by $A_n$, then all terms in those functions are dominated by $A_{n+1}$.

Answer 2

With regard to the general question, I defer to Joel Hamkins's answer. For your specific function, though, the first few cases give

$$\begin{align} w(2) &= 2^n - 2 \\\ w(3) &= 3^n -3\cdot 2^n + 3\\\ w(4) &= 4^n - 4\cdot 3^n + 6\cdot 2^n - 4\\\ w(5) &= 5^n - 5\cdot 4^n + 10\cdot 3^n - 10\cdot 2^n + 5 \end{align}$$

This suggests the explicit formula (where by "explicit" I just mean that the function $w$ doesn't appear on the right hand side)

$$w(i) = \sum_{j=0}^{i-1} (-1)^j(i-j)^n{i \choose j}$$

which I suspect (without taking time to verify) can be proved by straightforward induction.

A minor additional note: The OP's second example does not have chaotic trajectories. Because the coefficient 5 is greater than 4, the typical trajectory quickly escapes the unit interval and henceforth heads for $-\infty$.

Added 12/19/11: An elementary mathoverflow question that was opened and closed yesterday made me realize there's an interpretation for the function $w(i)$ that makes it easy to see the equivalence of the OP's recursive formula and the "explicit" formula I came up with: The function $w$ counts the number of maps from a set of $n$ objects onto a set of $i$ objects (with $n$ assumed greater than or equal to $i$). The OP's recursive formula does the count by starting with the number of all maps ($i^n$) and subtracting the number that are mappings onto subsets of size $j$ for $j=1$ to $i-1$. My explicit formula is an inclusion-exclusion count of all maps (not necessarily onto) from a set of size $n$ to sets of size $i-j$. The only little mystery from this point of view is why the equivalence works for all $n$, not just $n\ge i$.

Answer 3

To follow up on Joel Hamkins' answer, the fundamental obstruction here is totality. Explicit definitions are always going to give total functions. The reason that recursion is so powerful for defining functions is that it is possible to make partial functions, e.g. $$ f(0) := 0 \qquad f(2n+2) := f(2n) \qquad f(2n+1) := f(2n+3) $$

The following is a standard theorem.

Theorem. Let $C$ be a countable system of total computable functions $\mathbb{N} \to \mathbb{N}$ with the property

• There is a numbering $\phi_i\colon \mathbb{N} \to C$ such that every $f \in C$ is of the form $\phi_i$ for at least one $i$, and there is a uniform way to compute $\phi_i(j)$ given just $i$ and $j$.

Then $C$ does not include all total computable functions from $\mathbb{N}$ to $\mathbb{N}$.

Proof. Diagonalization.

In the context of this question, the philosophical meaning of this theorem is that it is not possible to come up with a completely explicit form for every computable function, in some fixed signature, because then by enumerating all possible forms we would get a numbering $\phi$ as in the theorem.

The closest we can hope for in terms of an explicit form for all total computable functions is something like Kleene normal form, but this still includes an unbounded search. Kleene's normal form theorem says that there is a primitive recursive function $U$ and a primitive recursive relation $T$ such that for every computable function $f$ there is an $e$ such that for all $i$, $$ f(i) \simeq U(\mu s . T(e,i,s)). $$ where $\mu$ is the unbounded search operator.

Answer 4

There is an easy inversion formula for $$a(k)=\sum_{j=0}^k\Big({k\atop j}\Big)b(j)\, ,$$ namely, $$b(k)=\sum_{j=0}^k (-1)^{k-j}\Big({k\atop j}\Big)a(j)\, ,$$ and in your case ($a(k):=k^n$) this produce the formula shown by Barry. You can see and prove it in several ways: The inverse matrix of the triangular matrix whose entries are the binomial coefficients. Or an identity between suitable generating functions. Also, as an instance of the inclusion-exclusion formula. I'm quite sure you may find nice hints in Concrete Mathematics by Graham, Knuth, and Patashnik.