2
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ It generally helps questions get accepted and get attention when a bit more context and/or information is provided. What's this for, what have you tried, anything like that you can give? $\endgroup$
    – Trevor
    Jan 1 '21 at 20:01
  • 1
    $\begingroup$ Why do you think an explicit formula exists? $\endgroup$ Jan 1 '21 at 22:31
  • 1
    $\begingroup$ @Greg Martin I am not sure if an explicit formula exists :( $\endgroup$
    – JG12321
    Jan 1 '21 at 22:52
2
$\begingroup$

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

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