Find values of $a$ for which the function is periodic.

Question

Given a positive integer $m$ consider the sequence $\{a_n\}$ of positive integers defined by the initial term $a_0=a$ and the recurrence relation

$a_{n+1} = a_n/2$ if $a_n$ is even; $a_n+m$, if $a_n$ is odd.

Find all values of $a$ for which the sequence is periodic.

I tried some kind of case-checking kind of solution, but that did not lead me anywhere. Please help.

Answer 1

Fact 1: If there are two distinct $k_1$ and $k_2$ s.t. $a_{k_1}=a_{k_2}$ then the sequence repeats.

If $m$ is odd (the crux of the problem) then each $a_k$ is no larger than $a_1 + 3m$ [make sure you see why or check the proof below; essentially you get to add by $m$ only once before you have to divide by 2]. As each $a_k$ is positive it follows that $a_k \in \{1,2,\ldots, a_1+3m\}$ for all $k$. Therefore it follows from Fact 1 that the sequence repeats.

If $m$ is even and positive then let $i_0$ be the smallest integer such that $a_12^{-i_0}$ is no longer even--or equivalently $2^{-i_0}a_1$ is odd. Then $a_2 = a_12^{-1}$, $\ldots ,$ $a_{i_0+1} = 2^{-i_0}a_1$, while $a_{i_0+1+j} = a_12^{-i_0} + jm$ for each nonnegative integer $j$ [make sure you see why; note that $a_{i_0+j+1} = a_12^{-i_0} + jm$ is an odd integer as $a_12^{-i_0}$ is odd and $m$ is even]. So the function is not periodic.

So for a positive integer $m$, the function is periodic iff $m$ is odd, no matter what positive integer $a_1$ is.

[If $m$ is 0 and $a_1 $ is odd then all of the $a_n$s are $a_1$. If $m=0$ and $a_1$ is even then letting $i_0$ be the smallest integer s.t. $a_12^{-i_0}$ is odd, then $a_n=a_12^{-i_0}$ for all $n > i_0$.]

---

Proof that $a_k< a_1+3m$ for all $k$ if $m$ is odd: We first show that $a_k < a_1+2m$ if $a_k$ is odd, by induction on $k$. Let us assume that $a_{k_0} < a_1+2m$ and that $a_{k_0}$ is odd. Then $a_{k_0+1}=a_{k_0}+m$ is even [as $m$ is odd] and is no greater than $a_1+3m$. Then $a_{k_0+2} = a_{k_0+1}/2$ is no greater than $a_1/2 + 3m/2 < a_1+2m$. So indeed, $a_k < a_1+2m$ if $a_k$ is odd.

Now we claim that $a_k < a_1+3m$ if $a_k$ is even. Indeed, let us use induction on $k$. If $a_{k-1}$ is even then by induction hypthesis $a_{k-1} < a_1+3m$ and $a_k = a_{k-1}/2 < a_{k-1}$ so indeed, $a_k < a_1+3m$ as well. If $a_{k-1}$ is odd then by the previous paragraph $a_{k-1} < a_1+2m$, which implies $a_k < a_1+3m$. Thus indeed, $a_k < a_1+3m$ if $a_k$ is even.

So $a_k < a_1+2m$ if $a_k$ is odd and $a_k < a_1+3m$ if $a_k$ is even, so the $a_k$s are indeed bounded.