0
$\begingroup$

I have been playing around with integer sequences as of late, and the following question occurred to me:

Suppose for $m$ fixed we have some some initial values $a_1,\cdots,a_m$ and for all $n\in\mathbb{N}:n>m$ we have a linear recurrence relation $a_n=\sum_{i=1}^{m}\alpha_i a_{n-i}$ with $\alpha_i\in\mathbb{Z}$ (we could generalise to non-linear recurrence relations, but we focus on linear ones for the time being). Suppose we define $b_n\equiv a_n \bmod{10}$ with $0\leq b_n\leq9$ and define the decimal expansion of $x$ by the concatenation $0.b_1b_2b_3\cdots$. Which recurrence relations give $x\in\mathbb{Q}$? Which give $x\notin\mathbb{Q}$? Which $x$ are normal?

I then realised (an embarrassingly long time after initially formulating this problem) that $x$ is rational if and only if its decimal expansion is repeating after some finite number of digits or terminating (i.e. repeated zeroes after some finite number of digits), so this question essentially reduces to whether a given recurrence relation is periodic (after some finite number of 'leading terms') when reduced mod10. Computationally it is easier to reduce each term mod10 as it is calculated.

I have been playing around with the Fibonacci sequence (OEIS A000045) and the example $a_n=a_{n-1}-a_{n-4}, a_1=a_2=a_3=a_4=1$ (which is sadly not documented on OEIS) but without much clue of how to check if values reoccur or not.

Does anyone have any insights into this problem? Is it too broad to be solved in general? Are there any interesting cases you can think of and wish to highlight?

$\endgroup$
1
  • 4
    $\begingroup$ All linear recurrence relations give $x \in \mathbb{Q}$ and none give $x$ normal. See: Pisano periods. $\endgroup$ May 6 at 10:22

1 Answer 1

3
$\begingroup$

Set $B_n = (a_n,\ldots,a_{n+m-1})$ for $n \ge 1$. The sequence $(B_n)_{n \ge 1}$ thus defined takes values in a finite set (namely $\{0,\ldots,9\}^m$) and satisfies a recursion relation of the form $B_{n+1}=f(B_n)$. Therefore, it is eventually periodic: once you get any value for the second time, the periodic behaviour is forced. The linearity plays no role here.

$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.