# Counting the amount of iterations to reach specific answer

I have the following function $$f(x) = (x + y) \cdot z$$ where $$y$$ is any positive number and $$z \in (0,1)$$. The way this works is that the output feeds the input such that $$x_{n+1} = (x_n + y) \cdot z$$ or $$f(f(f(f...$$ or $$(x+y)\cdot z + y)\cdot z + y) \cdot z + y) \cdot z ...$$ if we try to solve $$x = (x + y) \cdot z$$ we get $$x = \frac{y \cdot z}{1 - z}$$ which will only occur after infinitely many iterations assuming that $$x_{initial} < \frac{y \cdot z}{1 - z}$$ where $$x_{initial}$$ is the first number that we start the iteration with.

Since for $$x = \frac{y \cdot z}{1 - z}$$ we need infinitely many iterations we can approximate this to $$x > \frac{y \cdot z}{1 - z} \cdot 0.99$$ the reason I say greater is because it is very rare that after an iteration I get exactly a specific number. I've already written a computer code that performs all of these iterations and stops when $$x > \frac{y \cdot z}{1 - z} \cdot 0.99$$ telling the user how many iterations it has performed.

What I want to do is find some function that can express this mathematically instead of a computer having to go through all of these iterations. I want to find some function $$N(i)$$ where $$i$$ is the number of iterations (doesn't have to be an integer) and $$N(i)$$ gives the value of $$x$$ after those iterations. In this case this function must include $$x_{initial}, y, z$$ as constants. For example if do $$\lim_{i \to \infty } N(i) = \frac{y \cdot z}{1 - z}$$, therefore this function will have a horizontal asymptote.

Perhaps there isn't a clear way to express this mathematically and can only be calculated via computer iteration. If anyone has any ideas I'll greatly appreciate it if you could write them down.

Thanks

• Have you tried formulating an explicit expression for the output, after $n$ iterations? Like a geometric sum ... – Matti P. Apr 12 '19 at 11:59
• This problem is actually not too different from this: math.stackexchange.com/questions/3164490/… – Matti P. Apr 12 '19 at 12:01

You have stated the recurrence relation $$x_{n+1}=(x_n+y)\cdot z=z\cdot x_n+y\cdot z$$ This has the solution $$x_n=C\cdot z^n + \frac{y\cdot z(z^n-1)}{z-1}$$ where $$C$$ is an arbitrary constant. We can deduce the value of $$C$$ by using $$x_0=x_{\text{initial}}\implies C=x_{\text{initial}}$$ $$\boxed{\therefore x_n=\overbrace{f(f(f(\dots(x)))}^{n\text{ times}}=x_{\text{initial}}\cdot z^n+\frac{y\cdot z(z^n-1)}{z-1}}$$ Finally if you want to solve for the value of $$n$$ which gives the value of $$0.99\left(\frac{y\cdot z}{1-z}\right)$$ then you have to solve $$x_n=x_{\text{initial}}\cdot z^n+\frac{y\cdot z(z^n-1)}{z-1}=0.99\left(\frac{y\cdot z}{1-z}\right)$$ $$\frac{x_{\text{initial}}\cdot z^n(z-1)+y\cdot z(z^n-1)}{z-1}=0.99\left(\frac{y\cdot z}{1-z}\right)$$ $$x_{\text{initial}}\cdot z^n(z-1)+y\cdot z(z^n-1)=-0.99\cdot y\cdot z$$ $$x_{\text{initial}}\cdot z^{n+1}-x_{\text{initial}}\cdot z^n+y\cdot z^{n+1}-y\cdot z=-0.99\cdot y\cdot z$$ $$z^n(x_{\text{initial}}\cdot z-x_{\text{initial}}+y\cdot z)=0.01\cdot y\cdot z$$ $$z^n=\frac{0.01\cdot y\cdot z}{x_{\text{initial}}\cdot z-x_{\text{initial}}+y\cdot z}$$ $$n=\log_z{\left(\frac{0.01\cdot y\cdot z}{x_{\text{initial}}\cdot z-x_{\text{initial}}+y\cdot z}\right)}$$ As you want the least integer greater than this you have $$\boxed{n_{\text{min}}=\left\lceil\log_z{\left(\frac{0.01\cdot y\cdot z}{x_{\text{initial}}\cdot z-x_{\text{initial}}+y\cdot z}\right)}\right\rceil}$$