A term of the sequence Let $a_0$ and $a_n$ be different divisors of a natural number $m$, and $a_0, a_1, a_2,\cdots, a_n$ be a sequence of natural numbers such that it satisfies 
$$a_{i+1} = |a_i\pm a_{i-1}|\text{  for  }0 < i < n$$
If $\text{gcd}(a_0,\cdots, a_n) = 1$, show that there is a term of the sequence that is smaller than $\sqrt{m}$.
I suppose this claim is true, by checking some of the sequences for small $m$ manually, but a formal still recedes me. This problem is from Serbia MO. Can somebody help? Thanks.
 A: Let $a_j$ and $a_k$, with $j<k$, be two lowest terms of the sequence, and suppose that $k>j+2$. Without loss of generality, we can also assume that all terms $a_i$ with $j<i<k$ are higher than both $a_j$ and $a_k$.
If we consider $a_{j+2}$, there are two possibilities:
1) $a_{j+2}$ is equal to the difference between the two preceding terms, i.e. $a_{j+2}=a_{j+1}-a_j$. In this case, $a_{j+2}<a_{j+1}$. Also, it is clear that the successive term $a_{j+3}$ has to be equal to the sum  (and not the difference) of the two preceding terms $a_{j+1}$ and $a_{j+2}$. In fact, if it were $a_{j+3}=a_{j+1} -a_{j+2}$, we would obtain  $a_{ j+3}=a_{j+1}-(a_{j+1}-a_j)=a_j$, which contradicts the condition that $a_ j$ and $a_ k$ are two lowest terms. Thus we must have  $a_{j+3}=a_{j+2}+a_{j+1}$.              
2) $a_{j+2}$ is equal to the sum of the two preceding terms, i.e. $a_{j+2}=a_{j+1}+a_j$. In this case, $a_{j+2}>a_{j+1}$. Considerations similar to those above allow to conclude that the successive term $a_{j+3}$ has again to be equal to the sum of the two preceding terms $a_{j+1}$ and $a_{j+2}$ (if $a_{j+3}=a_{j+2}-a_{j+1}$, we would have $a_{ j+3}=(a_{j+1}+a_j)-a_{j+1}=a_j$). Thus, even in this case, we must have  $a_{j+3}=a_{j+2}+a_{j+1}$.               
Let us make an example to better illustrate these two cases: suppose that $a_j=3$ and $a_{j+1}=13$. In the first case, $a_{j+2}=13-3=10$. Then, we have  $a_{j+3}=13+10=23$ (otherwise the difference between 13 and 10 would give 3, equal to $a_j$). On the other hand, in the second case, we have $a_{j+2}=13+3=16$, and then necessarily $a_{j+3}=16+13=29$ (otherwise $16-13=3$ would be equal to $a_j$).
In a similar manner, it can be shown that necessarily $a_{k-3}=a_{k-2}+a_{k-1}$ (otherwise, we would get $a_{k-3}=a_{k}$).  
Now let $a_h$ be the highest term among all those included in the interval between $a_j$ and $a_k$.  According to the considerations above, we must have $j+2<h<k-2$. We then have $a_{h+2}=a_h-a_{h+1}$ and $a_{h+1}=a_h-a_{h-1}$ (otherwise, $a_h$ could not be the highest term). Since the second equation can be written as $a_{h-1}=a_h-a_{h+1}$, we get that $a_{h+2}=a_{h-1}$. In a similar manner, we can show that $a_{h+1}=a_{h-2}$. This means that, considering the set of terms included between $a_{h-2}$ and $a_{h+2}$, they constitute a series of 5 terms of the form $f$, $g$, $f+g$, $f$, $g$. Clearly, substituting this series of five terms with the pair $f$, $g$ does not alter the properties of the whole sequence. Thus, we can  remove the terms $a_h$, $a_{h+1}$ and $a_{h+2}$ obtaining a new whole (shorter) sequence that still satisfies the conditions stated in the problem. Proceeding in this manner, we can arrive at a point where the two lowest terms $a_j$ and $a_k$ are either contiguous or separated by a single term. In this second case, the middle term is given by $a_j+a_k$. However, if now we procede backward to re-insert terms between $a_j$ and $a_k$, we would have to insert either  $a_j$ or $a_k$, which violates the assumption that all terms $a_i$ with $j<i<k$ are higher than both $a_j$ and $a_k$. This shows that, in the initial sequence, necessarily  the two lowest terms $a_j$ and $a_j$ are separated by at most one term. If present, the term in the middle is equal to their sum.
Now let us rename, by simplicity, the terms of this pair/triad as $r$, $r+s$, and $s$. It can be shown that any other term of the sequence can be written as $j_ir+k_is$, where $j_i$ and $k_i$ are positive integers. To show this, let us assume first that terms in the sequence can be calculated only as the sum (and not the difference) of the two preceeding terms.  If $r$ and $s$ are contiguous, moving rightward from this pair, the first term is  $s+r$, the second term is $2s+r$, the third term is $3s+2r$, the fourth term is $5s+3r$, and so on (each coefficient is the sum of the two preceeding ones, so that they follow a Fibonacci pattern). Symmetrically, moving leftward from the $r,s$ pair, the first term is  $r+s$, the second is $2r+s$, the third is $3r+2s$, the fourth is $5r+3s$, and so on. Now let us consider the possibility that terms in the sequence can be calculated as the difference (and not only the sum) of the two preceeding terms. Again moving rightward from the $r,s$ pair, it is clear that calculating any term $a_i$ as $|a_{i-1}-a_{i-2}|$ still yields a term of the form $j_ir+k_is$. In this regard, note that since the coefficients $j_i$ and $k_i$ are all calculated as the absolute values of the difference between consecutive Fibonacci numbers, $j_i$ and $k_i$ must be (positive) Fibonacci numbers as well. Also note that, since $r$ and $s$ are the lowest terms of the whole sequence, the minimal value of $j_i$ and $k_i$ is zero, which occurs when a term reduces to either $r$ or $s$ (for example, consider the following hypothetical sequence that decreases via progressive differences: $2r+s$, $3r+2s$, $r+s$, $s$, $r$... clearly the next term has to be again $r+s$, because the term $|r-s|$ would violate the assumption that $r$ and $s$ are the lowest terms).   
Similar results are obtained in the case that $r$ and $s$ are separated by the middle term $r+s$. In this case, moving rightward from the triad, the first term is  $2s+r$, the second is $3s+r$, the third is $5s+2r$, the fourth is $8s+3r$, and so on (again there is a Fibonacci pattern). Moving leftward from the triad, the first term is  $2r+s$, the second is $3r+s$, the third is $5r+2s$, the fourth is $8r+3s$, and so on. The same considerations reported above show that, even in this case, all terms of the sequence can be written as $j_ir+k_is$, where $j_i$ and $k_i$ are positive integers. 
Also note that, to satisfy the condition $\text{gcd}(a_0,\cdots, a_n) = 1$, $r$ and $s$ have to be coprime.
Because $m$ is a multiple of the first and last terms of the sequence, now we can set $m=t(j_0r+k_0s)=u(j_nr+k_ns)$. Solving for $r$ we get $r=s(uk_n-tk_0)/(tj_0-uj_n)$, which implies that $r$ is a divisor of $|(uk_n-tk_0)|$, and then $r<uk_n$ or $r<tk_0$. In the first case we can write $m=u(j_nr+k_ns)>uk_ns>rs$, whereas in the second case we can write $m=t(j_0r+k_0s)>tk_0s>rs$. In both cases we get $m>rs$, so that we can conclude that $\min(r,s)<\sqrt{m}$.
