
> 
> 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](http://www.math.u-szeged.hu/~mmaroti/schweitzer/schweitzer-2005.pdf) (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](https://www.artofproblemsolving.com/community/q1h1110221p5055383),
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](https://mathoverflow.net/questions/67436/is-there-any-sequence-a-n-of-nonnegative-numbers-for-which-sum-n-geq-1a-n).
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.



The sequence $a_{n+1}=\left\lceil \frac{-1+\sqrt{5}}{2}a_{n}-a_{n-1} \right\rceil$ is periodic
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.


