8
$\begingroup$

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?

$\endgroup$
  • 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$ – Simply Beautiful Art Jul 10 '17 at 22:20
  • $\begingroup$ @Monolite Aha, got it! :D $\endgroup$ – Franklin Pezzuti Dyer Jul 10 '17 at 22:27
  • $\begingroup$ @lulu of course, I apologize. $\endgroup$ – Monolite Jul 10 '17 at 22:32
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Well put. (+1) ${}$ $\endgroup$ – Chris Jul 10 '17 at 22:28
  • $\begingroup$ @Chris Why thank you! :D $\endgroup$ – Franklin Pezzuti Dyer 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$ – Franklin Pezzuti Dyer Jul 11 '17 at 13:12
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.