Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
The iterates of $2n+1$ are
$$3^{k+1}\left\lfloor\frac{2n+1}{2^{k+1}}\right\rfloor+1.$$
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
