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?


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

1 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:


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.