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.
