Take an arbitrary odd natural number $x$, take the recursive sequence given by $$a_0 = x, a_n= \left \lfloor{ \frac{3 a_{n-1}}{2}} \right \rfloor$$

where $\left \lfloor{ .} \right \rfloor : N \rightarrow N$ is the floor function.

I would like to prove that for any $x$ chosen this sequence eventually has an even number in it, I thought this would be doable but I am stuck. How could one prove this?

  • 5
    $\begingroup$ If $a_0=1$ then the sequence stays at $1$. Did you mean to require $n>1$? $\endgroup$
    – lulu
    Jul 10 '17 at 22:06
  • 1
    $\begingroup$ $a_n(x)$ looks fairly periodic, where $x$ is the initial value. $\endgroup$ Jul 10 '17 at 22:20
  • $\begingroup$ @Monolite Aha, got it! :D $\endgroup$ Jul 10 '17 at 22:27
  • $\begingroup$ @lulu of course, I apologize. $\endgroup$
    – Monolite
    Jul 10 '17 at 22:32

Assuming that $x$ is an integer greater than one, we can rearrange the recursive definition to get $$a_n=\lfloor a_{n-1}+\frac{1}{2}a_{n-1}\rfloor$$ $$a_n=a_{n-1}+\lfloor \frac{1}{2}a_{n-1}\rfloor$$ Suppose that in the prime factorization of $a_{n-1}-1$, $2$ has a multiplicity of $k$. If this is so, then for some integer $m$ not divisible by $2$, we have $$a_{n-1}=2^k\cdot m+1$$ and so $$a_n=2^k\cdot m+1+\lfloor \frac{1}{2}(2^k\cdot m+1)\rfloor$$ $$a_n=2^k\cdot m+1+2^{k-1}\cdot m$$ $$a_n-1=2^{k-1}\cdot 3m$$ Thus the multiplicity of $2$ in each $a_n-1$ always decreases by $1$, so for some $a_n$, $a_n-1$ is odd, and $a_n$ is even. QED.

  • $\begingroup$ Well put. (+1) ${}$ $\endgroup$
    – Chris
    Jul 10 '17 at 22:28
  • $\begingroup$ @Chris Why thank you! :D $\endgroup$ Jul 10 '17 at 22:29
  • $\begingroup$ Shouldn't the last equation be $a_n - 1 = 2^{k-1}\cdot 3m$? If it isn't, then $(m+1)$ is a multiple of $2$ and we have a problem. $\endgroup$
    – COTO
    Jul 11 '17 at 1:53
  • $\begingroup$ @COTO Yes, thank you for pointing that out. :) $\endgroup$ Jul 11 '17 at 13:12

The iterates of $2n+1$ are


This is an even number when $k$ equals the number of trailing zeroes in the binary representation of $n$.

For instance, $2017=11111100001_b$ gives $3^5\cdot111111_b+1=15310$ after $5$ iterations.


Assuming that $x>1,$ we have $x=2^\alpha q+1,$ where $\alpha\geqslant1$ and $q$ is odd. Then $a_1=\left\lfloor3\cdot2^{\alpha-1} q+1+\frac{1}{2}\right\rfloor=3\cdot2^{\alpha-1} q+1.$ If $\alpha=1$ we are done, otherwise, we have $a_2=3^2\cdot2^{\alpha-2}q+1$...then the path is clear


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.