I'm looking for an example of a recurrence relation where it provably does not have a closed form.


Does such a thing exist?


For example, I believe $S(n, k)$, or the Stirling numbers of the second type, do not have a closed form -- but I'm not sure if they *don't* or if they *can't*.



Does there exist a recurrence relation which cannot be written in a closed form?
I'm sure you're aware that linear recurrent sequences are well understood and can be solved exactly by a "closed formula". Once you enter the world of non-linear recurrences, even when restricting to constant coefficients, you can get all sorts of strange behavior even with some very simple looking recurrences. One example is the [logistic map](http://en.wikipedia.org/wiki/Logistic_map):
$$x\_{n+1}=rx\_n(1-x\_n)$$
which is only exactly solvable for a few special values of the constant $r$. For the complex and chaotic behavior that happens with other values of $r$ you can check the wiki article, which has a nice bifurcation diagram and summary of the qualitative properties of this map.


