# Proving that a recursive sequence will eventually reach an even number.

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?

• If $a_0=1$ then the sequence stays at $1$. Did you mean to require $n>1$? – lulu Jul 10 '17 at 22:06
• $a_n(x)$ looks fairly periodic, where $x$ is the initial value. – Simply Beautiful Art Jul 10 '17 at 22:20
• @Monolite Aha, got it! :D – Franklin Pezzuti Dyer Jul 10 '17 at 22:27
• @lulu of course, I apologize. – 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.

• Well put. (+1) ${}$ – Chris Jul 10 '17 at 22:28
• @Chris Why thank you! :D – Franklin Pezzuti Dyer Jul 10 '17 at 22:29
• 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. – COTO Jul 11 '17 at 1:53
• @COTO Yes, thank you for pointing that out. :) – Franklin Pezzuti Dyer Jul 11 '17 at 13:12

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