\leq 2\max\{a_{2k-1},a_{2k}\}/3$ and $a_{2k+2} \leq (a_{2k}+a_{2k+1})/3 \leq 5\max\{a_{2k-1},a_{2k}\}/9 < 2\max\{a_{2k-1},a_{2k}\}/3$.

So we can expect that with probability $1/2^n$ there would be a subsequence of length $2n$, where the maximum of the next two terms does not exceed the maximum of the previous two terms by $2/3$. Clearly it cannot go down forever. We need to start with very large numbers to get a long stretch of a division-rich subsequence.

\[thm:poor\] There exist arbitrary long division-poor subsequences.

This proof is more complicated than the previous one, so we will do it together with a proof of a more powerful theorem in next Section \[sec:customized\].

If we index a division-poor subsequence in such a way that division happens on the odd term, then all the even terms form an increasing subsequence: $a_{2k} > a_{2k-2}$.

As every even term is the sum of the previous two terms we get: $a_{2k} = a_{2k-1} + a_{2k-2} > a_{2k-2}$.

That means that both division-rich and division-poor subsequences can not form a cycle. In particular, it means we can have sequences of arbitrary length without entering a cycle.

We showed that there exist 3-free Fibonacci sequences that have long increasing subsequences. Still, we want to present a 