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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.