# Families of 1st order recurrence relations with closed form

A general 1st order recurrence relation can be expressed as $$X_{n+1} = f(X_{n},n)$$.

I am looking for a source, list of functions or statement about $$f$$ such that an $$F$$ exists which expresses $$X_{n} = F(f, X_0, n)$$ as a closed form.

For example, a fairly simple function: $$f(X_n,n) = b_{n} + a_n X_n$$ can be rewritten as

$$\begin{eqnarray} X_{n+1} &=& b_{n} + a_n X_n \\ &=& b_{n} + a_n (b_{n-1} + a_{n-1} (b_{n-2} +\dots)) \\ &=& \left(\sum_{i=0}^{n} b_{n-i}\prod_{j>n-i}^{n}a_j \right) + X_0\prod_{j=0}^{n}a_j \\ &=& b_n + \left(\sum_{i=0}^{n-1} b_{i}\prod_{j=i+1}^{n}a_j \right) + X_0\prod_{j=0}^{n}a_j \\ &=& F(f,X_0,n+1) \end{eqnarray}$$

What can be said about $$f$$ if we require $$F$$'s existence?

By closed form I mean the a combination of all basic operations (+,-,*,/,^, $$\sum, \prod \dots$$), without the reference to a previously determined $$X_n$$

Edit for clarity: It seems function like $$$$f(X_n,n) = a_n(1 - s_n^2) + s_n^2\frac{X_n + b_n}{2} + s_n\frac{|X_n - b_n|}{2}$$$$ do not have such a closed form. It seems like this type of non-linearity already leads to a falsification of existence.

• Is there a proof and if so, how can I write it down? Dec 18, 2022 at 10:49
• Why is $F$ not a clear definition? It only takes the $X_0$ and the information provided by $f$. Dec 18, 2022 at 10:54
• $F$ is a closed form of the example. My question tries to address the fact that the recursion relation in the edit seems to not have the same type of expression as the example due to the non-linearity. You previously mentioned a proof for a general 1st order recursion relation, could you refer me to that source? The first argument in $F$ is a function not a value. I don't understand how the comment "the value of $X_n$ where $(X_k)_k$..." returns anything like a closed form. It uses a recursively created sequence. Dec 18, 2022 at 11:33
• In the book "A=B", there is an algorithm called "Hyper". It takes a linear recurrence and tells whether any hypergeometric solution exist or not. If I am not mistaken, the algorithm was found by Marko Petkovsek, one of the authors of the book". The book is freely downloadable. There is the link: www2.math.upenn.edu/~wilf/AeqB.pdf. I hope, there is an answer to your problem in the book.
– ALNS
Dec 18, 2022 at 15:28