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.

Systems of Iterated Equations

  1. Iterations on Monotone Functions
  2. Graphing Equations Is Useful
  3. Graphing Equations Is Useful, II
  4. Graphing Equations Is Useful, III
  5. Graphing Equations Is Useful, IV
  6. Graphing Equations Is Useful, V
  7. Tangential Chaos
  8. Equation in Radicals as a System of Equations
  9. Two Conditions for a Triangle to Be Equilateral

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

Copyright © 1996-2017 Alexander Bogomolny

 62683464

Search by google: