Integer Recursion Reference Request

Question

I've run across the following recursion which at times seems very steady and predictable and at other times seems very chaotic.

Let $c_1, \dots c_k, b_0, m \in \mathbb{Z}$ with $b_0>m\ge 3$ and $b_i = 0$ for $i \le 0$. For $n \ge 1$, define $$b_n = \sum_{i=1}^k c_i\left \lfloor \frac{b_{n-i}}{m} \right \rfloor .$$

Here's two examples where the sequence behaves very differently:

In both, take $k=2$, $m=5$, $b_0=26$.

Example 1: For $c_1=2$, $c_2=4$, the sequence of $b_n$ eventually repeats: $$26, 10, 24, 16, 22, 20, 24, 24, 24, 24, \dots$$ where $b_i =24$ for $i \ge 6$.

Example 2: For $c_1=3$, $c_2=4$, the sequence of $b_n$ diverges: $$26, 15, 29, 27, 35, 41, 52, 62, 76, 93, 114, 138, \dots$$ where the sequence is strictly increasing for $i \ge 4$.

Is this a well-known recursion and/or dynamical system that has been studied before?

The main question I'm curious about is: given $m$ and $b_0$, under what conditions for $c_i$ is it eventually periodic vs. divergent?

Answer 1

I don't have a complete solution but I do have some conjectures and insights which might be useful if someone wants to look into this more deeply. I will assuming here that the $c_i > 0.$ Also, I will allow the initial values $b_{1-k},b_{2-k},\cdots,b_0$ to be arbitrary non-negative integers.

Conjectures:

• If $\sum_1^k c_i < m$ then the sequence stabilizes to $0.$
• If $\sum_1^k c_i = m$ then the sequence is eventually periodic.
• If $\sum_1^k c_i > m$ then there is a (relatively small) region near the origin in $\mathbb{Z}^k$ so that the sequence is eventually periodic if the initial values $(b_{1-k},\cdots,b_0)$ are in that region but grows without bound otherwise.

---

Consider the sequence of integers $q_n=\lfloor \frac{b_n}{m} \rfloor$ so $$b_n = \sum_{i=1}^k c_i\ q_{n-i} $$

and the sequence of $b_n$ is periodic or increasing if and only if the same is true of the sequence of $q_n.$

Also, $$q_n = \lfloor\sum_{i=1}^k \frac{c_i}m q_{n-i}\rfloor $$ so we need only investigate this series.

The same conjectures hold for this sequence with the change of the initial conditions to $(q_{1-k},\cdots,q_0)$

There are two related series of rational numbers $x_i$ and $y_i$for $i \gt -k$ defined by the same initial conditions and recurrences with no rounding. $y_i=x_i=q_i$ for $i \le 0$ while $$x_n = \sum_{i=1}^k \frac{c_i}m x_{n-i} $$ $$y_n = \sum_{i=1}^k \frac{c_i}m y_{n-i}-\frac{m-1}m. $$ Both sequences are standard recurrence relation so we know when the series $x_i$ and $y_i$ decay, are constant, or increase. Also, I claim that $y_i \le q_i \le x_i.$