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

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 .

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

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.