|
|
arxiv.org/pdf/1609.05570.pdf
Abstract: Pisot sequences (sequences $a_n$ with initial terms $a_0=x, a_1=y$, and defined for $n>1$ by $a_n= \lfloor a_{n-1}^2/a_{n-2} + \frac{1}{2} \rfloor$) often satisfy linear recurrences with constant coefficients that are valid for all $n \geq 0$, but there are also cautionary examples where there is a linear recurrence that is valid for an initial range of values of $n$ but fails to be satisfied beyond that point, providing further illustrations of Richard Guy's celebrated “Strong Law of Small Numbers”. In this paper we present a decision algorithm, fully implemented in an accompanying Maple program (Pisot.txt), that first searches for a putative linear recurrence and then decides whether or not it holds for all values of $n$.
We also explain why the failures happen (in some cases the 'fake' linear recurrence may be valid for thousands of terms).
We conclude by defining, and studying, higher-order analogs of Pisot sequences, and point out that similar phenomena occur there, albeit far less frequently.
⋮
⋮
⋮
⋮
⋮
3. How to Prove that a Proposed Linear Recurrence for a Pisot Sequence Holds for All Values
For the sake of pedagogy, before discussing the general case, in this section we will study a specific example.
The sequence $E(4,7)$, A010901, let's call it $\{ a_n \}$, starts with
$$
4, 7, 12, 21, 37, 65, 114, 200, 351, 616, 1081, 1897, 3329, 5842, 10252, 17991, 31572, 55405, 97229, \dots \quad
$$
The OEIS entry formerly contained the conjecture that this satisfies the linear recurrence
$$
a_n = 2a_{n-1} - a_{n-2} + a_{n-3} \quad ,
$$
wth initial conditions
$$
a_0=4 \quad , \quad a_1=7 \quad , \quad a_2=12 \quad,
$$
together with the remark that this is satisfied for $n \leq 50000$.
To prove that this holds for all $n$ we proceed as follows (the same method was used by Max Alekseyev [Al] to establish the recurrence for $E(5,17)$ mentioned above). Recall that by the definition of Pisot sequences
$$
a_n:= \left\lfloor \, \frac{a_{n-1}^2}{a_{n-2}} +\frac{1}{2} \, \right\rfloor \quad .
$$
Let's define the sequence $b_n$ to be the (obviously unique) sequence satisfying the recurrence
$$
b_n = 2b_{n-1} - b_{n-2} + b_{n-3} \quad ,
$$
subject to the initial conditions
$$
b_0=4 \quad , \quad b_1=7 \quad , \quad b_2=12 \quad .
$$
We have to prove that $a_n=b_n$ for all $n \geq 0$. Using the symmetry of the “$=$” relation, we will prove the equivalent statement that $b_n=a_n$. In other words we must show that
$$
b_n \, = \, \left\lfloor \, \frac{b_{n-1}^2}{b_{n-2}} +\frac{1}{2} \, \right\rfloor \quad .
$$
But, recalling that $N=\lfloor x \rfloor$ is just shorthand for
$$
N \leq x < N+1 \quad,
$$
our task is to prove that
$$
b_n \leq \frac{b_{n-1}^2}{b_{n-2}} +\frac{1}{2} < b_n +1 \quad ,
$$
or equivalently,
$$
- \frac{1}{2} \leq \, \frac{b_{n-1}^2-b_n b_{n-2}}{b_{n-2}} < \frac{1}{2} \quad .
$$
Define the sequence $c_n$ by
$$
c_n:=b_{n-1}^2-b_n b_{n-2} \quad.
$$
From the linear recurrence defining $b_n$, we know that $b_n$ is given explicitly by
$$
b_n=
3.902586801\,\cdot \, { (1.754877667)}^{n}+ \left( 0.04870659984- 0.09364053397\,i \right) \left( 0.1225611669+ 0.7448617670\,i \right) ^{n}
$$
$$
+ \left(
0.04870659949+ 0.09364053445\,i \right) \left( 0.1225611669- 0.7448617670\,i \right) ^{n} \quad,
$$
where we have used floating-point numbers for convenience.
(To make this rigorous we could instead use rational interval arithmetic. We emphasize that we do not need to solve the characteristic polynomial of the recurrence exactly, although in this case of course we could, since it is a cubic polynomial.)
It follows that the sequence $c_n$ is given by
$$
c_n=
0.02472469487\,\cdot \, { (0.5698402912)}^{n}+ \left( 0.4876376523+ 1.233168614\,i \right) \left( 0.2150798545+ 1.307141279\,i \right)^{n}
$$
$$
+ \left( 0.4876376524- 1.233168615\,i \right) \left( 0.2150798545- 1.307141279\,i \right)^{n} \quad .
$$
Hence, since the absolute value of the largest terms in $c_n$, $0.2150798545 \pm 1.307141279\,i$, is $1.324717958$, we have
$$
|c_n|=O(1.324717958^n) \quad,
$$
and similarly
$$
b_n = \Omega( 1.754877667^{n}) \quad,
$$
where the implied constants can be easily made explicit if desired. It follows that
$$
\left|\frac{c_n}{b_{n-2}}\right| \, = \, O\left( \left(\frac{1.324717958}{1.754877667}\right)^n\right)= O((0.7548776664)^n) \quad
$$
and now one can easily find an $N_0$ such that $|\frac{c_n}{b_{n-2}}|< \frac{1}{2}$ for $n \geq N_0$, and the computer can check that this is valid for the first $N_0$ values. This completes the proof. |
|
