Closed Form Solutions To Simple Iterated Polynomial Building Blocks

I've been doing some work on fractals and simple iterated polynomials lately. I admit, I've only taken classes up through Calc 2, although I've done a decent bit of reading on many topics over the years. But I've been working on finding closed-form solutions to simple polynomial recurrence relations using three basic "building blocks" (the most basic math operations essentially) and then combining them in various ways to see how the solution form changes based on its parts. (Note: In some ways, I am somewhat of a child playing with a loaded gun, so to speak, i.e. fumbling with things I don't fully understand probably.)

Here are the most basic building blocks I started with: $$\mathbf{x_{n+1}=ax_n}$$ $$\mathbf{x_{n+1}=x_n+b}$$ $$\mathbf{x_{n+1}=x_n^c}$$ And their combinations: $$\mathbf{x_{n+1}=ax_n+b}$$ $$\mathbf{x_{n+1}=ax_n^c}$$ $$\mathbf{x_{n+1}=x_n^c+b}$$ And the combination of all three: $$\mathbf{x_{n+1}=ax_n^c+b}$$

The solutions I have come up with so far: $$\mathbf{x_{n+1}=ax_n \Rightarrow x_n=a^nx_0}$$

$$\begin{eqnarray*} x_1&=&ax_0\\ x_2=ax_1=a(ax_0)&=&a^2x_0\\ x_3=ax_2=a(a(ax_0))&=&a^3x_0 \end{eqnarray*}$$

$$\mathbf{x_{n+1}=x_n+b \Rightarrow x_n=x_0+nb}$$

$$\begin{eqnarray*} x_1&=&x_0+b\\ x_2=x_1+b=(x_0+b)+b&=&x_0+2b\\ x_3=x_2+b=((x_0+b)+b)+b&=&x_0+3b \end{eqnarray*}$$

$$\mathbf{x_{n+1}=x_n^c \Rightarrow x_n=x_0^{c^n}}$$

$$\begin{eqnarray*} x_1&=&x_0^c\\ x_2=x_1^c=(x_0^c)^c&=&x_0^{c^2}\\ x_3=x_2^c=((x_0^c)^c)^c&=&x_0^{c^3} \end{eqnarray*}$$

$$\mathbf{x_{n+1}=ax_n+b \Rightarrow x_n=a^nx_0+b\sum_{i=0}^{n-1}a^i=a^nx_0+b\left(\frac{1-a^n}{1-a}\right),(a\neq1)}$$

$$\begin{eqnarray*} x_1&=&ax_0+b\\ x_2=ax_1+b=a(ax_0+b)+b&=&a^2x_0+ab+b\\ x_3=ax_2+b=a(a(ax_0+b)+b)+b&=&a^3x_0+a^2b+ab+b \end{eqnarray*}$$

$$\mathbf{x_{n+1}=ax_n^c \Rightarrow x_n=a^{\sum_{i=0}^{n-1}c^i}x_0^{c^n}=a^{\left(\frac{1-c^n}{1-c}\right)}x_0^{c^n},(c\neq1)}$$

$$\begin{eqnarray*} x_1&=&ax_0^c\\ x_2=ax_1^c=a(ax_0^c)^c=a(a^cx_0^{c^2})&=&a^{c+1}x_0^{c^2}\\ x_3=ax_2^c=a(a(ax_0^c)^c)^c=a(a^{c+1}x_0^{c^2})^c=a(a^{c^2+c}x_0^{c^3})&=&a^{c^2+c+1}x_0^{c^3} \end{eqnarray*}$$

The solutions that still evade me: $$\mathbf{x_{n+1}=x_n^c+b \Rightarrow x_n=?}$$ $$\begin{eqnarray*} x_1&=&x_0^c+b\\ x_2=x_1^c+b=(x_0^c+b)^c+b&=&\sum_{i=0}^c\binom{c}{i}x_0^{ci}b^{c-i}+b\\ x_3=x_2^c+b=\left(\sum_{i=0}^c\binom{c}{i}x_0^{ci}b^{c-i}+b\right)^c+b&=&\sum_{j=0}^c\binom{c}{j}\left[\sum_{i=0}^c\binom{c}{i}x_0^{ci}b^{c-i}\right]^{cj}b^{c-j}+b \end{eqnarray*}$$ $$\mathbf{x_{n+1}=ax_n^c+b \Rightarrow x_n=?}$$

Can anyone give a succinct explanation as to why these last two have such complicated forms compared to the rest? (And sorry for my possibly horrendous algebra, it's been several years since I had any formal math classes...) I read Chaos And Fractals, New Frontiers in Science several years ago (and still have the book). Might the answer be in there? I realize the last two relations are non-linear, but isn't $x_{n+1}=ax_n^c$? I apologize if this has been answered elsewhere. I tried looking around but nothing really seemed to match what I am talking about. Is there a good way to manipulate the nested summations?

• Wow, I just learned that this site is for professional mathematicians only. While I'd like to consider myself one, I'm really not. I apologize if this question is better for math.stackoverflow. – Garrett Miller Mar 26 '15 at 6:49
• You can flag this for moderator attention and ask them to migrate it if you like. – David Roberts Mar 26 '15 at 8:31
• @DavidRoberts Thanks. I will do that. – Garrett Miller Mar 26 '15 at 17:54

Mandelbrot considered a special case of your last one: $z_{n+1}=z_n^2+b$. There are closed forms in case $b=0$ and in case $b=-2$. But not for other values of $b$.
For the lower cases, like $z_{n+1}=az_n+b$, you can look for the topic "difference equations".
For $z_{n+1}=az_n^c$ you can try $u_n = \log z_n$ intead.
• Thank you for your answer GEdgar. Where can I find more information about the closed forms for $z_{n+1}=z_n^2+b$? Like why -2? 0 is obvious (the term just vanishes), but -2? And only -2? Does it have to do with the fact that it has the same absolute value as the exponent? – Garrett Miller Apr 3 '15 at 2:45
• The hint for $z_{n+1}=z_n^2-2$ is: double angle formula for cosine. – GEdgar Apr 3 '15 at 14:01