Find $f(f(f(f(f(f(\cdots f(x)))))))$ $2018$ times 
I was given a problem to calculate $f(f(f(\dots f(x))))$ $2018$ times if $f(x)=\frac{x}{3} + 3$ and $x=4$. 

Is it even possible to be done without a computer?
 A: We can rewrite the problem as a first-order difference equation:
\begin{align*}
    a_{n+1} &= \frac{1}{3} a_n + 3 \\ a_0 &= 4
\end{align*}
We want to know $a_{2018}$.
There are a number of standard techniques to solve these, that are covered in discrete math courses.  One trick is temporarily ignore the $+3$ at the end and find a general solution to $a_{n+1} = \frac{1}{3} a_{n}$.  It's not too hard to see that $a_{n} = \frac{1}{3^n}$ satisfies that, and so does any multiple of it.
OK, now what about the $3$?  Let's look for a constant solution to $a_{n+1} = \frac{1}{3}a_n  + 3$.  That is, we solve $a = \frac{1}{3}a + 3 $ for $a$.  We get $a = \frac{9}{2}$.
Combining the two, we have a solution $$a_n = c \cdot \left(\frac{1}{3}\right)^n + \frac{9}{2}$$
This sequence does satisfy $a_{n+1} = \frac{1}{3}a_n + 3$ for any $c$, as you can check.  We now just need to fit the initial condition $a_0 = 4$.  Substituting $n=0$ gives
$$
    4= c \cdot 1 + \frac{9}{2} \implies c = - \frac{1}{2}
$$
So our particular solution is 
$$
a_n = -\frac{1}{2} \cdot \left(\frac{1}{3}\right)^n + \frac{9}{2}
    = \frac{9}{2} - \frac{1}{2\cdot 3^n}
$$
Therefore
$$
    a_{2018} = \frac{9}{2} - \frac{1}{2\cdot 3^{2018}}
$$
This is very, very close to $\frac{9}{2} = 4.5$.
A: Hint: Consider the following recurrence relationship
$$a_{n+1}=\frac{a_n}{3}+3$$
for $n=0,1,\cdots$, and $a_0=4$. Now compute $a_n$ in terms of $n$.

If you are unaware of the method for solving linear recurrence relationships then consider
$b_n=a_{n}-\frac{9}{2}$ and observe that
$$b_{n+1}=\frac{b_{n}}{3} \implies b_{n}=\frac{b_0}{3^n} \implies a_n=\frac{9}{2}-\frac{1}{2}\cdot\frac{1}{3^n}.$$
A: You have $f(x) = \frac 1 3 x + 3.$ The numbers $f(x)$ and $f(w)$ will always be at a distance from each other that is $1/3$ the distance between $x$ and $w.$ That implies the sequence $f(x), f(f(x)), f(f(f(x))), \ldots$ converges to a point $x_0$ satisfying $f(x_0) = x_0.$ So we have
$$
\frac 1 3 x_0 + 3 = x_0
$$
and therefore
$$
x_0 = \frac 9 2.
$$
Since $f(9/2) = 9/2,$ the distance between $f(x)$ and $9/2$ is $1/3$ the distance between $x$ and $9/2.$ Then ask how many times you need to multiply by $1/3.$
A: Let's try to spot a pattern.
$$f(x)=3+\frac x3=\frac13(3^2+x)$$ $$f(f(x))=f\left(\frac13(9+x)\right)=3+\frac{9+x}{9}=4+\frac x9=\frac1{3^2}(3^3+3^2+x)$$ $$f(f(f(x)))=f\left(\frac19(36+x)\right)=3+\frac{36+x}{27}=\frac{13}3+\frac x{27}=\frac1{3^3}(3^4+3^3+3^2+x)$$ 
So iterating $2018$ times, we have $$f(f(f(\cdots f(x))))=\frac1{3^{2018}}(3^{2019}+3^{2018}+...+3^2+x)$$ or $$3^1+3^0+3^{-1}+...+3^{-2016}+\frac x{3^{2018}}\approx 4.5+\frac{2018}{3^{2018}}$$ Now since $3^{2018}$ is much bigger than $2018$, that term could be negligible so we can conclude that $$\boxed{f(f(f(\cdots f(x))))=4.5}$$
A: Suppose there exists an $x$ such that $f(x) = x$
$f(x) = \frac {x}{3} + 3 = x\\
x = \frac 92$
It would be a reasonable guess that we get something very close to $\frac {9}{2}$
$f(4) = 4 +\frac 13\\
f(4+ \frac 13) = 4 + \frac 13 + \frac 19\\
f(4+ \frac 13 + \frac 19) = 4 + \frac 13 + \frac 19 + \frac 1{27}$
Now we are on to something.
$f(4+ \sum_\limits{i=1}^{n} (\frac {1}{3})^i) = \frac {4}{3} + \frac{1}3\sum_\limits{i=1}^{n} (\frac {1}{3})^i + 3 =
4 + \sum_\limits{i=1}^{n+1}(\frac{1}3)^i$
$4 +\sum_\limits{i=1}^{n} \frac {1}{3}^n = 4 + \frac {(1-(\frac 13)^n)}{2}\\
4 +\sum_\limits{i=1}^{2018} \frac {1}{3}^n = 4 + \frac {(1-(\frac 13)^{2018})}{2}\\
4\frac 12 - \frac 12(\frac 13)^{2018}$
A: Consider that for all $x$ we have $$3f(f(x))-f(x)=\frac{x+36}{3}-\frac{x+9}{3}=9$$
From this putting $x=f(x)$ we get
$$3f(f(f(x)))-f(f(x))=9$$
I'll write $f^n(x)=\underbrace{f(f(\cdots f(x))\cdots )}_n$ from now
$$3f^3(x)-f^2(x)=9\\9f^3(x)-3f^2(x)=27$$
Also putting $x=f^2(x)$ $$3f^4(x)-f^3(x)=9\\27f^4(x)-9f^{3}(x)=81$$
And in general $$3^{n-1}f^n(x)-3^{n-2}f^{n-1}(x)=3^n$$
Now lets sum this from $n=2018$ to $n=2$
$$3^{2017}f^{2018}(x)-3^{2016}f^{2017}(x)+3^{2016}f^{2017}(x)-3^{2015}f^{2016}(x)+3^{2015}f^{2016}(x)-\cdots-f(x)=9+27+81+\cdots+3^{2018}\\$$
We can see that most of the terms cancel and we get
$$3^{2017}f^{2018}(x)-f(x)=9+27+\cdots +3^{2018}$$
You can recognize the RHS as the geometric sequence and you know what $f(x)$ is, so you can finish yourself.
A: Let $x_{n+1} =f(x_n)$ that is  $x_{n+1} =\frac{x_n}{3}+3 $  
Letting $$u_n =x_n -\frac{3}{2}\implies u_{n+1}=\frac13 u_n \implies u_n = \frac{u_1}{3^{n-1}} \implies x_n = \frac{3}{2}+\frac{x_1 -\frac{3}{2}}{3^{n-1}}$$
Hence, we have $$ \color{blue}{ \underbrace{f(f(f(f(f(f(\cdots f(x)))))))}_{n~~times} = x_n = \frac{3}{2}+\frac{2x -3}{2\cdot3^{n-1}}}$$
A: Hint: $f^{(n)}(x)=\dfrac{x}{3^n}+\displaystyle\sum_{k=0}^{n-1}\dfrac{1}{3^{n-(k+2)}}$.The second term is straightforward to compute.
A: if $f(x)=\frac{x}{3}+3$
Then $f^2(x)=\frac{f(x)}{3}+3=\frac{x}{9}+\frac{3}{3}+3$
and $f^3(x)=\frac{f^2(x)}{3}+4=\frac{x}{27}+\frac{3}{9}+\frac{3}{3}+3$
By induction the general form is emerging as:
$$f^n(x)=3^{-n}x+3\left(\sum_{k=1}^n3^{1-k}\right)$$
Use the formula for a geometric sum and plug in $x=4, n=2018$:
$f^{2018}(4)=4+\frac{1}{2}\left(1-3^{-2018}\right)$
A: Doesn't look too bad to be honest.
We have:
$$f(x)=\frac{x}3+3=\frac{x+9}{3}$$
$$f^2(x)=\frac{\frac{x+9}{3}+9}{3}=\frac{x+\overbrace{36}^{(3+1)\cdot9}}{9}$$
$$f^4(x)=\frac{\frac{x+36}{9}+36}{9}=\frac{x+\overbrace{360}^{(9+1)\cdot36}}{81}$$
$$f^8(x)=\frac{\frac{x+360}{81}+360}{81}=\frac{x+(81+1)\cdot360}{81^2}$$
Can you see the pattern? Do you think you can take it from here?
A: In order to solve this, let's first write something down
$f(4) = 13/3 = (4 + 9)/3 = (1 + 3 + 9)/3$
$f(f(4)) = 40/9 = (13 + 27)/9 = (4 + 9 + 27) = (1 + 3 + 9 + 27)/9$
$f(f(f(4))) = 121/27 = (40 + 81)/27 = (1 + 3 + 9 + 27 + 81)/27$
We observe a rule:
1) Denominator:
It's the previous denominator  $\times 3$ because we basically take the previous number and divide it by $3$ and add $3$ to it.
2) Numerator: 
The numerator is the sum of a geometric progression, the last number being $3^{n + 1}$, where $n$ is the number of times we did: $f(f(...f(x)))$. In this case, the last number will be $3^{2019}$.
I hope this helped!
