# Comparing sum-free sequences

We will call a strictly increasing sequence of positive integers, $A = a_1, a_2, \ldots \quad \underline {\text {sum-free}}$ if for any four distinct indices $\{i, j. k, l\} \subset \mathbb N,\; a_i+a_j \ne a_k+a_l$. (I.e., sums of distinct pairs are distinct. (Please let me know if there is a short standard term for this property, since "sum-free" has many uses.)
Lemma If $a_1, a_2, \ldots , a_n \text { is sum-free and } n\ge2 \,$ then $a_1, a_2, \ldots , a_n, a_{n-1}+a_n$ is also sum-free.
Proof Let $a_{n+1}= a_{n-1}+a_n$. Then for any distinct indices $\{i, j. k, n+1\} \subset \mathbb N,$ $$a_i+a_j \le a_{n-1}+a_n=a_{n+1}<a_k+a_{n+1}\quad \blacksquare$$ Thus $1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots$ the Fibonacci sequence missing a few initial terms, is sum-free.

A sum-free sequence can also be generated using a greedy algorithm.
If $b_1, b_2, \ldots , b_n \text { is sum-free, and }$ $b_{n+1}\text { is the least integer such that } b_{n+1}>b_n \text { and }$ $b_{n+1} \ne b_i+b_j-b_k \text { for all distinct }i, j, k\le n, \text { then } b_1, b_2, \ldots , b_n, b_{n+1}$ is sum-free by definition.

Thus $1, 2, 3, 5, 8, 13, 21, 30, 39, \ldots$ the Greedy sequence is sum free. See OEIS A011185.

From the exhibited values it looks like Greedy is better than Fibonacci in the sense that Greedy produces larger sum-free subsets of $\{1, 2, \ldots , n\}$ than does Fibonacci.

Question Is $a_h>b_h \text { for all } h\ge n\;$ for some integer $n$?

I think the answer to the above question involves areas in which I am very rusty or were never strong to begin with. In particular, trying to come up with a formula for the Greedy sum-free sequence is a stumper. Generalizations of the above question are also interesting and may in fact be easier to prove, but I would rather not ask multiple questions in one post. The above question arose from thinking about extending my answer to this question.

From what you said, $$b_{n+1}\le{}b_{n-1}+b_n$$ Since $a_{n+1}=a_{n-1}+a_n$, we can subtract the inequality from the equality to get $$a_{n+1}-b_{n+1}\ge{}(a_{n-1}-b_{n-1})+(a_n-b_n)$$ Define $d_n=a_n-b_n$. Since $d_{n+1}\ge{}d_n+d_{n-1}$ and $d_7=0, d_8=4$, we get that $d_n$ is positive for all $n\ge{}8$.