Exercise 4.4.16* (Recurrence functions are eventually periodic)

Question

Let $u_0$ and $u_1$ be integers, and for $n\geq 2$ let $u_n$ be given by 
$$ u_n = au_{n-1} + b u_{n-2} \qquad (4.2) $$ where $a$ and $b$ are integers. Let $m$ be a positive integer. Show that the sequence $u_n \pmod m$ is eventually periodic, with least period not exceeding $m^2 - 1$.

Richard Ganaye · Accepted Answer

ewcommand{\N}{\mathbb{N}}

ewcommand{\Z}{\mathbb{Z}}

\begin{proof}

If $a \in \Z$,  $[a]_m$ denotes the class of $a$ in $\Z/m\Z$.

Consider the map
$$
\varphi
\left\{
\begin{array}{ccl}
[\![ 0, m^2]\!] & 	o & (\Z/m\Z)^2\
i & \mapsto & ([u_i]_m, [u_{i+1}]_m)
\end{array}
ight.
$$
Since $\mathrm{Card}\  [\![ 0, m^2]\!]   = m^2 + 1 > m^2 = \mathrm{Card}\  (\Z/m\Z)^2$, the map $\varphi$ is not injective, so there are two indices $i,\, j$ such that
$$0 \leq i <  j \leq m^2, \qquad  ([u_i]_m, [u_{i+1}]_m) = ([u_j]_m, [u_{j+1}]_m)$$
(pigeonhole principle).

We define $h = j - i$. Then $ h \leq j \leq m^2$, so
$$1 \leq h \leq m^2.$$
Consider the property defined for $k \in \N$ by
$$\mathscr{P}(k): u_k\equiv u_{k+h} \pmod m.$$
\begin{itemize}
\item $u_i \equiv u_j = u_{i + h} \pmod m$ and $u_{i+1} \equiv u_{j+1} = u_{i + 1 + h} \pmod m$, so $\mathscr{P}(i)$ and $\mathscr{P}(i + 1)$ are true.
\item Suppose that $\mathscr{P}(k)$ and $\mathscr{P}(k+1)$ are true for some integer $k \geq i$. Then
$$u_k \equiv u_{k + h} \pmod m, \qquad u_{k+1}\equiv u_{k + 1 +  h} \pmod m.$$
Then
\begin{align*}
u_{k+2 + h} &= a u_{k+1+h} + b u_{k + h}\
& \equiv au_{k+1} + bu_{k}  = u_{k+2} \pmod m.
\end{align*}
Thus $\mathscr{P}(k+2)$ is true, and the induction is done.
\end{itemize}
We obtain that
$$\forall k \in \N,\ k \geq i \Rightarrow u_{k+h} \equiv u_k \pmod m.$$
The sequence $u_n \pmod m$ is eventually periodic, with least period not exceeding $m^2$.
\end{proof}
Note: we don't obtain with this elementary argument the proposed result: "a least period not exceeding $m^2 - 1$", but an improvement of our result requires far more difficult theories on the "rank of apparition" (rank of appearance), so I think that there is an error in the statement (or I missed an argument).

Exercise 4.4.16* (Recurrence functions are eventually periodic)

Answers

Comments

Exercise 4.4.16* (Recurrence functions are eventually periodic)

Answers

Comments

Add answer