Exercise 2.4.13 (Least value of $s$ such that $u_{2s} = u_s$)

Question

Let $f(u)$ be a given function. Suppose that a sequence $u_i$ of real numbers is generated iteratively by putting $u_{i+1} = f(u)$. Suppose also that $u_1,u_2,\ldots,u_{17}$ are distinct, but that $u_{18} = u_{11}$. What is the least value of $s$ such that $u_{2s} = u_s$?

Richard Ganaye · Accepted Answer

\begin{proof} 
We prove by induction that $u_i = u_{i+7}$ for all $i\geq 11$.

$u_{11} = u_{18}$ by hypothesis, so the property is true for $i = 11$.

If $u_i = u_{i+7}$ for some $i\geq 11$, then $f(u_i) = f(u_{i+7})$, so $u_{i+1} = u_{(i+1) + 7}$.

The induction is done, so
$$\forall i \in \N,\ i\geq 11 \Rightarrow u_i = u_{i + 7}.$$

So $7$ is a period, and since $7$ is prime, there is no shortest period if the sequence is not constant nor stationary.

Since $7$ is a period, another induction on $k$ (not detailed) gives
$$\forall i \in \N,\ i\geq 11 \Rightarrow \forall k \in \N, \ u_i = u_{i + 7 k}.$$

So $u_{2s} = u_s$, with $s \geq 11$, if $2s = s + 7k$, that is $s = 7k$. If $k=0$, or $k = 1$, then  $s<11$. Since we want the least value of $s$, we take $k = 2$.

Then $s =14$, and
$$u_{14} = u_{28}.$$
(and $u_{21} = u_{42}, u_{28} = u_{56}, \cdots$)

The least value of $s$ such that $u_{2s} = u_s$ is $s = 14$.
\end{proof}

Exercise 2.4.13 (Least value of $s$ such that $u_{2s} = u_s$)

Answers

Comments

Exercise 2.4.13 (Least value of $s$ such that $u_{2s} = u_s$)

Answers

Comments

Add answer