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?
 A: 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$. 
A: 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.
