Compose the function $f$ $n$-times recurrently The function $f$ is defined as $f(x) = 3x+2$.
If I were to compose the function $f$ $n$-times recurrently I would start doing it $n = 1$ times, $n = 2$ times etc., until I can find a pattern between the result and $n$.
So far I have:


*

*$n=1$: $(f∘f) = f(3x+2) = 3(3x+2)+2 = 9x+8$

*$n=2$: $f(f∘f) = f(9x+8) = 3(9x+8)+2 = 27x+26$

*$n=3$: $f(f∘f∘f) = f(27x+26) = 3(27x+26)+2 = 81x+80$


Do I need to find some sort of correlation between the result in square brackets and n to solve this particular problem?
Any help will be appreciated and this is my first post so I apologize if I haven't done it right :)
 A: If you rewrite your work, you get
\begin{align*}
f(x)&=3^1x+3^0\cdot2\\
f\circ f(x)&=3^2x+3^1\cdot 2+3^0\cdot2\\
f\circ f\circ f(x)&=3^3x+3^2\cdot 2+3^1\cdot 2+3^0\cdot 2\\
f\circ f\circ f\circ f(x)&=3^4x+3^3\cdot 2+3^2\cdot 2+3^1\cdot2+3^0\cdot 2
\end{align*}
Are you starting to see the pattern now?
Now, I expanded the constants to look at one way of seeing the pattern, but if you know geometric sums or are familiar with the powers of $3$, you might notice that the constants you get are nearly powers of $3$.  In fact, we can rewrite the entire expression as
\begin{align*}
f(x)&=3^1x+(3^1-1)\\
f\circ f(x)&=3^2x+(3^2-1)\\
f\circ f\circ f(x)&=3^3x+(3^3-1)\\
f\circ f\circ f\circ f(x)&=3^4x+(3^4-1)
\end{align*}
Here, the pattern may be even easier to discover.  Now, one could have jumped to this answer by just looking at your original work, but it's sometimes nice to see how to derive these types of formulas if you don't spot the answer right away.
A: I don't get it, what is a problem?
It is almost for sure $$f^{(n)}(x) = 3^nx+3^n-1$$
Induction step: 
\begin{eqnarray}f^{(n+1)}(x) &=& f(3^nx+3^n-1) \\&=& 3(3^nx+3^n-1) +2 \\&=& 3^{n+1}x+3^{n+1}-1 \end{eqnarray}
A: It is evident from your results so far that $$f^n(x) = 3^n x +(3^n-1).$$
You may prove this by Mathematical Induction. 
It is true for $n=1$.
If it is true for $k$, then show that it is also true for $k+1.$ 
A: Let $\,f_n=f^{(n)}(x)\,$ with $\,f_1=3x+2\,$, then $f_{n+1} = f\left(f_{n}\right) = 3 f_n + 2\,$. The latter can be written as  $\,f_{n+1}+1=3(f_n+1)\,$, so $\,f_n+1\,$ is a GP with common ratio $\,3\,$, thus $f_n + 1 = 3^{n-1}(f_1+1)$.
