Show that the sequence $x_n=\Big[\frac32x_{n+1}\Big]$, $x_1=2$ contains an infinite set of odd numbers and an infinite set of even numbers.

Question

I am having a hard time proving this

Let $x_n$ be a sequence such that $x_{n+1}=\Big[\frac32x_n\Big]$ for $n\gt1$, where $[x]$ denotes the nearest integer function and $x_1=2$.

Show that this sequence has an infinite set of odd numbers and an infinite set of even numbers.

---

I think the best way to approach it is by contradiction. That is, assume that the sequence contains a finite number of odds, let that be $$S=\{x_{k_1},x_{k_2},\cdots x_{k_m}\}$$ Thus, all $x_{k_{m+i}}$ terms must be even numbers.

But $x_{k_{m+1}}=2l$ for $l\in\Bbb{Z}$, so $$x_{k_{m+2}}=\Big[\frac322l\Big]=\Big[3l\Big]$$

And since $[3l]$ is in $\Bbb{Z}$ for all $l\in\Bbb{Z}$ it follows that all $x_{k_j}$ will be of the form $[3t]$, $t\in \Bbb{Z}$.

If we can show that there are infinite number of odds of this form, I believe that we are done. But that is not hard to show, since $\forall t$ odd, $[3t]$ is also odd.

I am having strong doubts though about how rigorous this is, I fear I am missing something crucial here. Any ideas are welcome.

Answer 1

The argument you have started is a good approach. The only thing that is missing is to derive the desired contradiction.

Following the same path as in your argument we assume there is only a finite number of odd terms. This implies there is an integer $N$ such that $x_{n}$ is even for all $n\geq N$. Since $x_N$ is even we can write it on the form $x_N = 2^m\cdot k$ where $k$ is odd and $m\geq 1$. The recursion now gives us that (for $i\leq m$)

$$x_{N+i} = 3^i\cdot 2^{m-i}\cdot k$$

but then $x_{N+m} = 3^m\cdot k$ which is odd. This contradicts the assumption that there is a finite number of odd terms.

---

Similary if there is only a finite number of even terms then there is a $N$ such that $x_n$ is odd for all $n\geq N$. Since $x_N$ is odd we can write $x_N$ on the form $x_N = 2^m\cdot k+1$ where $k$ is odd and $m\geq 1$. But then

$$x_{N+i} = 3^i\cdot 2^{m-i}\cdot k + 1$$ so that $x_{N+m} = 3^m\cdot k+1$ which is even. Again this gives us a contradiction and we can conclude that the sequence has to contain an infinite number of terms of both parities.

---

Note that the argument above only works when $x_1>1$. If $x_1 = 1$ then $x_n=1$ for all $n$ so there will not be an infinite number of even terms (the argument above fails since $m=0$ in this case).

Answer 2

If $x_n=2m$ then $x_{n+1}=3m$ and if $x_n=2n+1$ then $x_{n+1}=\left\lfloor \frac{3}{2}(2m+1)\right\rfloor=3m+1$.

Suppose $x_n=2m_1+1$.

Then $x_{n+1}=3m_1+1$.

Suppose $x_{n+1}=3m_1+1$ is odd.

Then $m_1$ is even and $x_n=4m_2+1,\,x_{n+1}=6m_2+1,\,x_{n+2}=9m_2+1$.

Suppose $x_{n+2}$ is odd.

Then $m_2$ is even and $x_n=8m_3+1,\,x_{n+1}=12m_3+1,\,x_{n+2}=18m_3+1,\,x_{n+3}=27m_3+1$.

If $x_{n+3}$ is odd then $m_3$ is even and $x_n=16m_4+1$, etc.

So we see that an inductive argument can be made for the case that if there is a string of $k$ consecutive terms being odd, beginning with $x_n$, then it must be the case that $2^k$ divides $x_n-1$. Therefore there can be no infinite sequence of consecutive odd terms.

A similiar inductive argument can show that if there is a string of $k$ consecutive even terms beginning with $x_n=2m_1$ then $2^k$ divides $x_n$, so there can be no infinite sequence of consecutive even terms.

Since every consecutive subsequence of even terms must be interrupted by an odd term and every consecutive sequence of odd terms must be interrupted by an even term there must be an infinite number of odd terms and in infinite number of even terms.