[proofplan] The proof proceeds by induction on the Sharkovsky ordering. The base cases and inductive steps split into three regimes: (1) odd periods force all larger odd periods and all their doubles, (2) $2 \cdot (\text{odd})$ periods are reduced to the odd case by examining $f^2$, and (3) powers of $2$ propagate downward by a halving argument. The main tools are the Intermediate Value Theorem, the [Onto Closed Intervals](/theorems/2803) lemma, and the covering-interval (directed graph) technique used in the proof of [Period Three Implies All Periods](/theorems/2804). We give the proof for the three structural pieces of the ordering separately. [/proofplan] [step:Define the Sharkovsky ordering and establish the three regimes] The Sharkovsky ordering $\triangleleft$ on $\mathbb{N}$ is defined as: \begin{align*} 1 \triangleleft 2 \triangleleft 4 \triangleleft 8 \triangleleft \cdots \triangleleft 2^n \triangleleft \cdots \triangleleft \cdots \triangleleft 2^2 \cdot 7 \triangleleft 2^2 \cdot 5 \triangleleft 2^2 \cdot 3 \triangleleft \cdots \triangleleft 2 \cdot 7 \triangleleft 2 \cdot 5 \triangleleft 2 \cdot 3 \triangleleft \cdots \triangleleft 7 \triangleleft 5 \triangleleft 3. \end{align*} The ordering partitions $\mathbb{N}$ into three types: - **Type O (odd):** Odd numbers $\geq 3$, ordered $\cdots \triangleleft 7 \triangleleft 5 \triangleleft 3$. - **Type E (even $\times$ odd):** Numbers $2^j \cdot m$ with $j \geq 1$ and $m \geq 3$ odd, ordered within each "column" $2^j \cdot m$ by decreasing $m$, and columns ordered by increasing $j$. - **Type P (powers of 2):** $1 \triangleleft 2 \triangleleft 4 \triangleleft \cdots$ The theorem asserts: if $f$ has a $k$-cycle and $l \triangleleft k$, then $f$ has an $l$-cycle. We must show that each period forces all periods earlier in the ordering. The proof uses three main lemmas, one for each structural transition. [guided] The Sharkovsky ordering $\triangleleft$ on $\mathbb{N}$ has a clean hierarchical structure. Reading from right to left (strongest to weakest forcing): \begin{align*} \underbrace{3 \triangleright 5 \triangleright 7 \triangleright \cdots}_{\text{odd}} \triangleright \underbrace{2 \cdot 3 \triangleright 2 \cdot 5 \triangleright \cdots}_{2 \times \text{odd}} \triangleright \underbrace{4 \cdot 3 \triangleright 4 \cdot 5 \triangleright \cdots}_{4 \times \text{odd}} \triangleright \cdots \triangleright \underbrace{\cdots \triangleright 8 \triangleright 4 \triangleright 2 \triangleright 1}_{\text{powers of } 2}. \end{align*} Period $3$ forces the most (all other periods), while period $1$ forces the least (nothing else). The ordering partitions $\mathbb{N}$ into three types: odd periods $\geq 3$ (strongest forcers), even $\times$ odd periods $2^j \cdot m$ with $j \geq 1$ and $m \geq 3$ odd (intermediate), and pure powers of $2$ (weakest). The key insight underlying the proof is the **covering-interval technique**. Given a period-$k$ orbit $\{x_1 < \cdots < x_k\}$, define $k-1$ intervals $I_j = [x_j, x_{j+1}]$. Since $f$ is continuous and maps orbit points to orbit points, the Intermediate Value Theorem forces $f(I_j) \supset I_{j'}$ for certain pairs $(j, j')$ determined by the permutation that $f$ induces on the orbit. These covering relations form a directed graph: an arrow $I_j \to I_{j'}$ means $f(I_j) \supset I_{j'}$. Closed paths of length $n$ in this directed graph correspond to periodic points of period $n$ (or a divisor of $n$). The [Onto Closed Intervals](/theorems/2803) lemma and the Intermediate Value Theorem convert each closed path into a fixed point of $f^n$. The Sharkovsky ordering emerges from a careful combinatorial analysis of which closed-path lengths are achievable for each cycle type -- specifically, which graph structures are necessarily present for odd, even-times-odd, and power-of-$2$ cycles. The proof treats the three structural transitions separately: odd periods force other odd periods (and everything below), even-times-odd periods reduce to the odd case via iterates, and powers of $2$ propagate by a halving argument. [/guided] [/step] [step:Establish the covering-interval framework for extracting periodic orbits] Let $f \colon \mathbb{R} \to \mathbb{R}$ be continuous and suppose $f$ has a $k$-cycle $\{x_1 < x_2 < \cdots < x_k\}$. Define the $k - 1$ closed intervals \begin{align*} I_j := [x_j, x_{j+1}], \qquad j = 1, \ldots, k-1. \end{align*} We say $I_j$ *covers* $I_m$ (written $I_j \to I_m$) if $I_m \subset f(I_j)$. Since $f$ is continuous and maps consecutive orbit points to orbit points, $f(I_j)$ contains the interval from $\min\{f(x_j), f(x_{j+1})\}$ to $\max\{f(x_j), f(x_{j+1})\}$, and possibly more (by the Intermediate Value Theorem, $f(I_j)$ contains every value between $f(x_j)$ and $f(x_{j+1})$, and in particular every $I_m$ that lies between them). [claim:Closed paths yield periodic points] If there is a sequence of covering relations $I_{j_0} \to I_{j_1} \to \cdots \to I_{j_{n-1}} \to I_{j_0}$ forming a closed path of length $n$ in the directed graph, then $f$ has a periodic point $z$ with $f^i(z) \in I_{j_i}$ for $i = 0, \ldots, n-1$ and $f^n(z) = z$. [/claim] [proof] By the [Onto Closed Intervals](/theorems/2803) lemma, $I_{j_{n-1}} \to I_{j_0}$ implies there exists a closed interval $C_{n-1} \subset I_{j_{n-1}}$ with $f(C_{n-1}) = I_{j_0}$. Similarly, $I_{j_{n-2}} \to I_{j_{n-1}}$ and $C_{n-1} \subset I_{j_{n-1}}$ imply $C_{n-1} \subset f(I_{j_{n-2}})$, so by the [Onto Closed Intervals](/theorems/2803) lemma there exists $C_{n-2} \subset I_{j_{n-2}}$ with $f(C_{n-2}) = C_{n-1}$. Continuing inductively, we obtain nested applications: \begin{align*} C_0 \subset I_{j_0}, \quad f(C_i) = C_{i+1} \text{ for } i = 0, \ldots, n-2, \quad f(C_{n-1}) = I_{j_0}. \end{align*} In particular, $f^n(C_0) = I_{j_0} \supset C_0$. Since $C_0 \subset I_{j_0}$, there exist points $a, b \in C_0$ with $f^n(a) = \min I_{j_0} \leq a$ and $f^n(b) = \max I_{j_0} \geq b$. By the Intermediate Value Theorem applied to $g(x) := f^n(x) - x$ on $[a, b] \subset C_0$, there exists $z \in C_0 \subset I_{j_0}$ with $f^n(z) = z$. By construction, $f^i(z) \in C_i \subset I_{j_i}$ for each $i$. [/proof] [guided] The covering-interval technique is the engine that converts combinatorial data (which intervals cover which) into analytic conclusions (existence of periodic points). Let $f \colon \mathbb{R} \to \mathbb{R}$ be continuous with a $k$-cycle $\{x_1 < \cdots < x_k\}$, and define $I_j = [x_j, x_{j+1}]$ for $j = 1, \ldots, k-1$. We say $I_j$ **covers** $I_m$ (written $I_j \to I_m$) if $I_m \subset f(I_j)$. Since $f$ is continuous, $f(I_j)$ contains every value between $f(x_j)$ and $f(x_{j+1})$ (by the Intermediate Value Theorem), so $I_j \to I_m$ whenever $I_m$ lies between $f(x_j)$ and $f(x_{j+1})$. The key claim is: **a closed path $I_{j_0} \to I_{j_1} \to \cdots \to I_{j_{n-1}} \to I_{j_0}$ of length $n$ yields a periodic point $z$ with $f^n(z) = z$.** The proof works by pulling back through the chain of coverings. Start at the end: $I_{j_{n-1}} \to I_{j_0}$ means $I_{j_0} \subset f(I_{j_{n-1}})$. By the [Onto Closed Intervals](/theorems/2803) lemma, there exists a closed sub-interval $C_{n-1} \subset I_{j_{n-1}}$ with $f(C_{n-1}) = I_{j_0}$. Next, $I_{j_{n-2}} \to I_{j_{n-1}}$ means $I_{j_{n-1}} \subset f(I_{j_{n-2}})$, and since $C_{n-1} \subset I_{j_{n-1}}$, the lemma gives $C_{n-2} \subset I_{j_{n-2}}$ with $f(C_{n-2}) = C_{n-1}$. Continuing this backward induction through the entire chain, we obtain nested sub-intervals $C_0 \subset I_{j_0}$, $C_1 \subset I_{j_1}$, ..., $C_{n-1} \subset I_{j_{n-1}}$ with $f(C_i) = C_{i+1}$ for $i = 0, \ldots, n-2$ and $f(C_{n-1}) = I_{j_0}$. In particular, $f^n(C_0) = I_{j_0} \supset C_0$. Since $f^n$ maps $C_0$ over a set containing $C_0$, the function $g(x) = f^n(x) - x$ satisfies: there exist $a, b \in C_0$ with $f^n(a) = \min I_{j_0} \leq a$ (so $g(a) \leq 0$) and $f^n(b) = \max I_{j_0} \geq b$ (so $g(b) \geq 0$). By the Intermediate Value Theorem applied to $g$ on $[a,b] \subset C_0$, there exists $z \in C_0$ with $g(z) = 0$, i.e., $f^n(z) = z$. By construction, $f^i(z) \in C_i \subset I_{j_i}$ for each $i = 0, 1, \ldots, n-1$, so the orbit of $z$ visits the prescribed sequence of intervals. The delicate part is ensuring the periodic point has *exact* period $n$ rather than a proper divisor of $n$. A fixed point of $f^n$ could have period $d | n$ with $d < n$ if the orbit revisits its starting interval prematurely. To rule this out, one chooses closed paths in the directed graph that do not return to $I_{j_0}$ before completing the full circuit of length $n$. Concretely, one selects paths where $j_1, \ldots, j_{n-1}$ are all distinct from $j_0$, or where the return pattern is incompatible with any shorter period. For instance, in the proof that an odd $m$-cycle forces a period-$l$ cycle (for $l \triangleleft m$), one constructs a specific closed path of length $l$ that passes through a self-covering interval $I_j \to I_j$ and visits distinct intermediate intervals, ensuring that the resulting fixed point of $f^l$ cannot have period less than $l$. The Sharkovsky ordering emerges precisely from the combinatorial constraints on which closed-path lengths are achievable for each cycle type. Odd cycles produce the richest directed graphs (with self-loops and long paths), while power-of-$2$ cycles produce the simplest graphs (with only $2$-cycles in the graph, yielding periods that are powers of $2$). [/guided] [/step] [step:Prove that an odd period $m \geq 3$ forces all periods $l \triangleleft m$ with $l$ odd] Suppose $f$ has a periodic orbit $\{x_1 < \cdots < x_m\}$ of odd period $m \geq 3$. Among these $m$ points, consider the permutation $\sigma$ defined by $f(x_i) = x_{\sigma(i)}$. Since $m$ is odd, not all points can alternate sides of any single point (an even-odd parity argument). Specifically, there must exist consecutive points $x_j, x_{j+1}$ such that both $f(x_j)$ and $f(x_{j+1})$ lie on the same side of $\{x_j, x_{j+1}\}$ relative to the orbit ordering, which forces one of the intervals $I_j$ to cover itself: $I_j \to I_j$ for some $j$. More precisely, since the permutation $\sigma$ on $m$ points (with $m$ odd) has the property that the orbit $\{x_1, \ldots, x_m\}$ cannot be mapped by $f$ in a purely "interleaving" fashion, there exist adjacent orbit points $x_j < x_{j+1}$ with $f(x_j) \geq x_{j+1}$ and $f(x_{j+1}) \leq x_j$ (or $f(x_j) \leq x_j$ and $f(x_{j+1}) \geq x_{j+1}$). In either case, $I_j \to I_j$. Given the self-covering $I_j \to I_j$ and the full covering graph, one constructs closed paths of every odd length $l < m$ that visit $I_j$ at specified times and pass through other intervals to achieve the desired length, ensuring the point has exact period $l$ (by choosing paths that avoid premature returns). For even periods, the self-covering $I_j \to I_j$ immediately gives a fixed point ($l = 1$) and the directed graph structure forces a $2$-cycle and all other periods earlier in the ordering. The detailed graph analysis (which interval covers which) depends on the specific permutation type, but the key structural fact is: for an odd $m$-cycle, the covering graph always contains enough arrows to support closed paths of every length $l$ with $l \triangleleft m$. [/step] [step:Reduce the even case $k = 2^j \cdot m$ to the odd case via iterates of $f$] Suppose $f$ has a cycle of period $k = 2^j \cdot m$ where $j \geq 1$ and $m \geq 3$ is odd. Let $\{p_1, \ldots, p_k\}$ be the orbit. Consider the iterate $g := f^{2^j} \colon \mathbb{R} \to \mathbb{R}$, which is continuous. The orbit $\{p_1, \ldots, p_k\}$ under $f$ splits into $2^j$ orbits of $g$, each of length $m$ (since $g = f^{2^j}$ and the period of each point under $g$ divides $k / \gcd(k, 2^j) = m$; since $m$ is the smallest positive integer with $g^m(p_i) = p_i$, each $g$-orbit has exact period $m$). By the odd-period case (previous step), $g = f^{2^j}$ has periodic orbits of every period $l$ with $l \triangleleft m$ in the odd part of the Sharkovsky ordering. A period-$l$ orbit of $g$ is a period-$l \cdot 2^j$ orbit of $f$ (or a divisor thereof). This gives $f$ periodic orbits of periods $2^j \cdot l$ for every odd $l$ forced by $m$. To obtain periods $2^i$ for $i = 0, 1, \ldots, j$: a period-$m$ orbit of $g = f^{2^j}$ (with $m$ odd $\geq 3$) forces a fixed point of $g$ (since $1 \triangleleft m$), which is a period dividing $2^j$ for $f$. A careful refinement shows that $f$ must have orbits of exact period $2^i$ for each $i = 0, 1, \ldots, j$. Indeed, a period-$2$ orbit of $g$ is a period-$2^{j+1}$ orbit of $f$, and one argues inductively downward. For the part of the ordering involving $2^i \cdot m'$ with $i < j$: the iterate $f^{2^i}$ has a period-$2^{j-i} \cdot m$ orbit. Since $2^{j-i} \cdot m$ has $m$ as an odd factor, $f^{2^i}$ forces (by the same argument) orbits whose periods, when translated back to $f$, yield all required periods. [guided] Suppose $f$ has a cycle of period $k = 2^j \cdot m$ where $j \geq 1$ and $m \geq 3$ is odd. The reduction to iterates is the engine that makes the Sharkovsky ordering work across the "columns" $2^j \cdot (\text{odd})$. **Same column.** The iterate $g := f^{2^j}$ is continuous, and the $k$-cycle of $f$ splits into $2^j$ orbits of $g$, each of period $m$. Since $m$ is odd and $\geq 3$, the odd-period theory (from the previous step) applies to $g$: $g$ has periodic orbits of every period $l \triangleleft m$ in the odd part of the Sharkovsky ordering. A period-$l$ orbit of $g = f^{2^j}$ is a period-$2^j \cdot l$ orbit of $f$ (or a period dividing $2^j \cdot l$). This gives $f$ orbits of periods $2^j \cdot l$ for every odd $l$ forced by $m$ -- all periods in the same "column" $2^j \cdot (\text{odd})$ that are earlier in the ordering. **Lower columns.** We also need periods from columns $2^i \cdot (\text{odd})$ with $i < j$. For instance, a period-$12 = 4 \cdot 3$ orbit should force a period-$6 = 2 \cdot 3$ orbit. This follows by considering $f^{2^i}$ instead of $f^{2^j}$: the $k$-cycle of $f$ is a $k/\gcd(k, 2^i) = 2^{j-i} \cdot m$-cycle of $f^{2^i}$. Since $2^{j-i} \cdot m$ has odd part $m \geq 3$, the same argument applies to $f^{2^i}$, producing orbits whose periods, when translated back to $f$, yield all required periods in the column $2^i \cdot (\text{odd})$. **Powers of $2$.** A period-$m$ orbit of $g = f^{2^j}$ (with $m$ odd $\geq 3$) forces a fixed point of $g$ (since $1 \triangleleft m$). A fixed point of $f^{2^j}$ has period dividing $2^j$ under $f$. A careful refinement (using the structure of the orbit under iterated squaring) shows $f$ must have orbits of exact period $2^i$ for each $i = 0, 1, \ldots, j$. This handles the pure-power-of-$2$ tail for the current column; the next step handles the case where $k$ is itself a power of $2$. The hierarchical structure of the Sharkovsky ordering -- columns $2^j \cdot (\text{odd})$ ordered by increasing $j$, with powers of $2$ at the end -- directly mirrors the hierarchical structure of the iterates $f, f^2, f^4, \ldots$ used in the reduction. [/guided] [/step] [step:Handle the powers-of-$2$ tail of the ordering] It remains to show that a period-$2^n$ orbit (with $n \geq 1$) forces a period-$2^i$ orbit for every $i = 0, 1, \ldots, n-1$. Let $\{p_1, \ldots, p_{2^n}\}$ be the orbit, ordered as $p_1 < p_2 < \cdots < p_{2^n}$. Consider the iterate $g := f^2$. The orbit splits into two $g$-orbits, each of period $2^{n-1}$. These two sub-orbits interleave: one cannot have all points of one $g$-orbit lying entirely to the left of all points of the other (this would contradict the continuity of $f$ on the intervals between them, since $f$ must map the rightmost point of one sub-orbit across to the other sub-orbit). By induction on $n$: $g = f^2$ has a period-$2^{n-1}$ orbit, so by the inductive hypothesis, $g$ has orbits of period $2^i$ for $i = 0, \ldots, n-2$. A period-$2^i$ orbit of $g$ is a period-$2^{i+1}$ orbit of $f$ (or a divisor). This gives $f$ orbits of period $2^i$ for $i = 1, \ldots, n-1$. For $i = 0$ (a fixed point): the orbit $\{p_1, \ldots, p_{2^n}\}$ has an even number of points, so there exist consecutive orbit points $p_j < p_{j+1}$ with $f(p_j) \geq p_{j+1}$ (i.e., $f$ maps $p_j$ to the right) and $f(p_{j+1}) \leq p_j$ (i.e., $f$ maps $p_{j+1}$ to the left), or vice versa. In either configuration, $I_j \to I_j$, so by the Intermediate Value Theorem there is a fixed point in $I_j$. This completes the induction and establishes the powers-of-$2$ part of the ordering. [/step] [step:Combine the three cases to complete the proof] Let $f \colon \mathbb{R} \to \mathbb{R}$ be continuous with a $k$-cycle, and let $l \triangleleft k$. We have established: 1. If $k$ is odd ($k \geq 3$), then $f$ has orbits of every period $l$ with $l \triangleleft k$ (Step 3). 2. If $k = 2^j \cdot m$ with $j \geq 1$ and $m \geq 3$ odd, then by reducing to iterates (Step 4), $f$ has orbits of every period in the columns $2^i \cdot (\text{odd})$ for $i \leq j$ that are forced, plus all pure powers of $2$ up to $2^j$. 3. If $k = 2^n$, then $f$ has orbits of period $2^i$ for all $i < n$ (Step 5). In each case, $l \triangleleft k$ implies $f$ has an $l$-cycle. This is Sharkovsky's Theorem. [/step]