Does a closed formula exist for each recurrent formula?

Question

I'm interested in a question that probably lies close to the very concept of recursion. I have no idea whether my statement is true or false, neither I have tools to check it, so I'll just ask the question.

Short and simple, if there exists a recurrent formula for some process, can it be either proven or disproven (was it already?) that a closed formula also exists for the same process?

Thanks.

Answer 1

As a general rule, $x_{n+1}=f(x_n)$ does not have a closed form. But I don't know of a general proof. (This seems to be at the same level of difficulty as the antiderivative or closed-form zeroes problems.)

---

An interesting case:

Let us consider the following iteration:

$$x_{n+1}=\frac{x_n^2+a^2}{2x_n}.$$

One can recognize the Heron method for the computation of the square root. The next iterate would be

$$x_{n+2}=\frac{\left(\dfrac{x_n^2+a^2}{2x_n} \right)^2+a^2}{2\left(\dfrac{x_n^2+a^2}{2x_n} \right)}=\frac{x_n^4+6x_n^2a^2+a^4}{4x_n^3+4x_na^2},$$ and the next iterations seem scary to evaluate.

But consider

$$\frac{x_{n+1}-a}{x_{n+1}+a}=\frac{x_n^2+a^2-2x_na}{x_n^2+a^2+2x_na}=\left(\frac{x_n-a}{x_n+a}\right)^2$$ and all of a sudden we get the easy solution

$$\frac{x_{n}-a}{x_{n}+a}=\left(\frac{x_0-a}{x_0+a}\right)^{2^n}$$ which we can solve for $x_n$.