The sequence $a_{n+1}=\left\lceil \frac{-1+\sqrt{5}}{2}a_{n}-a_{n-1} \right\rceil$ is periodic

Question

Let $(a_{n})_{n \ge 1}$ be a sequence of integers such that for all $n \ge 2$:

$0\le a_{n-1}+\frac{1-\sqrt{5}}{2}a_{n}+a_{n+1} <1$.

Prove that the sequence $(a_{n})$ is periodic.

This question was asked at the Miklos Schweitzer Competition 2005, problem 2 (in Hungarian).

Since $(a_{n})$ is integer it follows that $a_{n+1}=\left\lceil \frac{-1+\sqrt{5}}{2}a_{n}-a_{n-1} \right\rceil$ is periodic.

Some discussion regarding this question can be found at Mathlinks, and apparently we can choose $a_{1}$ and $a_{2}$ to make this period as large as we want.

Any help would be appreciated, thanks.




I would like to clarify some points about this problem:

1) There is a ceiling function ($\lceil x \rceil$) at the recursive sequence which makes it considerably harder. The period is not 5 as claimed by some answers.

2) Miklos Schweitzer is not a conventional competition. This competition for undergraduate students is unique. The contest lasts 10 days with 10-12 problems, which are quite challenging and basically of research level. Moreover any literature can be used.

3) An example of Miklos Schweitzer problem can be found here at MO. It was indeed a very nice question with an even nicer solution. I'm not sure Art of Problem Solving would be better.

I am sorry for any inconvenience caused and I hope this question do not get closed.

Answer 1

Define the Fibonacci numbers by $f_0 = 0$, $f_1 = 1$, $f_{n+1} = f_n + f_{n-1}$, and the golden ratio by $\phi = \frac{\sqrt{5}+1}{2}$. Then it is easy to check that $f_n = \frac{\phi^n - (\tfrac{-1}{\phi})^n}{\sqrt{5}}$ and $(\phi-1)f_n = f_{n-1}-(\tfrac{-1}{\phi})^n$.

We will show that if five terms in a row are all less than $f_{2k}$ for some $k > 1$, then all $a_n$ are less than or equal to $f_{2k}.$

Suppose that $a_{n-1}, a_n$ are both positive. As is well known, we can find sets $I,J \subset \{2,3,4,...\}$ with $I \cap (I+1) = J\cap (J+1) = \emptyset$, such that $a_n = \sum_{i\in I} f_i$ and $a_{n-1} = \sum_{j\in J} f_j$. Put $x = \sum_{i\in I} (\tfrac{-1}{\phi})^i$ and $y = \sum_{j\in J} (\tfrac{-1}{\phi})^j$. By summing a geometric series, it's easy to show that we have $\frac{-1}{\phi^2} < x,y < \frac{1}{\phi}$. Expressing $a_{n+1}, ..., a_{n+5}$ in terms of $x$ and $y$, we get

$a_{n+1} = \sum_{i\in I}f_{i-1} - \sum_{j\in J} f_j + \alpha,\ \ \alpha = \lceil -x\rceil,$

$a_{n+2} = -\sum_{i\in I}f_{i-1} - \sum_{j\in J} f_{j-1} + \beta,\ \ \beta = \lceil\phi x + y + (\phi-1)\alpha\rceil,$

$a_{n+3} = -\sum_{i\in I}f_i + \sum_{j\in J} f_{j-1} + \gamma,\ \ \gamma = \lceil-\phi x-\phi y + (\phi-1)\beta - \alpha\rceil,$

$a_{n+4} = \sum_{j\in J} f_j + \delta = a_{n-1} + \delta,\ \ \delta = \lceil x+\phi y + (\phi-1)\gamma - \beta\rceil,$

$a_{n+5} = \sum_{i\in I}f_i + \epsilon = a_n + \epsilon,\ \ \epsilon = \lceil -y + (\phi-1)\delta - \gamma\rceil.$

Note that if we instead had $a_n$ positive and $a_{n-1}$ negative, then on writing $a_{n-1} = -\sum_{j\in J} f_j$ and $y = -\sum_{j\in J} (\frac{-1}{\phi})^j$, we still get $a_{n+4} = a_{n-1} + \delta$ and $a_{n+5} = a_n + \epsilon$, with $\alpha, \beta, \gamma, \delta, \epsilon$ defined as above. Note that in this case, we have the inequalities $\frac{-1}{\phi} < y < \frac{1}{\phi^2}$.

Claim: We always have $\delta, \epsilon \in \{-1,0,1\}$. Furthermore, if $0 < x < \frac{1}{\phi^2}$ and either $\frac{-1}{\phi^2} \le y \le \frac{1}{\phi} - \frac{x}{\phi}$ or $\frac{-1}{\phi} < y \le \frac{-1}{\phi^2} - \frac{x}{\phi}$, then $\delta \ge 0$ and $\epsilon \le 0$.

Proof of Claim: For the first part, note that

$a_n - a_{n+5} = (a_n - \frac{a_{n+1}}{\phi} + a_{n+2}) + \frac{1}{\phi}(a_{n+1} - \frac{a_{n+2}}{\phi} + a_{n+3}) - \frac{1}{\phi}(a_{n+2} - \frac{a_{n+3}}{\phi} + a_{n+4}) - (a_{n+3} - \frac{a_{n+4}}{\phi} + a_{n+5}),$

which is between $-1-\frac{1}{\phi}$ and $1+\frac{1}{\phi}$ by assumption. Thus $|\epsilon| = |a_{n+5}-a_n| \le 1$ (since it is an integer).

Now suppose that $0 < x < \frac{1}{\phi^2}$ and either $\frac{-1}{\phi^2} \le y \le \frac{1}{\phi} - \frac{x}{\phi}$ or $\frac{-1}{\phi} < y \le \frac{-1}{\phi^2} - \frac{x}{\phi}$. Then we immediately see $\alpha = 0$, and from

$-1 < y \le \phi x + y \le \frac{1}{\phi} + \phi x - \frac{x}{\phi} = \frac{1}{\phi} + x < 1$,

we see that

$\beta = \lceil\phi x + y\rceil = \begin{cases} 1 & \phi x + y > 0,\\ 0 & \phi x + y \le 0. \end{cases}$

From this together with

$\gamma = \lceil -\phi x - \phi y + \frac{\beta}{\phi}\rceil = \lceil -(\phi x + y) + \frac{\beta-y}{\phi}\rceil$

and $y > \frac{-1}{\phi}$ we can easily show

$1 \ge \gamma \ge \begin{cases} 1 & y \le 0\\ 0 & y > 0.\end{cases}$

That $\delta = \lceil x + \phi y + \frac{\gamma}{\phi} - \beta\rceil$ is at least $0$ follows from

$x + \phi y + \frac{\gamma}{\phi} - \beta = (\frac{\phi x + y}{\phi} - \beta) + (y + \frac{\gamma}{\phi}) > -1 + 0.$

Finally, we must show that $\epsilon =\lceil -y + \frac{\delta}{\phi} - \gamma\rceil$ is at most $0$. We split into three cases. First case:

$\gamma = 0\implies y>0\implies \beta = 1\implies \delta = 0\implies \epsilon = \lceil -y \rceil = 0.$

Second case:

$\gamma = 1\ \&\ y \ge \frac{-1}{\phi^2} \implies \epsilon \le \lceil \frac{1}{\phi^2} + \frac{1}{\phi} - 1\rceil = 0.$

Third case:

$\gamma = 1\ \&\ y \le \frac{-1}{\phi^2} - \frac{x}{\phi} \implies \delta \le \lceil \frac{-1}{\phi} + \frac{1}{\phi} - \beta\rceil = 0 \implies \epsilon \le \lceil \frac{1}{\phi} - 1\rceil = 0.$

Corollary: If $a_n = f_{2k}$ and $-f_{2k+2} \le a_{n-1} < f_{2k+3}-1$, then $a_{n+5} \le a_n$.

Proof: We just have to check that the claim applies. We have $x = (\tfrac{-1}{\phi})^{2k} = \frac{1}{\phi^{2k}}$, so we just need to check that either $\frac{-1}{\phi^2} \le y \le \frac{1}{\phi} - \frac{1}{\phi^{2k+1}}$ or $y \le \frac{-1}{\phi^2} - \frac{1}{\phi^{2k+1}}.$

Suppose first that $a_{n-1} \ge 0$. Then from $a_{n-1} < f_{2k+3} - 1 = \sum_{j=1}^{k+1} f_{2j}$, we see that $y \le \sum_{j=1}^k \frac{1}{\phi^{2j}} = \frac{1}{\phi} - \frac{1}{\phi^{2k+1}}.$

Now suppose that $a_{n-1} < 0$. Note that in this case we automatically have $y \le \frac{1}{\phi^2} \le \frac{1}{\phi} - \frac{1}{\phi^{2k+1}}.$ Write $a_{n-1} = -\sum_{j\in J} f_j$ for some $J \subseteq \{2,3,...\}$ with $J\cap (J+1) = \emptyset.$ If $2 \not\in J$, then $y > -\frac{1}{\phi^4}-\frac{1}{\phi^6} -\cdots = -\frac{1}{\phi^3} > -\frac{1}{\phi^2}$. If $J = \{2\}$ or if $2\in J$ and the second smallest element of $J$ is odd, then we have $y \ge -\frac{1}{\phi^2}$ as well. Now suppose that $2\in J$ and the next smallest element of $J$ is $2l$. Since $a_{n-1} \ge -f_{2k+2}$, we must have $l \le k$, so

$y < \frac{-1}{\phi^2} - \frac{1}{\phi^{2l}} + \frac{1}{\phi^{2l+3}} + \frac{1}{\phi^{2l+5}} + \cdots = \frac{-1}{\phi^2} - \frac{1}{\phi^{2l+1}} \le \frac{-1}{\phi^2} - \frac{1}{\phi^{2k+1}}.$

To finish: Note that if $a_n = f_{2k}$ and $a_{n-1}, a_{n+1} \le f_{2k}$, then $a_{n-1} + a_{n+1} = f_{2k-1}$, so $-f_{2k-2} \le a_{n-1} \le f_{2k},$ and we can apply the Corollary to see that $a_{n+5} \le f_{2k}.$ Of course, if $a_n < f_{2k}$ then we have $a_{n+5} \le a_n+1 \le f_{2k}$ (by the Claim) as well.

Answer 2

This is not a solution, but a plot suggesting that the recursion has the geometric structure of a planar quasicrystal with the fivefold symmetry of a Penrose tiling:

_{(source: harvard.edu)}

It's obtained by connecting each integer point $(x,y)$ to its image, rotated by 72 degrees with respect to the quadratic form invariant under the linearized recursion $(x,y) \mapsto (y, \frac{-1+\sqrt{5}}{2} y - x)$ [without ceiling functions, whose removal makes this map an exact 72-degree rotation]. The center is the green dot; other points get circles whose sizes keep track of how many times mod 5 they've been rotated; the orbits of $(5,0)$ and $(13,0)$ are in blue and red respectively. (The Mathlinks discussion suggested that starting at Fibonacci numbers yields long orbits.) For a larger picture see http://math.harvard.edu/~elkies/mo229714.pdf .

Answer 3

Another visualization, similar to Noam's, together with a modification of a comment by David, might lead to a solution of the question: Define $T:\mathbb Z^2\to\mathbb Z^2$ by $T(a_1,a_2)=(a_6,a_7)$. It is easy to see that $T(v)-v$ is in $\{-1,0,1\}^2$ (and distinct from $(1,-1)$ and $(-1,1)$) for all $v\in\mathbb Z^2$. Let $F_i$ be the $i$-th Fibonacci number. Then all points on the border of the triangle $\Delta_{2i+1}$ with vertices $(z,-z)$, $(-z,z)$, $(-z,-z)$ with $z=F_{2i+1}-1$ seem to be fixed under $T$. So, by the other remark about the step lengths of $T$, $\Delta_{2i+1}$ is invariant under $T$. Similarly, the triangles $\Delta_{2i}$ with vertices $(z,-z)$, $(-z,z)$, $(z,z)$ where $z=F_{2i}$ seem to have the property that each point on the border is either fixed, or still stays on the border.

Working out these observations seems to be somewhat technical. Set $\omega=\frac{\sqrt{5}-1}{2}$. The identity $\omega F_i=F_{i-1}-(-\omega)^i$, together with bad rational approximately of $\omega$, implies for instance $\lceil(\omega(\pm F_i+k)\rceil=\pm F_{i-1}+\lceil\omega k\rceil$ for each integer $k$ with $|k|<F_i$. That's something which would be needed.

The following draws the lines connecting $v$ with $T(v)$ (and nothing if $v=T(v)$) and the triangles $\Delta_j$.

Answer 4

Tilting Peter Mueller's image by -18° as suggested by Noam D. Elkies and coloring the interior of certain orbits shows again the 5-fold symmetry, self-similarity and the closeness to Penrose tilings.

Answer 5

This is really more of an extended comment, but it would be unpleasant to write it in that format. I am commenting on the suggestion of Peter Mueller to argue that the boundary of the triangles he constructs goes to the boundary.

While I don't have a complete answer, here is a plausible line of attack, which clarifies the role of the Fibonacci numbers.

Let me define $\epsilon_n=a_{n-1}-wa_n+a_{n+1}$ to be the "error terms" of the recursion. Then we have $$ a_2-a_7 = \epsilon_3+w\epsilon_4-w\epsilon_5-\epsilon_6. $$ I would like to show (among other things) that if $a_2=F_{2i+1}-1$ and $-a_2\leq a_1\leq a_2$ then $a_2-a_7\geq 0$. For this, consider $$\epsilon_3+w\epsilon_4=a_2+w(a_4+a_5).$$ This lies in $a_2+ w\mathbb Z$.

The nature of $a_2=F_{2i+1}-1$ is (I think) such that the fractional part of $a_2/w$ is close to $1$. In fact, it is not possible to achieve a larger fractional part with smaller positive integers. As a consequence, since $\epsilon_3+w\epsilon_4$ is positive, it will be either larger than $w$ or at least very close to $w$.

When we combine this with $-w e_5-e_6$ which are at most $-w$ and $-1$, but can not be too close to them, we see that overall we have $a_2-a_7>-1$, as desired.

The devil is in the detail, of course. We need to be specific as to how close $\epsilon_5,\epsilon_6$ could be to $1$: this is where the bound on $a_1$ must come in. It looks tedious but doable. There are other inequalities to check, but I am guessing that similar ideas might do the job.