Yes, actually this is a Romanian proposal by Mihai Bălună. Have fun with this nice problem.

? yes? there are thousands of proofs given(in particular, by darij and me), that this sequence is always unbounded.

Well, it's not exactly that I didn't give a proof, but it wasn't quite correct either... So, the problem is not too trivial... darij

I think a_i must be position. BTW,I am intrested in this problem.can you post the solution.

First, some basic facts: all the terms of the sequence are positive, two consecutive terms are always different, we have $u_{n+2}=u_{n+1}-u_{n}$ or $u_{n+2}=u_{n+1}+u_{n}$, but if $u_{n}>u_{n+1}$, then necessarily, $u_{n+2}=u_{n+1}+u_{n}$. I will then prove the following result: if $u_{n}<u_{n+1}$ for some integer n, then for some $m>n$ we have $u_{n+1}<u_{m}$ and $u_{n}+u_{n+1} < u_{m+1}$. Property 1: let a,b be two positive real numbers with $a<b$ and suppose that $u_{n}=b-a$,$u_{n+1}=2kb-(2k-1)a$ for some integer k>0. If $u_{n+2}=u_{n+1}-u_{n}$ then we have $u_{n+2}<u_{n+1}$ so, from a previous remark, we have necessarily, $u_{n+3}=u_{n+1}+u_{n+2}$. We check that in that case, $u_{n+2}>b$ and $u_{n+3}>a+b$. Property 2: let a,b be two positive real numbers with $a<b$ and suppose that $u_{n}=2kb-(2k-1)a$,$u_{n+1}=(2k+1)b-2ka$ for some integer k>0. If $u_{n+2}=u_{n+1}+u_{n}$, then We check that $u_{n+1}> b$ and $u_{n+2}> a+b$. Suppose now that $a=u_{n}<u_{n+1}=b$. If $u_{n+2}=a+b$, the result is proved. So suppose that $u_{n+2}=b-a$. Then necessarily, $u_{n+3}=u_{n+2}+u_{n+1}=2b-a$. Property 1 (with k=1) shows that the result is proved if $u_{n+4}=u_{n+3}-u_{n+2}$, so suppose that $u_{n+4}=u_{n+3}+u_{n+2}=3b-2a$. Property 2 (with k=1) proves the result if $u_{n+5}=u_{n+4}+u_{n+3}$ so suppose that $u_{n+5}=u_{n+4}-u_{n+3}=b-a$.$u_{n+4}>u_{n+5}$, so $u_{n+6}=u_{n+5}+u_{n+4}=4b-3a$. And so on (= induction) we show that the result is proved by using property 1 and 2 unless we have the following sequence: a,b,b-a,2b-a,3b-2a,b-a,4b-3a,5b-4a,...,b-a,2kb-(2k-1)a,(2k+1)b-2ka,b-a,... But in that last case, 2kb-(2k-1)a, can be as high as we want, for example higher than b, and (2k+1)b-2ka higher than a+b. The result is therefore proved. Now, there are always consecutive terms such that $u_{n}<u_{n+1}$ (if $u_{n}>u_{n+1}$ for some n, then $u_{n+2}=u_{n}+u_{n+1}>u_{n+1}$). Name $a=u_{n}<u_{n+1}=b$. Then an easy induction using the result shows that one can find terms higher than $k(a+b)$ for every integer k, which shows that such a sequence can not be bounded.

This problem was used as problem 1 of the final exam of the 3rd TST of Taiwan 2005.

I'm not really clear with Xell's solution. Can anybody elaborate?

Wasnt this posted before??? Bomb

Since $a_n = |a_{n+1}-a_{n+2}|$, we see that all elements of $\{a_n\}$ are nonnegative. We first show that all elements of $\{a_n\}$ are positive. Suppose for the sake of contradiction that there exists an $i \ge 0$ such that $a_{i+2}=0$. (Obviously $a_0,a_1 \ne 0$ since this is given.) $a_i = |a_{i+1} - a_{i+2}|$, so $a_i = a_{i+1}$. Let $x=a_i=a_{i+1}$. We will show that for any $j \ge 0$, the set $\{a_k|j \le k \le i_1 \}$ has only two distinct elements: $x$ and $0$. For the base case we have $j=i$. We will induct backwards on $j$, from $i$ to $0$. By the inductive hypothesis, $a_{j+1} \epsilon \{0,x\}$, $a_{j+2} \epsilon \{0,x\}$. Since $a_j = |a_{j+1} - a_{j+2}|$, $a_j \epsilon \{|0-0|,|0-x|,|x-0|,|x-x|\} = \{0,x\}$. (Remember that $x$ is nonnegative.) This completes the induction. So $a_0 \epsilon \{0,x\}$ and $a_1 \epsilon \{0,x\}$. Since we are given that $a_0$ and $a_1$ are positive, $a_0=a_1=x$. (If $x=0$, then we have our contradiction.) But we are also given that $a_0$ and $a_1$ are different, so we have our contradiction. Therefore, all elements of $\{a_n\}$ are positive, and as a corollary, no two consecutive elements of $\{a_n\}$ are equal. We will now show that $a_0$ cannot be the largest element of $\{a_n\}$. Suppose for the sake of contradiction that it is. Let $a_0 = x/k$, and let $a_1 = 1/k$. Then $k>0$ and $x>1$. $ka_0 = x$ $ka_1 = 1$ $ka_2 = b$ $a_0 = |a_1 - a_2|$, so $ka_0 = k|a_1 - a_2| = |ka_1 - ka_2| = |1-b|$. Then $x=|1-b|$. So $x=1-b$ or $x=b-1$. The former is impossible since it would imply that $b=1-x$, which would make $b$ negative. So $x=b-1$, and $b=x+1$. $b>x$. So $a_2 = b/k > x/k = a_0$. This contradicts the assumption that $a_0$ is the largest element of $\{a_n\}$. We will now suppose, for the sake of contradiction, that $a_{i+1}$, for $i \ge 0$, is the largest element of $\{a_n\}$. Let $a_0 = 1/k$, and let $a_1 = x/k$. Then $k>0$ and $x>1$. $ka_i = 1$ $ka_{i+1} = x$ $ka_{i+2} = x-1$ (It can't be $1-x$, since this is negative.) $ka_{i+3} = b$ $ka_{i+1} = k|a_{i+2} - a_{i+3}| = |ka_{i+2} - ka_{i+3}| = |x-1-b|$ $x=|x-1-b|$ The option $x=x-1-b$ is impossible, since it implies $b=-1$. Then $x=b+1-x$, and $2x=b+1$, and $b=2x-1$. Suppose $2x-1<x$. Then $x-1<0$, so $x<1$. Contradiction. So $a_{i+3} = b/k > x/k = a_{i+1}$. This contradicts our assumption that $a_{i+1}$ is the largest of $\{a_n\}$. We conclude that $\{a_n\}$ does not have a largest element, and it is therefore not bounded. QED.

This was also the first problem of the first MOP test for the Black group (USAMO winners) in 2005.

darktreb wrote: This was also the first problem of the first MOP test for the Black group (USAMO winners) in 2005. Also in the Romanian TST in 2005 Spread problem

What a easy problem???? There is no bounded.It is unlimited or it has at least 2 limits

Philip_Leszczynski wrote: [...] We conclude that $\{a_n\}$ does not have a largest element, and it is therefore not bounded. QED. You can't make that assumption, e.g the sequence $a_i = 1- \frac{1}{i}$ doesn't have a largest element and is bounded.

I'm guessing nipolo's brief "proof" is incorrect? Or if it is correct, can someone elaborate?

It is obvious that all numbers in the sequence are non-negative. Suppose that for some $i$, $a_i$ is the smallest number in the sequence up to $i$, ie. there exists no $j < i$ such that $a_j \leq a_i$. Then $a_{i-1} > a_i$, so $a_{i-2} = a_{i-1} - a_i$, so $a_{i-1} > a_{i-2}$, so $a_{i-3} = a_{i-1} - a_{i-2} = a_i$, which gives a contradiction, unless i < 3. This means that the smallest number in the sequence must be $a_0$, $a_1$ or $a_2$. Call this smallest number $m$. Because $a_0$ and $a_1$ are different and non-zero, $m > 0$. For any $i$, $a_i = | a_{i+1} - a_{i+2} |$. If $a_{i+1} > a_{i+2}$, $a_i = a_{i+1} - a_{i+2}$, so $a_{i+1} \geq a_i + m$. If $a_{i+2} > a_{i+1}$, $a_i = a_{i+2} - a_{i+1}$, so $a_{i+2} \geq a_i + m$. So for every number in the sequence, there is another number in the sequence that is at least $m$ larger. $m$ is a positive constant, so the sequence is unbounded. This was also in one of the South African monthlies (selection tests by post). In my origional solution I made the mistake of not showing by how much the sequence is increasing, which does not prove that the sequence is unbounded, as Zetax pointed out.

I can't see my mistake. If $a_0 = k$ and $a_1 = 2k$, then we have $a_2 = |a_1 - a_0| = k$ and $a_3 = |a_2 - a_1| = k$ and $a_4 = |a_3 - a_2| = 0$ And then all we get are zeros and $k$s. Where is my mistake?

Watch the indices carefully - it's $a_{\boxed{n}}=|a_{\boxed{n+1}}-a_{\boxed{n+2}}|$ and NOT $a_{n+2}=|a_{n+1}-a_n|$.

At the Romanian Selection Test, Sasha Zamorzaev from Moldova (invited to sit the test) provided a solution based, as far as I remember, on the sequence made by the $\max$ of three consecutive terms (or absolute difference of consecutive terms) from the original sequence, which actually reached all truths about this type of sequence in a couple short elegant lines. Unfortunately his solution is lost - and I lack the drive to try to reconstruct it

$\left\{a_{n}\right\}; (i) a_0, a_1 \ne 0, (ii) a_0 \ne a_1, (iii) a_n=\left| a_{n+1}-a_{n+2} \right|$ (Note that (iii) is equivalent to $a_{n+2}=a_{n+1} \pm a_{n}$) Suppose that $\left\{a_{n}\right\}$ is bounded; then there exists the biggest term $a_{N} (N \in \mathbb{N} \cup \left\{0 \right\})$. Let $a_{N}=M$. We first observe the following facts; (1) $\forall n \in \mathbb{N} \cup \left\{0\right\} ; a_{n} \ge 0$ (because $a_{n}=\left| a_{n+1}-a_{n+2} \right| \ge 0$) (2) $\forall n \in \mathbb{N} \cup \left\{0\right\} ; a_{n} \le M$ (because of our assumption) Now we separate the problem into two cases the value of $a_{N+1}$; $a_{N+2}=a_{N+1} \pm a_{N}$ Case I. $a_{N+2}=a_{N+1}+a_N$ $a_{N+2} \ge a_{N}(\because (1))=M$ $\therefore a_{N+2}=M$ $\therefore a_{N+1}=0$ Because of (i), N can't be 0. So $a_{N+1}=a_{N} \pm a_{N-1}$. Then $a_{N-1}$ has to be $M$($\because (1)$) Because of (ii), N can't be 1. So $a_{N}=a_{N-1} \pm a_{N-2}$. Then $a_{N-2}$ has to be $0$ Because of (i), N can't be 2. So $a_{N-1}=a_{N-2} \pm a_{N-3}$. Then $a_{N-3}$ has to be $M$($\because (1)$) We can apply the same process for $a_{N-2}(=0)$ and $ a_{N-3}(=M)$ which we applied for $a_{N+1}(=0)$ and $a_N(=M)$. It yields $N \ne 3, 4, 5 $ and $a_{N-5}=0$ and $a_{N-6}=M$. We can repeat the process infinitely many times, then $N$ can't be $0, 1, 2, 3, 4, 5, \cdots$. This makes a contradiction. Case II. $a_{N+2}=a_{N+1}-a_N$ $a_{N+1}-a_{N}=a_{N+2} \ge 0 (\because (1))$, so $a_{N+1}=M(\because (2))$ Similarly, we can get $a_{N+2}=0$ Now we can apply the method for $a_{N+1}(=M)$ and $a_{N+2}(=0)$ which we used in Case I. Then $N+1 \ne 0, 1, 2, 3, 4, 5, \cdots$, and this also makes a contradiction. Therefore, the sequence $\left\{a_{n}\right\}$ should be unbounded. $Q. E. D.$ P. S.; Oh no my poor English skill

Let $x=a_0$ and $y=a_1$ for simplicity. First, notice that the sequence is strictly positive because no two consecutive terms can be equal. Define $M_n$ to be the maximum of the terms $a_0, a_1, \cdots, a_{2n-1}$ for $n \geq 1$. Claim. The difference $|a_{2n+1} - a_{2n}|$ strictly increases as $n \geq 0$ increases. Proof. Suffices to look at the first four terms. The second term $y$ is precisely the absolute difference between the third and fourth terms, but evidently $y>y-x$. $\blacksquare$ Now, the only possibilities for the first four terms are $$\{a_0, a_1, a_2, a_3\} \in \{\{x, y, y-x, 2y-x\}, \{x, y, x+y, x\}, \{x, y, x+y, x+2y\}\}.$$Thus, we have $M_2 \geq M_1+y-x$. The claim then implies $$M_n > M_1 + (n-1)(y-x)$$for all $n$. However, the RHS clearly approaches infinity, so the sequence cannot be bounded.

The answer is no. Suppose $(a_i)$ was bounded. First we get that $a_i\ge 0$ for all $i$. Claim: $a_n \ge 0$ for all $n$. Proof: Suppose some $n$ satisfied $a_n = 0$. Note $n\ge 2$. Then $a_{n+1} = a_{n-1}, a_{n-1} = a_{n-2}$, which gives that $a_{n-3} = 0$. Repeating this process we find that $a_0 = 0, a_1= 0$, or $a_2 = 0$, which implies $a_2 = 0$. But then $a_0 = a_1$, contradiction. $\square$ Claim: $a_{n+3}\ge a_n$ for all $n$. Proof: Note that $a_{n+2}\in \{a_{n+1} - a_n, a_{n+1} + a_n\}$ and $a_{n+3}\in \{a_{n+2} - a_{n+1}, a_{n+2} + a_{n+1}\}$ by the problem condition. If $a_{n+2} = a_{n+1} + a_n$, then $a_{n+3} \in \{a_n, 2a_{n+1} + a_n\}$, which implies $a_{n+3} \ge a_n$. If $a_{n+2} = a_{n+1} - a_n$, then $a_{n+3}\in \{-a_n, 2a_{n+1} - a_n\}$. Since $a_{n+3}\ge 0$, $a_{n+3} = 2a_{n+1} - a_n$. Since $a_{n+1}\ge a_n$, $a_{n+3}\ge 2a_n - a_n = a_n$, as desired. $\square$ Now, the three sequences $(a_{3i}), (a_{3i+1}), (a_{3i+2})$ are each increasing. Since $(a_i)$ is bounded they are all eventually constant, so $a_n = a_{n+3}$ for all $n\ge C$ for some constant $C$. Let $a_C = x, a_{C+1} = y$. Note that $a_{C+2} \in \{y-x, y+x\}$ and $y = |a_{C+3} - a_{C+2}| = |x - a_{C+2}|$. If $a_{C+2} = y-x$, then $|2x-y| = y$. Since $x>0$, we have $x=y$. This is absurd because it implies $a_{C-1} = 0$, contradiction. Thus, $a_{C+2} = y+x$. Now we have $y+ x = a_{C+2} = |a_{C+3} - a_{C+4}| = |x-y|$, which implies either $x=0$ or $y=0$, contradiction.

Clearly, $a_n$ is nonnegative for all $n$ and $a_{n+2}=a_{n+1}-a{n}$ or $a_{n+1}+a_n$. Let $n$ be the smallest index such that $a_n=a_{n+1}$. Then, $a_{n-1}=0.$ However, that implies $a_{n-2}=a_{n-3}$, contradiction. Therefore, consecutive terms are different. Suppose that the sequence is bounded, then let $m$ be the maximum value and $M$ be the index such that $a_M=m$. Note that $a_{M-1}$, $a_{M+1} < m$. $a_{M+1}$ can't be $a_M+a_{M-1}$ so it has to be $a_M-a_{M-1}$. Now, $a_{M+1} < a_M$ so $a_{M+2}$ cannot be $a_{M+1}-a_M$ so it must be $a_{M+1}+a_M=2a_M-a_{M-1}>a_M$, contradiction. Therefore, the sequence is not bounded.

Note that $a_{n+2} = a_{n+1} + a_n$ or $a_{n+2} = a_{n+1} - a_n$. If the former case is always true, then we are trivially done. Otherwise, there exists an $n$ with $a_n > a_{n+1}$. Shift the sequence so that $a_0 > a_1$. Lemma 1: For all $n$, $a_n \ge a_1$. Proof: We use induction, base cases $n=0, 1$. We can check that $a_2 = a_0 + a_1 > a_1$. For $n > 2$, if $a_{n} = a_{n-1} + a_{n-2}$, we are done. Otherwise, \[a_{n} = a_{n-1} - a_{n-2} = a_{n-3} + a_{n-2} - a_{n-2} = a_{n-3} \ge a_1\] Lemma 2: For all $n$, either $a_{n+1} \ge a_n + a_1$ or $a_{n+2} \ge a_n + a_1$. Proof: If $a_{n+1} = a_n + a_{n-1} \ge a_n + a_1$ are we done. Otherwise \[a_{n+1} = a_n - a_{n-1} < a_n \implies a_{n+2} = a_{n+1} + a_n \ge a_n + a_1\] Hence, we can construct an infinite subsequence, each term at least $a_1$ greater than the previous, so the sequence must be unbounded.

If someone can please make sure that this solution is right, that would be appreciated, thank you! (I'm really iffy on this solution but it might work) The sequence must be unbounded. Observe that all terms are positive for obvious reasons. As a start, note that $a_{n+2} = a_{n+1} \pm a_n$ for some choice of sign. Now the sequence either starts increasing, or it starts decreasing; but if it starts decreasing, then it must increase immediately after that since we can't have any negative terms. Henceforth assume $a_0 < a_1$. Moreover assume that $a_1 > a_2$, as otherwise we either find a term where that happens or the sequence is trivially unbounded (always addition). Call a value $a_i$ a $difference$ if $a_i = a_{i-1} - a_{i-2}$. $\textbf{Claim.}$ The smallest difference is $a_1 - a_0$. $\textit{Proof.}$ We have our sequence starting $a_0$, $a_1$, $a_1 - a_0$. We are forced to have $a_3 = 2a_1 - a_0$. Subtracting now gets us a difference of $a_1 > a_1 - a_0$. Adding again and subtracting after that, we obtain a difference of $a_1 - a_0$. Observe that if we have $a$, $b$, $a + b$ as the sequence, the difference will be $a$; i.e. after a sufficient amount of adding, the difference will be $2$ terms back. But after the second addition we just simply keep looking further at the increasing sequence $a_1 - a_0, 2a_1 - a_0, 3a_1 - 2a_0$ $\cdots$ so the next difference will always be at least $a_1-a_0$. Now if at any point in the sequence we have $a$, $b$, $b-a$, we are forced to add the difference $b-a$ to $b$; if this happens finitely many times again the sequence is trivially unbounded (infinite adding wahoo) but if it happens infinitely many times, we add a difference of at least $a_1 - a_0$ each time; thus it is unbounded.

The answer is no, the sequence is always unbounded. Clearly each of these terms are positive, and no two consecutive terms are equal. Consider pairs of consecutive terms(the same pair appearing multiple times in the sequence counts as a different pair). If a pair is decreasing, call it a fruity pair. If there are finitely many fruity pairs, then the sequence is eventually strictly increasing, so it is unbounded. Therefore, there are infinitely many fruity pairs. So consider what happens when you move from one fruity pair to the next. I claim that either (the second number increases) or (it stays the same and the first one increases). Suppose that the first fruity pair is $(a,b)$. Then the next term has to be $a+b$, and the term after that can either be $a$(in that case we have completed our larger fruity pair) or $a+2b$. The next term can be $b$(in that case we have completed our larger fruity pair) or $2a+3b$. Eventually this is going to get to $F_{k}a+F_{k+1}b$ and $F_{k+1}a+F_{k+2}b$, and when we finally decide to subtract the next term is $F_{k-1}a+F_{k}b$ which is obviously greater than $b$. Therefore our claim is true. If the second number keeps staying the same, then the first number is unbounded. If the second number doesn't keep staying the same, then the second number is unbounded. $\blacksquare$

No it cannot be. Consider two consecutive terms $a,b$ with $a<b$ which clearly must exist. (take either $a_0,a_1$ or $a_1,a_2$) then either the next term is $b+a$ giving us another pair $b,b+a$ or it is $b-a$ and then the next term will be $2b-a$ giving us pair $b-a,2b-a.$ In this process the greater term of each pair increases by either $a$ or $b-a.$ Thus the increase is $\ge \min(a,b-a)=x$ which are the difference and the smaller term in our pair. However now notice that $\min(b,(b+a)-b)=\min(a,b)\ge\min(a,b-a)=x$ and $\min(b-a,(2b-a)-(b-a))=\min(b-a,b)\ge\min(a,b-a)=x$ so as long as we repeat this both the smaller term and the difference in each of these pairs will be $\ge x.$ Thus at each step the largest term increases by at least $x$ so it must be unbounded.

blackbluecar wrote: The sequence is unbounded... Notice that $a_2$ and $a_3$ are certainly positive so lets say wlog that $a_0$ and $a_1$ are positive. Notice that $a_k=u \cdot a_0+v \cdot a_1$ for some positive integers $u$ and $v$. Thus, if $b_1,b_2,...$ is an increasing subsequence of $a_1,a_2,...$ then it must be unbounded. Why must it be unbounded? If e.g. $a_0 = 1$ and $a_1 = 2$, so $a_k = u_k + 2v_k$ and we might have $u_{k+1} = u_k + 2A$, $v_{k+1} = v_k - A$. This would imply $a_{k+1} = a_k$ which is not really possible, as almost all solutions show, but the situation here is evidence that the unboundedness is not too obvious perhaps? What if the increments can be some very small linear combinations of $a_0$ and $a_1$?

Assume the sequence is bounded. Notice that no value is equal to zero and so all values are positive (furthermore no adjacent values are equal). For any value $i$ let $f(i)\in \{i+1,i+2\}$ be a value such that $a_{f(i)}>a_i$. This value exists as it is impossible to have $a_{i+1},a_{i+2}<a_i$. Then we can create a sequence of values $s_i$ such that \[a_{s_1}<a_{s_2}<\dots<a_{s_n}<\dots\]and also choose the smallest constant $C$ which is at least each of these values. Write $b_i=a_{s_i}$ for convenience. Now we can analyze the relationship between three consecutive $s_n$, $s_{n+1}$, and $s_{n+2}$ for large $n$. Notice that $s_{n+2}=s_n+2$ and $s_{n+1}=s_n+1$ cannot happen; this would imply $b_{n+2}=b_{n+1}+b_n>C$. Notice that $s_{n+2}=s_n+4$ and $s_{n+1}=s_n+2$ cannot happen; this would imply \[(b_{n+1}-b_n)+(b_{n+2}-b_{n+1})=b_{n+1}.\] Notice that all remaining cases necessarily have $b_n$, $b_{n+1}$, and $b_{n+2}$ in an arithmetic sequence. Hence we violate the boundedness condition. Done.

First of all, it's clear that $a_n$ is nonnegative for all $n$ and that $a_{n+2}= a_{n+1}-a_{n}$ or $a_{n+2}= a_{n+1}+a_{n}$ Claim : All consecutive terms are different. Assume FTSOC that $a_n=a_{n+1}$ are the first two consecutive terms. Then this means $a_{n-1}=0$ implying that $a_{n-2}=a_{n-3}$. A contradiction. Now let $N$ be a positive integer such that $a_N$ is the maximum term in the sequence. This means that $a_{N+1} \neq a_{N}+a_{N-1}$ as $a_N > a_{N+1}, a_{N-1}$. So $a_{N+1}= a_{N}-a_{N-1}$, but this forces $a_{N+2}$ to be more than $a_N$, contradiction. Implying that the sequence is unbounded.

Subjective Rating (MOHs)

$ $

Attachments:

This problem I would say lies in a gray area between 5-10 MOHS as it is very easy to fakesolve (i.e, proving a subsequence is increasing but not showing divergence, assuming a maximum term.) Anyways, here is a solution that hasn't been posted yet I believe. The answer is no, the sequence cannot be bounded. FTSOC, assume it can. Clearly $a_n = a_{n - 1} \pm a_{n - 2}$ for all $n \ge 2$ so define: n is additive if $a_n = a_{n - 1} + a_{n - 2}$ n is subtractive if $a_n = a_{n - 1} - a_{n - 2}$ It is easy to show that all terms must be positive. Moreover, we must have an infinite number of subtractive integers as otherwise, the sequence eventually assumes a Fibonacci recurrence which diverges. Lemma 1: For every additive $n$, the smallest $g > n$ that is subtractive satisfies $a_g \ge a_{n - 2}$. Proof. Since $a_{n - 2}, a_{n - 1}, \dots, a_{g - 3}$ has a Fibonacci recurrence it is increasing, then \[a_g = a_{g - 1} - a_{g - 2} = (a_{g - 2} + a_{g - 3}) - a_{g - 2}\ = a_{g - 3} \ge a_{n - 2}. \] Claim 1: For every subtractive $p$, there exists a larger subtractive $q$ where $2a_p < a_q$. Proof. Let $s$ be the minimal subtractive integer after $p$, we consider cases on what $s$ is. For brevity let $a_{p - 2} = x, a_{p - 1} = y$, it is easy to check the case $s = p + 1$ fails. Case 1: $s = p + 2$. The sequence necessarily has \[a_{p - 2}, a_{p - 1}, a_p, a_{p + 1}, a_{p + 2}, a_{p + 3} = x, y, y - x, 2y - x, y, 3y - x \]and applying Lemma 1 and letting $n = p + 3$ and $q = g$ yields $a_q \ge 2y - x > 2(y - x) = 2a_p$ as wanted. Case 2: $s = p + 3$. We use a similar approach, the sequence has \[a_{p - 2}, a_{p - 1}, a_p, a_{p + 1}, a_{p + 2}, a_{p + 3}, a_{p + 4} = x, y, y - x, 2y - x, 3y - 2x, y - x, 4y - 3x \]and applying Lemma 1 again with $n = p + 4, q = g$ yields $a_q \ge 3y - 2x > 2(y - x) = 2a_p$ which works. Case 3: $s \ge p + 4$. So \[a_{p - 2}, a_{p - 1}, a_p, a_{p + 1}, a_{p + 2}, a_{p + 3}, a_{p + 4} = x, y, y - x, 2y - x, 3y - 2x, 5y - 3x, \dots \]now Lemma 1 where $n = p + 4, q = g$ gives $a_q \ge 2y - x > 2(y - x) = 2a_p$. The claim is proven, now recurring it we can extract a subsequence of the original sequence where every proceeding term is more than twice the previous which must diverge. We are done.

Assume that the sequence is bounded, this then forces a maximum. We then show some other number in the sequence is bigger than the maximum. Claim: No two consecutive numbers in the sequence are equal. Proof: Assume there exists a smallest $i$ with $a_{i} = a_{i + 1}$. This then forces $a_{i - 1} = 0, a_{i - 2} = a_i, a_{i -3} = a_{i - 2}$, so if $i > 3$ we get a contradiction. Otherwise, if $i = 3$ this forces $a_2 = 0$, contradiction, if $i = 2$ this forces $a_1 = 0$, contradiction, if $i = 1$ this violates the problem conditions. Now take the maximum $m = a_j$, then take $a_{j + 1}$. If it is greater than $m$ we are done, if it is equal to done it violates the claim, contradiction, if it is less than $m$ it forces $a_{j + 2} = m + a_{j + 1}$, done ($a_{j + 2} > m$ since $a_{j + 1} \neq 0$ since $a_{j + 2} = a_{j+ 3}$ by the claim), done.

ezpotd wrote: Assume that the sequence is bounded, this then forces a maximum. We then show some other number in the sequence is bigger than the maximum. --- Now take the maximum $m = a_j$, then take $a_{j + 1}$. If it is greater than $m$ we are done, if it is equal to done it violates the claim, contradiction, if it is less than $m$ it forces $a_{j + 2} = m + a_{j + 1}$, done ($a_{j + 2} > m$ since $a_{j + 1} \neq 0$ since $a_{j + 2} = a_{j+ 3}$ by the claim), done. There is an issue. The sequence may not have a maximum term (it's infinite). So, it's not so trivial. But, it can be modified as in #46, and you can take $\limsup a_n$ and get a contradiction.

oops. quick and easy fix: Assume the sequence is bounded, then the sequence does have a limit supremum $A$. Call a number good if it is at least $0.99A$. Some good number must exist, otherwise the limit supremum would be less than $0.99A$. We force a contradiction Consider a good number $a_i$ that is followed by a smaller number $a_{i + 1}$. Then we must have $a_{i + 2} = a_{i + 1} + a_{i}$. If $a_{i + 3} = a_{i + 2} - a_{i + 1} = a_{i}$, we have two consecutive good numbers that are decreasing, this forces $a_{i + 4} = a_{i + 3} + a_{i + 2} > A$. If $a_{i + 3} = a_{i + 2} + a_{i + 1}$, either this is greater than $A$ and we are done or we have $a_{i + 3} > a_{i + 2}$. If $a_{i + 4} = a_{i + 3} + a_{i + 2}$ the sum is greater than $A$ and we are instantly done, if $a_{i + 4} = a_{i + 3} -a_{i + 2} = a_{i + 1}$, we have then proved that $a_{i + 3} = a_{i} + 2a_{i + 1}$, so $a_{i + 3n} = a_{i} + 2n $, obviously contradiction since it would imply $a$ unbounded. If no good number is ever followed by a smaller number, at some point all the remaining numbers in the sequence are good, implying that the difference between them is at most $0.01A$, which obviously fails. i just realized how horrible this writeup is but im too lazy.