Is there a general formula for recurrence relations like $ f(x+1) = \sum_{i=0}^k a_n{[f(x)]}^n $

Question

Or in other words, polynomial relation of the function rather than the argument. I've worked out that in general $ f(x+1)={f(x)}^n $ implies $$f(x) = C^{n^x} $$ for some C, but I would like to know if there's a general form for more complicated polynomials, and I'd especially like to know how many arbitrary constants are involved.

Answer 1

There are (up to conjugacy by linear functions) two sequences of polynomials $P_n$ such that $P_n$ has degree $n$ and $P_n(P_m(x)) = P_{nm}(x)$ (i.e. $P_n$ form a semigroup under conjugation). These are the monomials $P_n(x) = x^n$ and the Chebyshev polynomials $P_n = \cos(n \arccos(x))$. Each of these give rise to closed-form general solutions of your recurrence:

$f(x+1) = P_k(f(x))$ with $f(0)=c$ has solution $f(x) = P_{k^x}(c)$.

On the other hand, any polynomial $f$ of degree $> 1$ has fixed points and periodic points, and these result in particular closed-form solutions of your recurrence.