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

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.

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.

• This site is not really for discussing contest problems unless there is some research angle of interest to professionals. Perhaps Art of Problem Solving would be better. – Todd Trimble Jan 30 '16 at 23:00
• Actually, Miklos Schweitzer competition is as close to research level as possible. If there are solutions anywhere in the web (not this particular problem), I would really appreciate the link. – Fedor Petrov Jan 30 '16 at 23:12
• An obvious remark is that one should show that the sequence is bounded. This would imply periodicity without any specific information about the period. – Lev Borisov Jan 31 '16 at 12:47
• I still think this should not be on MO. It may be a hard problem but is not a research problem, i.e., I doubt it arose independently in jack's research. Second, I assume whoever posed the problem in the competition (plus, I hope, some of the competitors) know how to solve it, so asking them and not MO is a more efficient way of getting the answer. – Felipe Voloch Jan 31 '16 at 13:53
• @FelipeVoloch Well, many questions I ask here do not arise in my research (some come from teaching, some from working on math competitions, some from pure curiosity), does it mean that they are not appropriate here? I do not think so. It is easy to make a 'research level question' from this: describe all linear reccurences for which such a sequence is always periodic. But why not start from this? – Fedor Petrov Jan 31 '16 at 17:02

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.

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 .

• Pictures corrected: I had originally implemented $\lceil x \rceil$ as ${\rm round}(x + \frac12)$, but that gave $x+1$ for $x \in \bf Z$ $-$ resulting in a somewhat different recursion, though it seems periodic too. Here's the previous screenshot: math.harvard.edu/~elkies/mo229714-.png – Noam D. Elkies Jan 31 '16 at 20:00
• Noam, how do you know to turn 72 degrees? – john mangual Feb 3 '16 at 21:58
• The eigenvalues of the corresponding linear transformation of ${\bf R}^2$ are $\exp \pm 2\pi i/5$ so it's a 72-degree rotation for an invariant quadratic form. (It had already been noted that this linear transformation is a 5th root of the identity.) – Noam D. Elkies Feb 3 '16 at 22:05

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

• Thanks for making this image! I notice that no orbits cross the lines $x=3$, $x=8$ or $x=21$. Can we prove this (and its generalization to other odd Fibonaccis)? If so, this fact coupled with its rotations under the $5$ fold symmetry proves the result. – David E Speyer Feb 2 '16 at 15:51
• Hmmm, what I wrote isn't exactly right. The orbit through $(8,27)$ crosses $x=8$. But I still think there is something here. – David E Speyer Feb 2 '16 at 16:33
• Neat. You might still rotate the y-axis by 18(?) degrees to retain the approximate fivefold symmetry. – Noam D. Elkies Feb 2 '16 at 18:15
• Yeah, it feels like one would need to find some "walls" that can not be crossed. I wonder if one can think of some congruences in the ring $\mathbb Z[x]/\langle x^2+x-1\rangle$ to allow for a better control after five iterations. – Lev Borisov Feb 2 '16 at 21:23
• @LevBorisov: You are right, there are some details missing for which I don't have the time to check. – Peter Mueller Feb 3 '16 at 0:27

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.

• Suggestion: Draw in the lines at $x=\tau y$ and $y = \tau x$, with $\tau = (1+\sqrt{5})/2$. I think that there are $10$ "wedges" which are permuted cyclically (the other boundaries are at $x=0$, $y=0$ and $x=-y$, which are already drawn. – David E Speyer Feb 4 '16 at 22:14
• There are already so many lines... Yes indeed, there appear to be wedges of 2 kinds, both resembling to a pentagonal version of the Sierpinsky triangle, with the colored shapes being the "iterations" of a certain fractal. – Wolfgang Feb 5 '16 at 8:21

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.

• Yes, one certainly has to use the identity $\omega F_i=F_{i-1}-(-\omega)^i$, together with bad rational approximately of $\omega$. This implies for instance $\lceil(\omega(\pm F_i+k)\rceil=\pm F_{i-1}+\lceil\omega k\rceil$ for each nonzero integer $k$ with $|k|<F_i$. Nevertheless, trying to work things out along this idea seems to be a pain. So someone probably has a better idea. – Peter Mueller Feb 3 '16 at 10:25
• Certainly, if the result is already known, then it is not worth sweating out the details. I do wonder what happens if one replaces $w$ by nearby numbers. For example, what happens if you do $2\cos(2\pi/7)$ as opposed to $2\cos(2\pi/5)$? What happens if you take a rational number nearby? Can you assure that there is a transcendental number near $w$ such that there is a recursive sequence like this that goes to infinity? What happens for higher order "almost linear" recursions with characteristic roots of length one? This must have been studied, but so far nobody gave a reference. – Lev Borisov Feb 3 '16 at 15:36
• I tried the $7$ instead of $5$. For initial values in $[1,100]^2$ there is periodicity. – Lev Borisov Feb 3 '16 at 16:01