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)

  • $\begingroup$ Just in case anyone missed out, I've already given one possible answer, the Fibonacci sequence with the initial $0, 1, 1$ removed. $\endgroup$ – Mach9 Apr 11 '12 at 13:16
  • 1
    $\begingroup$ The powers of two, $a_k=2^k$ have this property. Actually, for any integer $b>1$, $a_k=b^k$ have this property. $\endgroup$ – Thomas Andrews Apr 11 '12 at 13:21
  • 1
    $\begingroup$ D you want this property to be true for all $k$, or do you want it true just for a single value of $k$? $\endgroup$ – Thomas Andrews Apr 11 '12 at 13:24
  • $\begingroup$ @Gerry Myerson: I hadn't noted that so far, sorry. I'll do it from now on. $\endgroup$ – Mach9 Apr 11 '12 at 14:40
  • $\begingroup$ @Thomas Andrews: Right, but that's pretty large compared to the Fibonacci series, which, as you might note, I had called it too big. I should've mentioned this before, but what is the smallest of such series? $\endgroup$ – Mach9 Apr 11 '12 at 14:42

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

(*) Edit: Of course, the range is even stronger. $k$ distinct integers from $1$ to $a_n$ add up to a value between $\frac{k(k+1)}{2}$ and $ka_n-\frac{k(k-1)}{2}=\frac{k(2a_n-k+1)}{2}$, for a total of $1+\frac{k(2a_n-2k)}{2}$ distinct possible values. So we can slightly improve the above:

$$\binom{n}{k}\leq 1+k(a_n-k)\\ \frac{1}{k}\binom{n}{k}-\frac{1}{k} +k \leq a_n$$

  • $\begingroup$ Thanks for the answer. But, I feel Catalan numbers are pretty huge. I'm looking for the smallest alternative possible. BTW, every number in the Fibonacci series is the sum of its previous two numbers, which violates the statement (in this case) that $k=2$ (and therefore apparently $2$ and above), i.e. any random two numbers in the series cannot be equal to any other two. Is that not a valid proof? $\endgroup$ – Mach9 Apr 11 '12 at 14:50
  • $\begingroup$ Obviously, the Catalan numbers are too big, but my proof shows that $a_{2n}$ has to be bigger than the Catalan numbers $C_n$. You can't do any better, sorry to say. $\endgroup$ – Thomas Andrews Apr 11 '12 at 14:53
  • $\begingroup$ It's not obvious what your comment is trying to prove, when you ask "Is that not a valid proof?" $\endgroup$ – Thomas Andrews Apr 11 '12 at 14:55
  • $\begingroup$ I mean to say, in my understanding, each term is only the sum of its preceding two terms. This is a basic inequality, as here $k=2 (LHS)$ and $k=1 (RHS)$. Consequently, no $k$ terms can sum up to another $k$, doesn't it do better than the Catalan numbers? Are there any counter-examples to this (please state a few)? $\endgroup$ – Mach9 Apr 11 '12 at 15:43
  • $\begingroup$ And, what about alternating negative/positive odd numbers? This, for example, is $1, -3, 5, -7, 9...$, thus the $n$th term is (-1)^{n-1}*(2*n - 1) $\endgroup$ – Mach9 Apr 11 '12 at 15:43

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.