# Recurrence relation involving floor function.

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

• $$x_{n-1} = 3x_n + \{6 \mid 7 \mid 8\}.$$
• $$x_{n-2} = 9x_n + 3\{6,7,8\} + \{6,7,8\}.$$
• $$x_{n-3} = 27x_n + 9\{6,7,8\} + 3\{6,7,8\} + \{6,7,8\}.$$

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}