Let $m$ be a positive integer number and $\left(a_n\right)$ be a sequence such that $a_1\in \mathbb{Z}^+$ and $$a_{n+1}=\left\{\begin{matrix} a_n^2 +2^m \quad &\text{if} \quad a_n<2^m,\\ \frac{a_n}{2} &\text{otherwise}. \end{matrix}\right.$$ For each $m\in \mathbb{Z}^+$, find all positive integer numbers $a_1$ such that $a_n$ is a integer number for all $n \in \mathbb{Z^+}$.

First I assume that $a_1 \geq 2^m$ and assume $a_1=2^kl$, where $l$ is an odd number. Then $l$ must be less than $2^m$ since if not, then $a_{k+1}=l$ and $a_{k+2}$ is not an integer number. And since the assumption $a_1 \geq 2^m$, there must exist an $h$ such that $a_{h+1}=2^{k-h}l<2^m$ and $a_h=2^{k-h+1}l >2^m$. Then $a_{h+2}=2^{k-h}l+2^m$ and $a_{h+3}=2^{k-h-1}l+2^{m-1}$. Since $2^{k-h}l<2^m$, we see that $a_{h+3}<2^{m-1}+2^{m-1}=2^m$ and therefore $a_{h+4}=2^{k-h-1}l+2^{m-1}+2^m$. Then $a_{h+5}=2^{k-h-2}l+2^{m-2}+2^{m-1}<2^{m-2}+2^{m-2}+2^{m-1}=2^m$. Going on the process till $k-h-1=0$ yields the next term will not be an integer. This implies that $l=0$.
I will show that if $a_1=2^m$, then $a_n$ is a integer number. Indeed, $a_2=2^{m-1}, a_3=2^{m-1}+2^m, a_4=2^{m-2}+2^{m-1}, a_5=2^{m-2}+2^{m-1}+2^m$. We obtain by induction that $a_{2k+1}=2^m+2^{m-1}+...+2^{m-k}$ and $a_{2k}=2^{m-1}+...+2^{m-k}$.
The case $a_1=2^k$ with $k>m$ will done when $a_{k-m+1}=2^m$
The case $a_1<2^m$ will turn into the first case that $a_2 \geq 2^m$ and $a_2=2^kl$ with an odd number $l$.
This completes the proof.

Am I on the right track? It may be quite "hand-crafted". Help me if there is a mistake or a better way. Thank you.

  • $\begingroup$ >We obtain by induction that $a_{2k+1}=2^m+2^m−1+...+2^{m−k}$ and $a_{2k}=2^{m−1}+...+2^{m−k}$. $$ $$ And for sufficiently large k those aren't integers. $\endgroup$ – liaombro May 12 '19 at 18:59
  • $\begingroup$ I don't get it the formula is $a_{n+1}=a_n^2+2^m$ why are you using $a_{n+1}=a_n+2^m$ ? $\endgroup$ – Julian Mejia May 12 '19 at 19:41
  • $\begingroup$ It's a mistake. I forgot the formula. $\endgroup$ – RuaSun May 13 '19 at 1:16

You should state what you are trying to prove. It appears the claim is that the only $a_1$ that works is $2^m$.

$l$ cannot be zero because then $a_1=0$, which is not allowed.

If you find any $a_1$ that is greater than or equal to $2^{m-1}$ you can multiply it by any power of $2$ and have a new $a_1$ that works. In particular, if $2^m$ works, so does any higher power of $2$.

$2^m$ does not work. $a_2=2^{m-1}$, then $a_3=3\cdot 2^{m-1}$ and every two iterations will remove a power of $2$ until you get to an odd number greater than $2^m$ and fail. For example, if $m=4$, the sequence is $16,8,24,12,28,14,30,15,31,31/2$

| cite | improve this answer | |

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.