1
$\begingroup$

My question concerns using the fixed-point iteration to find the fixed point of the function $f(x)=x+x^2=x(1+x)$ (this function has a single fixed point at $0$).

The problem

Given some fixed $x_0$, define the sequence $x_n$ by $$\begin{align*} x_{n+1}=x_n+x_n^2&&\text{for all $n\geq0$.} \end{align*}$$ Does this sequence converge to $0$ for all $x_0$ in the range $-1\lt x_0\lt0$? After some computational numerical exploration, I think the answer might be yes but I'm not so sure how to prove this.

Some notes

The sequence trivially converges to $0$ when $x_0=-1$ or $x_0=0$. It's also fairly easy to prove that it does not converge to $0$ whenever $x_0$ lies outside this range (i.e., $x_0\lt-1$ or $x_0\gt0$).

I've already proved that for any $x_0$ in this range, all successive $x_n$s remain in this range (i.e., $-1\lt x_n\lt0$ for all $n\geq0$) and that the sequence increases / gets closer to $0$ (i.e., $x_{n+1}\gt x_n$), but is there any way to prove it actually converges to $0$?

Some examples

If, for example, $-\frac{1}{2}\lt x_n\lt-\frac{1}{4}$, we'll have $-\frac{3}{8}\lt x_{n+1}\lt-\frac{1}{8}$ and $-\frac{21}{64}\lt x_{n+2}\lt-\frac{5}{64}$, etc. So it seems as though the range of possible values gets closer to $0$. But, how would one prove this?

$\endgroup$

2 Answers 2

2
$\begingroup$

You can use the monotone convergence theorem. It tells us that a sequence $\{x_n\}_{n=1}^\infty\subseteq \mathbb R$ converges if it is bounded and decreasing. For you sequence we have $|x_{n+1}| = |x_n| |1+x_n| \leq 1$ since $x_0 \in (-1,0)$. And likewise we have $x_{n+1} = x_n(1+x_n) \leq x_n$ as $1+x_n \in (0,1)$.

(You can use induction to prove both these claims.)

Now you have shown that $\lim_{n\to\infty} x_n=x$ exists. From this we see that $$ x = \lim_{n\to\infty} x_{n+1} = \lim_{n\to\infty} x_n(1+x_n) = x(1+x). $$ Hence $x$ satisfies $x = x^2+x$ so $x=0$.

$\endgroup$
4
  • $\begingroup$ Great, exactly what I was looking for! $\endgroup$
    – Revoltechs
    Apr 16, 2021 at 7:15
  • $\begingroup$ @ΑΘΩ You're right, I should have said increasing and replaced $\leq$ with $\geq$. Thanks. $\endgroup$
    – user178563
    Apr 16, 2021 at 8:05
  • $\begingroup$ I've already proved that $x_n$ is monotonic increasing and bounded above by $0$ in this case. So this is all I needed to complete the argument (from what I understand, I've never formally studied real analysis, so I certainly may be missing something). $\endgroup$
    – Revoltechs
    Apr 16, 2021 at 8:06
  • $\begingroup$ @user178563 Glad to see that you agree. If we are to be very precise (which we should very well be, for this is what this forum is about) the part where it appears you want to show that $|x_n| \leqslant 1$ by induction on $n$ is also dubious (the induction is not spelled out clearly). $\endgroup$
    – ΑΘΩ
    Apr 16, 2021 at 8:08
1
$\begingroup$

The answer to your question (regarding convergence to $0$) is indeed affirmative and for a reason that is not too difficult to ascertain. For simplicity let us introduce the quadratic polynomial function: \begin{align*} f \colon \mathbb{R} &\to \mathbb{R} \\ f(x)&=x^2+x \end{align*} and let us note that $f[(-1, 0)] \subseteq (-1, 0)$, in other words the interval $(-1, 0)$ is stable under $f$. To prove this latter claim it suffices to notice that $x^2+x+1=\left(x+\frac{1}{2}\right)^2+\frac{3}{4} \geqslant \frac{3}{4}>0$ for any $x \in \mathbb{R}$ (and thus in particular $x^2+x>-1$ always) and respectively that given $x \in (-1, 0)$ we have $x+1>0$ yet $x<0$ which means that $x^2+x=x(x+1)<0$.

The immediate conclusion that we draw from this is that for any fixed $t \in (-1, 0)$, the unique recursive sequence $x \in \mathbb{R}^{\mathbb{N}}$ defined by $x_0=t$ and $x_{n+1}=f(x_n)$ for any $n \in \mathbb{N}$ has the property that actually $x \in (-1, 0)^{\mathbb{N}}$ and is thus a bounded sequence. Furthermore, since $x_{n+1}=x_n+x_n^2 \geqslant x_n$ takes place for every $n \in \mathbb{N}$ we gather that $x$ is increasing (one can actually make the more precise observation that since $x_n \neq 0$ for all $n \in \mathbb{N}$ under the stated conditions, the inequality mentioned above is actually strict, rendering $x$ into a strictly increasing sequence, however that is not essential for the study of convergence).

According to one of the theorems of Weierstrass, any upper-bounded increasing sequence of real numbers is convergent, which applies in particular to $x$. Since $x$ is defined recursively with respect to the continuous function $f$, it follows with necessity that $\displaystyle\lim_{n \to \infty} x_n$ must be a fixed point for $f$. However it is obvious that there is just one such fixed point - the unique solution to the equation $f(u)=u \Leftrightarrow u^2=0$ - which is $0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.