2
$\begingroup$

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)

  • 0
    Just in case anyone missed out, I've already given one possible answer, the Fibonacci sequence with the initial $0, 1, 1$ removed.2012-04-11
  • 1
    The powers of two, $a_k=2^k$ have this property. Actually, for any integer $b>1$, $a_k=b^k$ have this property.2012-04-11
  • 1
    D you want this property to be true for all $k$, or do you want it true just for a single value of $k$?2012-04-11
  • 0
    @Gerry Myerson: I hadn't noted that so far, sorry. I'll do it from now on.2012-04-11
  • 0
    @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?2012-04-11

1 Answers 1

2

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

  • 0
    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?2012-04-11
  • 0
    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.2012-04-11
  • 0
    It's not obvious what your comment is trying to prove, when you ask "Is that not a valid proof?"2012-04-11
  • 0
    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)?2012-04-11
  • 0
    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)2012-04-11
  • 0
    @Mach9 You need to clarify your language. You still haven't stated what you are trying to prove, or, if you have, you haven't clarified the relevance to the problem at hand. Did you see my example in my answer (added later) that showed that $26$ can be written as the sum of $3$ Fibonacci numbers in two ways, $26 = 21+3+2 = 13 + 8 + 5$? So clearly, unless you meant something else, this is not true for the Fibonacci sequence.2012-04-11
  • 0
    $1+(-3)=5+(-7)$ so that doesn't work. You get a similar exponential requirement if you allow negative numbers.2012-04-11
  • 0
    If Catalan numbers are this huge, I'd be better off using the binary sequence. The only thing I don't need like in binary is that any number of powers of $2$ will be distinct from any other number of powers of $2$, right? I wish to know of a sequence such that _no **k** terms' sum is equal to any other **k** term's sum._2012-04-12