1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

$$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}

$\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.