Counting the amount of iterations to reach specific answer

108 Views Asked by At

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

1

There are 1 best solutions below

1
On BEST ANSWER

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}$$