$a_1,a_2,\ldots$ is a sequence of nonzero integer numbers that for all $n\in\mathbb{N}$, if $a_n=2^\alpha k$ such that $k$ is an odd integer and $\alpha$ is a nonnegative integer then: $a_{n+1}=2^\alpha-k$. Prove that if this sequence is periodic, then for all $n\in\mathbb{N}$ we have: $a_{n+2}=a_n$. (The sequence $a_1,a_2,\ldots$ is periodic iff there exists natural number $d$ that for all $n\in\mathbb{N}$ we have: $a_{n+d}=a_n$)
Problem
Source: Iran MO Third Round 2022 Mid-Terms P4
Tags: recursive, Integer sequence, Periodic sequence, number theory
Behanorm_rifghcky
18.08.2022 08:26
Claim:$\forall n\in \mathbb N,a_{n+1}\equiv a_n+1 ~(\mod 2).$ Assume that $a_n=2^{\alpha}k$ where $k\equiv 1 ~(\mod 2)$ and $\alpha \in \mathbb Z_{\geqslant 0}$.So we have:$a_n+a_{n+1}=2^{\alpha}(k+1)-k\equiv 1~(\mod 2).$ From the Claim we can get that if $\{a_n\}$ is periodic,assume that the period is $d$,then $d$ is an even number. For any even term in $\{a_n\}$ :$a_s=2^{\alpha}k~(\alpha\geqslant 1)$,we have:$a_{s+1}=2^{\alpha}-k,a_{s+2}=1-a_{s+1}=k+1-2^{\alpha}.$ Thus we have:$|a_{s+2}|=|k+1-2^{\alpha}|\leqslant (2^{\alpha}-1)+|k|\leqslant 2^{\alpha}|k|=|a_s|.$(The last inequality holds because:$(|k|-1)(2^{\alpha}-1)\geqslant 0$) Which implies that:$|a_s|\geqslant |a_{s+d}|$.So all the above inequalities take the equal sign. So we get:$k\leqslant 0,|k|=1\Rightarrow k=-1\Rightarrow a_s=a_{s+2}=...=-2^{\alpha},a_{s+1}=a_{s+3}=...=2^{\alpha}+1$. So $\forall n\in \mathbb N,a_n=a_{n+sd}=a_{n+sd+2}=a_{n+2}.$Done!
Kugelmonster
04.01.2023 20:22
Main Idea: The value of
$$\left|a_n-\frac 12\right|$$is monotonically (not strictly monotonically though) decreasing.
Proof for monovariant (not interesting)Consider $a_n = 2^\alpha \cdot k$ and the next value $a_{n+1}$
If $a_n$ is positive, then either $a_{n+1}$ is positive too (and thus smaller, done!) or negative. In last case, our claim is $k-2^\alpha < k\cdot 2^\alpha$ which is true.
If $a_n$ is negative, then $k < 0$ and therefore $a_{n+1} = 2^\alpha +(-k) \le 2^\alpha \cdot (-k) + 1$.
Remark: We have also proven that the monovariant is only nondecreasing if $a_n > 0, \alpha = 0$ or $a_n < 0, k = -1$.
Because of the monovariant, the sequence $(a_n)$ can only be periodic if the monovariant is constant. However, there are only pairs of two integers each for which the monovariant is the same. This completes the proof.