# Does a closed formula exist for each recurrent formula?

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.

• Have you heard of the quadratic chaos generated by the logistic map $x_{n+1} = r x_n (1 - x_n)$? May 25, 2022 at 21:03
• Can you share what definition you are using for "recurrent formula" and "closed formula"?
– D.W.
May 26, 2022 at 1:41

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$$.