7
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ This doesn't immediately look like a dynamical system to me: what would be the phase space? Is there a dynamical reformulation of the problem that I'm missing? $\endgroup$ – Ian Morris Mar 4 '16 at 18:12
  • $\begingroup$ Perhaps I'm misusing the phrase "dynamical system". I thought any recursive sequence could be interpreted as some sort of discrete dynamical system, but I'll readily admit I'm probably missing some nuance critical to dynamical systems experts. Feel free to correct the wording and/or tags as appropriate. $\endgroup$ – Aeryk Mar 4 '16 at 19:05
  • $\begingroup$ No, I think I misunderstood something actually: I'd misread the question. We can interpret this question as being about the dynamical system on $\mathbb{Z}^k$ defined by $f(x_1,\ldots,x_k):=f(x_2,\ldots,x_k,\sum_{i=1}^kc_i\lfloor x_{k+1-i}/m\rfloor)$. $\endgroup$ – Ian Morris Mar 4 '16 at 19:45
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Do the $x_n$ and $y_n$ sequences have a name? Or is there a paper you can refer me to in which they are studied? $\endgroup$ – Aeryk Mar 6 '16 at 19:31
  • $\begingroup$ $x_i$ could be called an order $n$ linear recurrence relation. It is not hard to find an order $n+1$ recurrence for $y_i.$ $\endgroup$ – Aaron Meyerowitz Mar 6 '16 at 23:48

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.