12
$\begingroup$

Does there exist a strictly increasing sequence $\{a_n\}_{n\in N}$ of natural numbers such that the following two requirements hold:

1, For all $n\in N$, there is NO subset $M$ of $\{0,\cdots ,n-1\}$ such that $a_n=\Sigma\{a_m\ |\ m\in M\}$.

2, $\{a_n\}_{n\in N}$ is $o(2^n)$, i.e. $\lim_{n\to\infty}\frac{a_n}{2^n}=0$.

$\endgroup$
  • 1
    $\begingroup$ For the stronger property of all subsets having different sums, there is a set whose maximum element is less than $(0.22002)2^n$. See combinatorics.org/ojs/index.php/eljc/article/view/v5i1r3 $\endgroup$ – Tony Huynh Aug 31 '16 at 6:50
  • 1
    $\begingroup$ @Tony: for increasing values of $n$ the sets in the above result may be completely different and not necessarily supersets of previous sets, right? If true, then the above result would not be useful for constructing a sequence . $\endgroup$ – Pushpendre Aug 31 '16 at 9:12
  • $\begingroup$ @Pushpendre Correct. It is just a related result that I was aware of. $\endgroup$ – Tony Huynh Aug 31 '16 at 13:05
17
$\begingroup$

Such sequences are called sum free sequences. In the paper "On a question about sum-free sequences", Deshouillers, Erdős and Melfi construct a sequence where $a_n$ is $o(n^{3+\epsilon})$. Luczak and Schoen, later improved this to a construction of a sum free sequence with $a_n=o(n^{2+\epsilon})$, and show that the exponent $2$ is minimal.


I should mention that the construction, referenced above is related to finding suitable perturbations starting from the set of cubes of integers. Of course for the purposes of the particular question in the OP, one can be more explicit at the cost of not being optimal. For example we can define a sequence $\{a_n\}$ as $$a_1=2 \, ,\quad a_{2n}=a_{2n-1}+1\, , \quad a_{2n+1}=1+\sum_{i=1}^{2n}a_i$$ which is obviously a sum free sequence and grows as $\sim (\sqrt{3})^n$.

$\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.