Iterations on Monotone Functions

The following has been prompted by Dan Sitaru's posting of a problem and its solution at the CutTheKnotMath facebook page.

For a given real-valued function $f$ we consider iterations $x_{n+1}=f(x_{n}),$ $n=0,1,\ldots$ and an admissible $x_{0}.$ The basic fact we wish to establish is this:

Let $f$ be strictly monotone. Then one of the two:

  1. If $x_{0}$ is a fixed point of $f,$ i.e., $f(x_{0})=x_{0},$ the iterations stop right away.

  2. The iterations form an infinite sequence which either converges to one of the attractive fixed points or, otherwise, diverges.

The iterations never form a finite loop.

Proof

Without loss of generality , we may assume that $f$ is monotone increasing, i.e., $x\lt y$ implies $f(x)\lt f(y).$

Only the second part needs to be clarified. So assume $x_{0}$ is not a fixed point of $f$ and let $x_{1}=f(x_{0}).$ Either $x_{1}\lt x_{0}$ or $x_{1}\gt x_{0}.$ In the former case, $x_{2}=f(x_{1})\lt f(x_{0})=x_{1}$ and it can easily be seen that the successive iterations form a strictly decreasing sequence. Similarly, if $x_{1}\gt x_{0}$ the iterations strictly increase.

In Dan's example, $f(x)=x+x^{3}+\sqrt[3]{x}+\arctan x$ which, as a sum of strictly increasing functions is strictly increasing. Moreover, it has a single fixed point: $f(0)=0,$ since this is the only point where its graph crosses the diagonal $y=x.$ It follows that the iterations on this function cannot form a finite cycle. In particular, the system $y=f(x),$ $z=f(y),$ $w=f(z),$ $x=f(w)$ may only have a single solution, viz., $x=y=z=w=0.$ The same holds for any number of similarly formed equations.

[an error occurred while processing this directive]

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
[an error occurred while processing this directive]