Bounded sequence with $a_n=|a_{n+1}-a_{n+2}|$

Suppose $a_0,a_1>0$ are distinct, and $a_n=|a_{n+1}-a_{n+2}|$ for all $n\geq 0$. Is it possible that the sequence is bounded? From my experiment, the sequence seem to always be unbounded.

We have $\pm a_n=a_{n+1}-a_{n+2}$, so $a_{n+2}=a_{n+1}\pm a_n$. For each $n$ we can choose plus or minus. What can we do to show that the magnitude of the sequence must grow?

• Shouldn't the terms be $a_n=|a_{n-1}-a_{n-2}|$ ? – user99680 Nov 15 '13 at 2:14
• @user99680 No, the equation is correct as I typed. It's defined in an unusual way :) – Kunal Nov 15 '13 at 2:24
• I'm curious: Where did this problem come from? Is it some type of homework, is it related to another problem you're considering, or do you just like to play with math and you made up this question out of thin air? All of these possibilities are perfectly legitimate, by the way. – Will Nelson Nov 15 '13 at 21:15
• @WillNelson It is the last one. I just thought it would be interesting to consider a sequence in which there are two possibilities for the next value in the sequence ($a_{n+2}$ here). Nice proof, by the way! – Kunal Nov 16 '13 at 1:20

Although it can be shown $$(*)\ \limsup_{n\to\infty} a_n = +\infty,$$ it is not necessarily the case that $$\liminf_{n\to\infty} a_n = +\infty.$$ Example: $1,2,3,5,2,7,9,2,11,13,2,\ldots$.

I now show $(*)$ above.

We know: $a_0,a_1>0$. $a_0 \ne a_1$. $a_n = |a_{n+2} - a_{n+1}|$.

Clearly, $a_n\ge 0$ and for all $n$, either (1) $a_{n+2} = a_{n+1} + a_n$, or (2) $a_{n+1} > a_n$ and $a_{n+2} = a_{n+1} - a_n$.

Fix an $\epsilon>0$ such that $a_0, a_1, \mbox{ and } |a_1-a_0|>\epsilon$.

Observe that $a_n, a_{n+1}, \mbox{ and } |a_{n+1} - a_n|>\epsilon$ for all $n$. To see this, use induction. It's true for $a_0$ and $a_1$ by assumption. Suppose it's true for $a_n$ and $a_{n+1}$. We know $$a_{n+2} \ge |a_{n+1} - a_n| > \epsilon$$ and $$|a_{n+2} - a_{n+1}| = a_n > \epsilon.$$ Thus, the induction step is proved.

Finally, observe that for all $n$, either $a_{n+1} - a_n > \epsilon$ or $a_{n+2} - a_n > \epsilon$. If $a_{n+1} > a_n$, then $a_{n+1} - a_n > \epsilon$ by the lemma shown above. If $a_{n+1} < a_n$, then $a_{n+2} = a_n + a_{n+1}$, and so $a_{n+2} - a_n = a_{n+1} > \epsilon$, again by the lemma above.

Since for all $n$, $a_{n+2} - a_n > \epsilon$ or $a_{n+1} - a_n > \epsilon$, it follows $a_n$ is arbitrarily large for some $n$.