$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
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!
04.01.2023 20:22