Solution to recursive sequence involving floor function

ceiling-and-floor-functionsrecurrence-relations

I want to find an explicit formula for the following recursive sequence:
$$ E_n =
\begin{cases}
E_0 & n=0 \\
\lfloor k E_{n-1} \rfloor & n \ge 1
\end{cases}, \ n \in \mathbb{N}_0 \ , \ k \in \left( 0 , 1 \right) $$
Without the floor function, the solution looks like:
$$ E_n = E_0 k^n, $$
but I'm not sure how to approach this with the floor function involved…

Best Answer

The exact behavior of the sequence $\langle E_n:n\in\Bbb N\rangle$ seems very hard to pin down, but the long-term behavior is fairly simple.

Suppose first that $E_0\ge 0$. Then $$E_{n+1}=\lfloor kE_n\rfloor\le kE_n<E_n$$ for each $n\in\Bbb N$, so $0\le E_n\le k^nE_0$ for $n\in\Bbb N$, so $\lim\limits_{n\to\infty}E_n=0$, and since $E_n$ is an integer for each $n\in\Bbb Z^+$, there is an $n_0\in\Bbb N$ such that $E_n=0$ for all $n\ge n_0$.

If $E_0<0$, however, matters are somewhat different. For instance:

  • If $E_0=-1$, for instance, $E_n=-1$ for all $n\in\Bbb N$.
  • If $E_0=-2$, there are two cases. If $\frac12<k<1$, then $E_n=-2$ for all $n\in\Bbb N$, but if $0<k\le\frac12$, then $E_n=-1$ for all $n\in\Bbb Z^+$.

More generally, let $m\in\Bbb Z^+$. If $E_0=-m$ and $\frac{m-1}m<k<1$, then $E_n=-m$ for all $n\in\Bbb N$. If $0<k\le\frac{m-1}m$, there are a positive integer $m'<m$ and an $n_0\in\Bbb Z^+$ such that $E_n=-m'$ for all $n\ge n_0$. And with a little more thought it’s clear that if $r\in\Bbb R^+$, and $E_0=-r$, then there are a positive integer $m$ and an $n_0\in\Bbb Z^+$ such that $m\le\lceil r\rceil$ and $E_n=-m$ for all $n\ge n_0$.

In short, the sequence $\langle E_n:n\in\Bbb N\rangle$ is always eventually constant; its limit is $0$ if $E_n\ge 0$ and a negative integer greater than or equal to $\lfloor E_0\rfloor$ if $E_0<0$.

Related Question