1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Once the greedy sequence starts getting better, it will keep on getting better.
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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.