Why does this mathematical series plateau below $\frac{1}{4}$ then have runaway growth?

Question

This recursive mathematical series plateaus when $x \leq 1/4$, and it then goes runaway growth. Why?

x = 1/4
y = 0
for i in range(10000000):
    y = (x + y)**2

Answer 1

As a remark, you seem to implicitely only allow non-negative $x$ (setting say $x=-1000$ certainly leads to a runaway growth of $y$), so I'll keep that restriction.

So why is there no runaway growth for $0 \le x \le \frac14$?

As Matti.P wrote in a comment, your loop code would mathematically be described as a seqeunce: $y_0=0;\; y_{i+1}=(x+y_i)^2$ for all $i=0,1,2,\ldots$.

You start with $y_0 = 0 \le \frac14$.

Whenever you do the next loop iteration, and start with an $y_i$ that fulfills $0 \le y_i \le \frac14$, then the next $y_{i+1}$ fulfills the same condition!

Let's prove it. From

$$ 0 \le x+y_i \le \frac14 + \frac14 =\frac12,$$

which comes from using $0 \le x \le \frac14$ and $0 \le y_i \le \frac14$, we can immediately conclude, as the function $f(t)=t^2$ is increasing for $0 \le t$, that

$$ 0^2=0 \le y_{i+1}=(x+y_i)^2 \le \frac14 = \left(\frac12\right)^2.$$

So if $0 \le x \le \frac14$ and because we start with an $y$ value that is between $0$ and $\frac14$, all the following $y$-values will also stay in that interval.

To see why there is runaway growth for $x > \frac14$, we need a little bit more theory.

First, for all $x>0$ the sequence of $(y_i)$ will be increasing. It's true for the very first step from $y_0$ to $y_1$:

$$y_0=0; y_1=x^2 > 0.$$

And it keeps true from one step to the next:

if $0 \le y_i < y_{i+1}$, then

$$y_{i+1}=(x+y_i)^2 < (x+y_{i+1})^2 = y_{i+2},$$

again using the (strict) monotonicity of $f(t)=t^2$ for $t \ge 0$.

So $(y_n)$ is increasing for $x>0$. Such sequences can only have 2 behaviours:

• they converge to a limit, or
• they increase beyond all bounds and "converge" to $+\infty$.

We've seen above that for $0 \le x \le \frac14$ there is no increase beyond all bounds, so it must converge to a limit $l(x)$. How can this limit be calculated?

Well if we know (or assume) that $\lim_{i\to\infty}y_i=l(x)$, then we know that

$$l(x)=\lim_{i\to\infty}y_i = \lim_{i\to\infty}y_{i+1} = \lim_{i\to\infty} (x+y_i)^2 =(x+l(x))^2,$$

where the last equality used the fact that the function $g(t)=(x+t)^2$ is continous ($x$ is just a constant for that function). As we can see, this yields a quadratic equation for $l(x)$, which you can solve the usual way and get

$$l(x)=\frac{1-2x}2 \pm \sqrt{\frac{1-4x}4}$$

Which of the 2 values is actually the limit depends on $y_0$, but this is not our concern here. Note that the term under the square root is $\frac{1-4x}4$. That means the square root exists (in real numbers) only when $x \le \frac14$. If $x >\frac14$, the square root is complex and the only solutions to the equation are 2 non-real numbers.

But obviously, our sequence contains only real numbers, so the limit (if it exists) must be a real number. So the only conclusion we can draw is that for $x > \frac14$, the sequence $(y_n)$ has no limit.

But as I wrote above, for increasing sequences there are only 2 kinds of behaviours, and one has just been ruled out. So it has to be the other, which is unbounded growth.