I am interested in the following recurrence relation:
$$ x_n = \left\lfloor \frac{x_{n-1}}{3}\right\rfloor - 2 $$ with initial condition $x_0 = x$.
In particular, I would like to find the specific $n$ such that $x_n \leq 0$. Now, if it weren't for the $-2$-term, I could use the fact that for any $m \in \mathbb{N}$ and $r, s \in \mathbb{R}$ that
$$ \left\lfloor \frac{\left\lfloor r / s \right \rfloor}{m}\right\rfloor = \left\lfloor \frac{r}{ms} \right\rfloor $$ to write $x_n$ in terms of $x_0$. However, due to the subtraction-term I am unable to proceed. I was hoping that anyone could shed some light on this issue, whether it is possible to find a closed form solution for $x_n$ at all.
I have been looking into chapter 3 of the book Concrete Mathematics, however I haven't been able to find any help there. They do however solve various sums involving the floor and ceiling functions.
Thanks in advance for any insight!
$$x_n = \left\lfloor \frac{x_{n-1}}{3}\right\rfloor - 2$$
This sequence is strictly decreasing. Since $x_1, x_2, x_3, \dots$ will all be integers. We may as well study what happens starting from the integer $x_1$.
Theorem. There are $3^k$ values of $x_1$ that will result in a given integer value of $x_{k+1}$.
In particular (Read $\{a \mid b \mid c\}$ as $``a$ or $b$ or $c"$.)
$$x_1 = 3^kx_{k+1} + \sum_{i=0}^{k-1} 3^i \{6 \mid 7 \mid 8\}$$
Proof.
If $x_n = \left\lfloor \dfrac{x_{n-1}}{3}\right\rfloor - 2$, then $x_{n-1} = 3(x_n+2) + \{0 \mid 1 \mid 2\}$.
So
It follows by induction that $x_{n-k} = 3^k x_n + \sum_{i=0}^{k-1} 3^i \{6 \mid 7 \mid 8\}$
In particular,
$$x_1 = 3^k x_{k+1} + \sum_{i=0}^k 3^i \{6 \mid 7 \mid 8\}$$
Hence there are $3^k$ values of $x_1$ that will result in a particular value of $x_{k+1}$.
For example, if I wanted to make $x_4=-2$, then one number I could use would be
$$x_{n-3} = 27(-2) + 9(7) + 3(6) + 8 = 35$$
\begin{align} x_1 &= 35 \\ x_2 &= \left\lfloor \frac{35}{3} \right\rfloor - 2 = 9\\ x_3 &= \left\lfloor \frac 93\right\rfloor - 2 = 1\\ x_4 &= \left\lfloor \frac 13\right\rfloor - 2 = -2\\ \end{align}