Set with $k$-subset unique sum

Question

Probably, I should call it a sequence, anyway, is there a sequence/set (Fibonacci is a valid answer for this question (minus the first three Fibonacci numbers including zero), but too big) where any $k$-subset (subset/aggregation of terms within sequence, with $k$ elements) will have a unique sum that can't be achieved by any other k-subset?

This PDF is somewhere along the same lines... Thanks all.

Edit I'm asking for the smallest such series, and it must satisfy (as one commenter asked) for all $k$ (well, if that's not possible, just odd or even $k$ will do)

Answer 1

I'll assume you want your $a_i$ to be positive integers, and that you want the statement true for all $k$.

Let $a_1 < a_2 < ... < a_n ...$ be such a sequence. Then for any $n$, and $k\leq n$, the $k$-subsets of $\{a_1,...,a_n\}$ must be distinct. But the sum of any $k$-subset of this set is at most $ka_n$. So there must be at least $n\choose k$ distinct numbers from $1$ to $ka_n$, and hence ${n\choose k} \leq ka_n$, or $$a_n \geq \frac{1}{k} {n\choose k}$$

Now, if $n=2m$ and $k=m$ then you get:

$$a_{2m} \geq \frac{1}{m} {2m\choose m}$$

The right hand side is approximately $\frac{(m+1)2^{2m}}{m^{5/2}\sqrt{\pi}}$. This can be seen via Catalan numbers, see: http://en.wikipedia.org/wiki/Catalan_number .

That would seem to imply that the Fibonacci sequence does not satisfy your original condition. The Fibonacci sequence grows like $\frac{1}{\sqrt 5}\phi^n$, where $\phi = \frac{1+\sqrt{5}}{2} < 2$.

Indeed, if $26 = 21 + 3 + 2 = 13 + 8 + 5$, so this is not true for the Fibonacci numbers when $k=3$.