# Is there a recurrence relation which has no closed formula?

From what I know, it is unknown whether $$x_n=x_{n-1}^2 + 1$$ has a closed form. Is there a recurrence relation which is known to have no closed form with a proof of inexistence?

Assuming a closed form is a non recursive description using the elementary operations of addition multiplication and power, or, assuming any other good definition of "closed form".

Edit

There are similar questions out there, but the answers are a little bit going around the question.

So is there one with proof or is it unknown? And if it depends on the definition of a closed form, then what are the (or some) options? How strong can a closed form definition be to still have a recursive relation that can be proved to not being able to have its form?

Update

Because it is a big question, and I don't want to open a new small one, I think a good representative small question about this subject is: Is there a recurrence relation with a domain of the natural numbers, described by elementary functions, which has no closed form defined as:

A closed form of a recurrence relation with a domain of natural numbers is a function $$f$$ that can be described as a composition of a constant number of elementary functions without reccursion. i.e, $$f(n) = f_1(f_2( \dots (f_k(n))) \dots)$$ where $$f_i$$ is elementary for all $$1 \leq i \leq k$$

I think this definition is the most intuitive and basic.

For example, the relation $$x_n = x_{n-1}+1$$ has a closed form in this sense: $$f(n) = f_1(f_2(f_3(f_4(n))))$$

Where $$f_1$$ is division, $$f_2(n)=(n,2)$$, $$f_3$$ is multiplication and $$f_4(n) = (n,n+1)$$

Is there a recurrence relation which has no closed form in this sense?

• This example is a good candidate for an example without a closed form, but I am not aware of a proof either. – Peter Sep 21 at 18:36
• Take a look at cs.stackexchange.com/questions/27598/… – John Douma Sep 21 at 18:39
• Fix a language for closed forms, each a finite string in a countable alphabet. There are countably many forms, so enumerate them. In the spirit of Richard's paradox, define $a_n$ as the $n$th form's $n$th term $+1$. Clearly, $a_n$ is none of the original forms, but it looks like I've defined it as one. This can be resolved if you know about metalanguages, but the moral is we need to formalise what a closed form is, or at least which notation is legal in it, to properly consider some questions. I wonder whether your question is one of them. – J.G. Sep 21 at 20:55
• Much of the difficulty here depends on formalizing what a closed form is. I'm not aware of a generally accepted definition. In practice it turns out that closed forms aren't as big a deal as you might think. – Qiaochu Yuan Sep 21 at 21:43
• Hmm, I'm not sure whether I get you correctly. There is a powerseries for the "Schroeder-function" associtated to $f(x)=1+x^2$ such that we can use it (and its inverse) to compute iterates by iteration-height $h$ as argument. This can -for a given iteration-initialization-value $x_0$ be made in a single power-series for $h$ as argument. Don't know, whether one would call such a powerseres a closed form, after $\exp(x)$ is also computable by a power series and yet is assumed to be a "closed-form". – Gottfried Helms Sep 22 at 10:23

Here is a remark I put in a paper [1, p. 5828] of mine, which I got from an anonymous referee of that paper:

We may resonably interpret "having closed form" as "being differentiably algebraic". According to Eremenko, the integer iterates of a polynomial $$M(x)$$ are uniformly differentiably algebraic (= satisfy the same algebraic differential equation with constant coefficients) iff $$M$$ is conjugate (by a linear function) to a monomial, a Chebyshev polynomial, or the negative of a Chebyshev polynomial. See [2, p. 663]. In case $$M(x) = x^2+c$$, this means precisely $$c=0$$ or $$c=-2$$.

So in the case $$M(x) = x^2+1$$ mentioned by the O.P., the iteration does not have closed form in this sense.

Note that Erimenko is a member here, so he may able to provide more information!

[1] Edgar, G. A., Fractional iteration of series and transseries, Trans. Am. Math. Soc. 365, No. 11, 5805-5832 (2013). ZBL1283.30001.

[2] Rubel, Lee A., Some research problems about algebraic differential equations. II, Ill. J. Math. 36, No. 4, 659-680 (1992). ZBL0768.34003.

This may be kind of weak, but in a certain sense, Liouville's theorem guarantees there is no closed formula for $$a_0 =0$$ and $$a_n = a_{n-1} + \int_{n-1}^n e^{-x^2} \text{d}x$$.

• No closed formula with only elementary functions. Certainly a closed formula using erf. – marty cohen Sep 21 at 20:34
• And that's an important point in many ways. Closed is something like ill definited – Cade Reinberger Sep 21 at 21:16
• I think the question would be better phrased along the lines of "is there a closed form recurrence which has no closed form solution?". Your solution won't classify then, since you can't express $\int_{n-1}^n e^{-x^2}dx$ in closed form (without special functions). – Wojowu Sep 22 at 11:11
• Right. It's kind of weak, doubtless – Cade Reinberger Sep 22 at 16:21