Iterations of Interval Transformations

Suppose that for a function $f: \mathbb {N} \rightarrow \mathbb {N}$, the inequality $f(n+1)>f(f(n))$ holds for every $n \in \mathbb {N}$. Prove that $f(n)=n$ for every $n \in \mathbb {N}$.

Does there exist a continuous function $f: \mathbb {R} \rightarrow \mathbb {R}$ satisfying the equation $f \circ f=F$ in the following cases:

Let us denote by $\mathrm{Id}_{X}$ (or simply Id) the identity map of a set $X$ onto itself (i.e., $\operatorname {Id}(x)=x$ for every $x$ in $X$). A map $h: X \rightarrow X$ will be called an involution if $h \circ h=\mathrm{Id}_{X}$.

Let $f(x)=x+1, g(x)=x-1(x \in \mathbb {R})$. Find two involutions $h$ and $k$ such that the relations $h \circ k=f, k \circ h=g$ hold.

Let us denote by $\mathrm{Id}_{X}$ (or simply Id) the identity map of a set $X$ onto itself (i.e., $\operatorname {Id}(x)=x$ for every $x$ in $X$). A map $h: X \rightarrow X$ will be called an involution if $h \circ h=\mathrm{Id}_{X}$.

Prove that every bijection of a set onto itself is the composition of two involutions.

A map $h: X \rightarrow X$ is called an involution if $h \circ h=\mathrm{Id}_{X}$, where $\mathrm{Id}_{X}$ is the identity map of $X$. A fixed point of a map $f$ is a point $x$ in its domain of definition such that $f(x)=x$.

Prove that a continuous map $f: \Delta \rightarrow \mathbb {R}$, where $\Delta$ is some interval, has a fixed point in each of the following cases:

A fixed point of a map $f$ is a point $x$ in its domain of definition such that $f(x)=x$. Let a function $f \in C(\left[a, b\right])$ be increasing, $f(\left[a, b\right]) \subset [a, b]$. Prove that for every $x_{0} \in [a, b]$ the sequence $x_{n}=f\left(x_{n-1}\right)$ ($n \in \mathbb {N}$) converges to a fixed point. Does this hold if $f$ is a decreasing function?

A fixed point of a map $f$ is a point $x$ in its domain of definition such that $f(x)=x$. Let $f \in C(\mathbb {R})$. For $x_{0} \in \mathbb {R}$, set $x_{1}=f\left(x_{0}\right), x_{k}=f\left(x_{k-1}\right) (k \in \mathbb {N})$. Prove that if for some $x_{0} \in \mathbb {R}$ the sequence $\left\{ \frac{1}{n} \sum_{0 \leqslant k<n} f\left(x_{k}\right)\right\}$ is bounded, then $f$ has a fixed point. Does this hold for continuous maps $f: \mathbb {C} \rightarrow \mathbb {C}$?

A fixed point of a map $f$ is a point $x$ in its domain of definition such that $f(x)=x$.

Prove that a finite group of affine transformations of the plane has a fixed point (common to all transformations of the group).

Maps $f: \Delta_{1} \rightarrow \Delta_{1}$ and $g: \Delta_{2} \rightarrow \Delta_{2}$ ($\Delta_{1}, \Delta_{2}$ being intervals on the line) are called topologically conjugate if there exists a continuous bijection (homeomorphism) $h: \Delta_{2} \rightarrow \Delta_{1}$ such that $f=h \circ g \circ h^{-1}$ (i.e., $h \circ g=f \circ h$). In this case we write $f \sim g$ and call $h$ the conjugating map. It is assumed that the maps are continuous, defined on intervals, and map them into themselves.

Prove that the relation of topological conjugacy is an equivalence relation, i.e.

Maps $f: \Delta_{1} \rightarrow \Delta_{1}$ and $g: \Delta_{2} \rightarrow \Delta_{2}$ ($\Delta_{1}, \Delta_{2}$ being intervals on the line) are called topologically conjugate if there exists a continuous bijection (homeomorphism) $h: \Delta_{2} \rightarrow \Delta_{1}$ such that $f=h \circ g \circ h^{-1}$ (i.e., $h \circ g=f \circ h$). In this case we write $f \sim g$ and call $h$ the conjugating map. It is assumed that the maps are continuous, defined on intervals, and map them into themselves.

Prove that topologically conjugate maps simultaneously possess or fail to possess the following properties:

Maps $f: \Delta_{1} \rightarrow \Delta_{1}$ and $g: \Delta_{2} \rightarrow \Delta_{2}$ ($\Delta_{1}, \Delta_{2}$ being intervals on the line) are called topologically conjugate if there exists a continuous bijection (homeomorphism) $h: \Delta_{2} \rightarrow \Delta_{1}$ such that $f=h \circ g \circ h^{-1}$ (i.e., $h \circ g=f \circ h$). In this case we write $f \sim g$ and call $h$ the conjugating map. It is assumed that the maps are continuous, defined on intervals, and map them into themselves.

Prove that topologically conjugate maps have

Maps $f: \Delta_{1} \rightarrow \Delta_{1}$ and $g: \Delta_{2} \rightarrow \Delta_{2}$ ($\Delta_{1}, \Delta_{2}$ being intervals on the line) are called topologically conjugate if there exists a continuous bijection (homeomorphism) $h: \Delta_{2} \rightarrow \Delta_{1}$ such that $f=h \circ g \circ h^{-1}$ (i.e., $h \circ g=f \circ h$). In this case we write $f \sim g$ and call $h$ the conjugating map. It is assumed that the maps are continuous, defined on intervals, and map them into themselves.

Prove that if $f \sim g$, then the intervals on which the inequality $f(x)>x$ holds are carried by the conjugating map $h$ into intervals on which (depending on the character of the monotonicity of $h$) the same or the opposite strict inequality holds for the map $g$. Prove that if the maps $f$ and $g$ are defined on $\mathbb {R}$ and one of them is odd, then the conjugating bijection $h$ can be chosen to be increasing.

Maps $f: \Delta_{1} \rightarrow \Delta_{1}$ and $g: \Delta_{2} \rightarrow \Delta_{2}$ ($\Delta_{1}, \Delta_{2}$ being intervals on the line) are called topologically conjugate if there exists a continuous bijection (homeomorphism) $h: \Delta_{2} \rightarrow \Delta_{1}$ such that $f=h \circ g \circ h^{-1}$ (i.e., $h \circ g=f \circ h$). In this case we write $f \sim g$ and call $h$ the conjugating map.

Determine whether the maps $f$ and $g$ defined on $\mathbb {R}$ are topologically conjugate in the following cases:

Maps $f: \Delta_{1} \rightarrow \Delta_{1}$ and $g: \Delta_{2} \rightarrow \Delta_{2}$ ($\Delta_{1}, \Delta_{2}$ being intervals on the line) are called topologically conjugate if there exists a continuous bijection (homeomorphism) $h: \Delta_{2} \rightarrow \Delta_{1}$ such that $f=h \circ g \circ h^{-1}$ (i.e., $h \circ g=f \circ h$). In this case we write $f \sim g$ and call $h$ the conjugating map.

Let $\alpha >0, \alpha \neq 1, f_{\alpha }(x)=x^{\alpha }, g_{\alpha }(x)=x^{-\alpha }(x>0)$. For which $\alpha$ and $\beta$ are the functions topologically conjugate

Maps $f: \Delta_{1} \rightarrow \Delta_{1}$ and $g: \Delta_{2} \rightarrow \Delta_{2}$ ($\Delta_{1}, \Delta_{2}$ being intervals on the line) are called topologically conjugate if there exists a continuous bijection (homeomorphism) $h: \Delta_{2} \rightarrow \Delta_{1}$ such that $f=h \circ g \circ h^{-1}$ (i.e., $h \circ g=f \circ h$). In this case we write $f \sim g$ and call $h$ the conjugating map.

Maps $f: \Delta_{1} \rightarrow \Delta_{1}$ and $g: \Delta_{2} \rightarrow \Delta_{2}$ ($\Delta_{1}, \Delta_{2}$ being intervals on the line) are called topologically conjugate if there exists a continuous bijection (homeomorphism) $h: \Delta_{2} \rightarrow \Delta_{1}$ such that $f=h \circ g \circ h^{-1}$ (i.e., $h \circ g=f \circ h$). In this case we write $f \sim g$ and call $h$ the conjugating map.

Prove the topological conjugacy of the continuous maps $f, g:\left[-1,1\right] \rightarrow [-1,1]$, given as follows:

Maps $f: \Delta_{1} \rightarrow \Delta_{1}$ and $g: \Delta_{2} \rightarrow \Delta_{2}$ ($\Delta_{1}, \Delta_{2}$ being intervals on the line) are called topologically conjugate if there exists a continuous bijection (homeomorphism) $h: \Delta_{2} \rightarrow \Delta_{1}$ such that $f=h \circ g \circ h^{-1}$ (i.e., $h \circ g=f \circ h$). In this case we write $f \sim g$ and call $h$ the conjugating map.

Let $f:\left[a_{1}, b_{1}\right] \rightarrow \left[a_{1}, b_{1}\right], g:\left[a_{2}, b_{2}\right] \rightarrow \left[a_{2}, b_{2}\right]$ be homeomorphisms of intervals having no fixed interior points. Prove that $f \sim g$. Verify that the statement remains valid if the closed intervals are replaced by open intervals.

Maps $f: \Delta_{1} \rightarrow \Delta_{1}$ and $g: \Delta_{2} \rightarrow \Delta_{2}$ ($\Delta_{1}, \Delta_{2}$ being intervals on the line) are called topologically conjugate if there exists a continuous bijection (homeomorphism) $h: \Delta_{2} \rightarrow \Delta_{1}$ such that $f=h \circ g \circ h^{-1}$ (i.e., $h \circ g=f \circ h$). In this case we write $f \sim g$ and call $h$ the conjugating map.

Classify, up to topological conjugacy, the homeomorphisms of an interval onto itself having a finite set of fixed points, among which are the endpoints of the interval.

Let $f$ be a map of an interval $\Delta \subset \mathbb {R}$ into itself, $f^{0}(x)=x$, $f^{1}(x)=f(x)$, $f^{n}(x)=f\left(f^{n-1}(x)\right)$ for $n>1$. We say that the method of successive approximations with initial point $x_{0} \in \Delta$ converges if the limit $\lim x_{n}$ exists, where $x_{n}=f^{n}\left(x_{0}\right)$.

Let the function $f \in C(\left[a, b\right])$ be increasing. Prove that the method of successive approximations converges for any initial point $x_{0} \in [a, b]$, if

Let $f$ be a map of an interval $\Delta \subset \mathbb {R}$ into itself, $f^{0}(x)=x$, $f^{1}(x)=f(x)$, $f^{n}(x)=f\left(f^{n-1}(x)\right)$ for $n>1$. We say that the method of successive approximations with initial point $x_{0} \in \Delta$ converges if the limit $\lim x_{n}$ exists, where $x_{n}=f^{n}\left(x_{0}\right)$.

Prove the convergence of the method of successive approximations for any starting point $x_{0} \in \Delta$ and find $\lim x_{n}$ for the following maps $f$:

Let $f$ be a map of an interval $\Delta \subset \mathbb {R}$ into itself, $f^{0}(x)=x$, $f^{1}(x)=f(x)$, $f^{n}(x)=f\left(f^{n-1}(x)\right)$ for $n>1$. We say that the method of successive approximations with initial point $x_{0} \in \Delta$ converges if the limit $\lim x_{n}$ exists, where $x_{n}=f^{n}\left(x_{0}\right)$.

Determine for which starting points $x_{0}$ in the domain of definition of the map $f$ the method of successive approximations converges, and find $\lim x_{n}$, if

We call a fixed point $x^{*}$ of the map $f$ attracting if for all $x_{0}$ taken from some neighborhood of the point $x^{*}$, the sequence $x_{n}=f^{n}\left(x_{0}\right)$ converges to the point $x^{*}$. If for some neighborhood $U$ of the fixed point $x^{*}$ and an arbitrary point $x_{0} \in U, x_{0} \neq x^{*}$, there is an index $n$ such that $x_{n} \notin U$, then the point $x^{*}$ is called repelling.

Let $x^{*}$ be a fixed point of the map $f$, and suppose $f$ is differentiable at $x^{*}$. Prove that

For which values of the parameter $a$ and for which $x_{0} \in \mathbb {R}$ does the sequence of iterates $x_{n}=f^{n}\left(x_{0}\right)$ converge, if

Let $\varphi$ be a differentiable function defined on an interval $\Delta$, and $N_{\varphi }$ the map defined at those points $x \in \Delta$ where $\varphi^{\prime }(x) \neq 0$ by $N_{\varphi }(x)=x-\varphi (x) / \varphi^{\prime }(x)$. The fixed points of $N_{\varphi }$ coincide with the roots of $\varphi$. We say that Newton's iterative process with initial point $x_{0}$ converges to $c$ if $x_{k}=N_{\varphi }^{k}\left(x_{0}\right) \rightarrow c$.

Let $\varphi \in C^{2}(\Delta ), c \in \Delta , \varphi (c)=0,\left|\varphi^{\prime }(x)\right|>m>0$ for $x \in \Delta$. Prove that if the point $x_{0}$ is sufficiently close to $c$, then

Let $\varphi$ be a differentiable function defined on an interval $\Delta$, and $N_{\varphi }$ the map defined at those points $x \in \Delta$ where $\varphi^{\prime }(x) \neq 0$ by $N_{\varphi }(x)=x-\varphi (x) / \varphi^{\prime }(x)$. The fixed points of $N_{\varphi }$ coincide with the roots of $\varphi$. We say that Newton's iterative process with initial point $x_{0}$ converges to $c$ if $x_{k}=N_{\varphi }^{k}\left(x_{0}\right) \rightarrow c$.

Prove that if $\varphi \in C^{(n)}(\Delta ), c \in \Delta , \varphi (c)=\varphi^{\prime }(c)=\ldots = =\varphi^{(n-1)}(c)=0, \varphi^{(n)}(c) \neq 0$, then for initial points $x_{0}$ sufficiently close to $c$, Newton's iterative process converges to $c$, and moreover $\left|x_{k}-c\right| \leqslant M q^{k}(M>0,0<q<1)$.

Let $\varphi$ be a differentiable function defined on an interval $\Delta$, and $N_{\varphi }$ the map defined at those points $x \in \Delta$ where $\varphi^{\prime }(x) \neq 0$ by $N_{\varphi }(x)=x-\varphi (x) / \varphi^{\prime }(x)$. The fixed points of $N_{\varphi }$ coincide with the roots of $\varphi$. We say that Newton's iterative process with initial point $x_{0}$ converges to $c$ if $x_{k}=N_{\varphi }^{k}\left(x_{0}\right) \rightarrow c$.

Let $\varphi \in C^{2}(\left[a, b\right])$ be a function such that $\varphi \varphi^{\prime \prime }>0$ on $(a, b)$ and $\varphi (a)=\varphi^{\prime \prime }(b)=0$ (or $\varphi (b)=\varphi^{\prime \prime }(a)=0$). Verify that for any initial point from $\left[a, b\right]$, Newton's iterative process converges to a root of $\varphi$.

Let $\varphi$ be a differentiable function defined on an interval $\Delta$, and $N_{\varphi }$ the map defined at those points $x \in \Delta$ where $\varphi^{\prime }(x) \neq 0$ by $N_{\varphi }(x)=x-\varphi (x) / \varphi^{\prime }(x)$. We say that Newton's iterative process with initial point $x_{0}$ converges to $c$ if $x_{k}=N_{\varphi }^{k}\left(x_{0}\right) \rightarrow c$.

Let $P$ be a polynomial having only simple real roots. Prove that if $x_{0}$ is an inflection point of $P$ (i.e. $P^{\prime \prime }\left(x_{0}\right)=0$), then Newton's iterative process, started at the point $x_{0}$, converges to a root of $P$. In a similar way, by varying the inflection points, one can find all the roots except the minimal and maximal ones.

The set $\left\{ x_{n}=f^{n}\left(x_{0}\right) \mid n \in \mathbb {N}\right\}$ is called the trajectory of the point $x_{0}$. If the trajectory is finite, then there exists $n \in \mathbb {N}$ such that the points $x_{0}, x_{1}, \ldots , x_{n-1}$ are pairwise distinct, while $x_{n}=x_{0}, x_{n+1}=x_{1}, \ldots$; in this case $x_{0}$ is called a periodic point, the number $n$ its period, and the tuple $\left(x_{0}, \ldots , x_{n-1}\right)$ an $n$-cycle.

Let $\left(x_{0}^{*}, x_{1}^{*}, \ldots , x_{n-1}^{*}\right)-n$-cycle of the map $f$ be given. Prove that

Let $f$ be a continuous map of a segment $\Delta$ into itself, and let $I_{0}, I_{1}, \ldots$ be a finite or infinite sequence of segments, with $I_{0} \subset \Delta , I_{n+1} \subset f\left(I_{n}\right)$ for every $n \geqslant 0$. Prove that

The set $\left\{ x_{n}=f^{n}\left(x_{0}\right) \mid n \in \mathbb {N}\right\}$ is called the trajectory of the point $x_{0}$. If the trajectory is finite, then there exists $n \in \mathbb {N}$ such that the points $x_{0}, x_{1}, \ldots , x_{n-1}$ are pairwise distinct, while $x_{n}=x_{0}, x_{n+1}=x_{1}, \ldots$; in this case $x_{0}$ is called a periodic point, the number $n$ its period, and the tuple $\left(x_{0}, \ldots , x_{n-1}\right)$ an $n$-cycle.

Prove that if a continuous map of a segment into itself has a 4-cycle, then it also has a 2-cycle.

The set $\left\{ x_{n}=f^{n}\left(x_{0}\right) \mid n \in \mathbb {N}\right\}$ is called the trajectory of the point $x_{0}$. If the trajectory is finite, then there exists $n \in \mathbb {N}$ such that the points $x_{0}, x_{1}, \ldots , x_{n-1}$ are pairwise distinct, while $x_{n}=x_{0}, x_{n+1}=x_{1}, \ldots$; in this case $x_{0}$ is called a periodic point, the number $n$ its period, and the tuple $\left(x_{0}, \ldots , x_{n-1}\right)$ an $n$-cycle.

Let $f: \Delta \rightarrow \Delta$ be a continuous map of a segment into itself. Prove that the following statements are equivalent:

1. there exists a point $a \in \Delta$ such that the points $b=f(a), c=f^{2}(a)$, $d=f^{3}(a)$ satisfy the inequalities $d \leqslant a<b<c$ or $c<b<a \leqslant d$;

2. in $\Delta$ there exists a point having period three;

3. for any $m \in \mathbb {N}$, in $\Delta$ there exists a point having period $m$.

The set $\left\{ x_{n}=f^{n}\left(x_{0}\right) \mid n \in \mathbb {N}\right\}$ is called the trajectory of the point $x_{0}$. If the trajectory is finite, then there exists $n \in \mathbb {N}$ such that the points $x_{0}, x_{1}, \ldots , x_{n-1}$ are pairwise distinct, while $x_{n}=x_{0}, x_{n+1}=x_{1}, \ldots$; in this case $x_{0}$ is called a periodic point, the number $n$ its period, and the tuple $\left(x_{0}, \ldots , x_{n-1}\right)$ an $n$-cycle.

Prove that for $n \geqslant 2$ the Chebyshev polynomial $T_{n}$ (see problems I.2.20 and 1.16 b)), defined on $\left[-1,1\right]$, has cycles of arbitrary order.

A fixed point $x^{*}$ of a map $f$ is called attracting if for all $x_{0}$ from some neighborhood of $x^{*}$ the sequence $x_{n}=f^{n}\left(x_{0}\right)$ converges to $x^{*}$, and repelling if for some neighborhood $U$ of it and every point $x_{0} \in U$, $x_{0} \neq x^{*}$, there is an index $n$ such that $x_{n} \notin U$. If the points $x_{0}, x_{1}, \ldots , x_{n-1}$, where $x_{k}=f^{k}\left(x_{0}\right)$, are pairwise distinct while $x_{n}=x_{0}$, then the tuple $\left(x_{0}, \ldots , x_{n-1}\right)$ is called an $n$-cycle and $n$ the period of $x_{0}$; the $n$-cycle is called attracting if $x_{0}$ is an attracting fixed point of $f^{n}$, and repelling if $x_{0}$ is a repelling fixed point of $f^{n}$.

Find the values of the parameter $a$ for which the map $f(x)=1-a\left|x\right|(x \in \mathbb {R})$ has

A fixed point $x^{*}$ of a map $f$ is called attracting if for all $x_{0}$ from some neighborhood of $x^{*}$ the sequence $x_{n}=f^{n}\left(x_{0}\right)$ converges to $x^{*}$, and repelling if for some neighborhood $U$ of it and every point $x_{0} \in U$, $x_{0} \neq x^{*}$, there is an index $n$ such that $x_{n} \notin U$. If the points $x_{0}, x_{1}, \ldots , x_{n-1}$, where $x_{k}=f^{k}\left(x_{0}\right)$, are pairwise distinct while $x_{n}=x_{0}$, then the tuple $\left(x_{0}, \ldots , x_{n-1}\right)$ is called an $n$-cycle and $n$ the period of $x_{0}$; the $n$-cycle is called attracting if $x_{0}$ is an attracting fixed point of $f^{n}$, and repelling if $x_{0}$ is a repelling fixed point of $f^{n}$.

Let $a>0, f(x)=1-a x^{2}(x \in \mathbb {R})$. Determine for which values of the parameter $a$ an attracting fixed point and an attracting 2-cycle exist. Find the "birth moments" of the 2-, 4- and 3-cycles (i.e., the lower bounds on the values of $a$ for which these cycles exist).

A fixed point $x^{*}$ of a map $f$ is called attracting if for all $x_{0}$ from some neighborhood of $x^{*}$ the sequence $x_{n}=f^{n}\left(x_{0}\right)$ converges to $x^{*}$, and repelling if for some neighborhood $U$ of it and every point $x_{0} \in U$, $x_{0} \neq x^{*}$, there is an index $n$ such that $x_{n} \notin U$. If the points $x_{0}, x_{1}, \ldots , x_{n-1}$, where $x_{k}=f^{k}\left(x_{0}\right)$, are pairwise distinct while $x_{n}=x_{0}$, then the tuple $\left(x_{0}, \ldots , x_{n-1}\right)$ is called an $n$-cycle and $n$ the period of $x_{0}$; the $n$-cycle is called attracting if $x_{0}$ is an attracting fixed point of $f^{n}$, and repelling if $x_{0}$ is a repelling fixed point of $f^{n}$.