Closed-form expressions for nth composition of a function

Question

Is there any general methods to find a closed-form expression for nth composition of a function? (Any book/article recommendations?)

For example

Let $f(x)=1+2x$, we have:

$$g_1=f=1+2x$$

$$g_2=f\circ f=1+2(1+2x)$$

$$\vdots$$

$$g_n=f \underbrace{\circ...\circ f}_{\text{n times}}=\underbrace{1+2(...(1+2x))}_{\text{n times}}$$

$$\text{where $n\in\mathbb{N}$ and n$\neq0$}$$

Based on guess and check I got: \begin{align} g_n(x) & =(\sum_{k=1}^{n-1}2^k)+2^nx+1 \\ & =2^n-2+2^nx+1 \\ & =2^{n}x+2^n-1 \end{align}

But it wouldn't always be easy to guess and check...

Any help would be appreciated.

Answer 1

There are closed forms for

1. polynomials of degree $1$
2. powers of $x$
3. fractional linear transformations
4. Chebyshev polynomials

but for most functions there is no closed form.