Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)

share|cite|improve this question
Just in case anyone missed out, I've already given one possible answer, the Fibonacci sequence with the initial $0, 1, 1$ removed. – Mach9 Apr 11 '12 at 13:16
The powers of two, $a_k=2^k$ have this property. Actually, for any integer $b>1$, $a_k=b^k$ have this property. – Thomas Andrews Apr 11 '12 at 13:21
D you want this property to be true for all $k$, or do you want it true just for a single value of $k$? – Thomas Andrews Apr 11 '12 at 13:24
@Gerry Myerson: I hadn't noted that so far, sorry. I'll do it from now on. – Mach9 Apr 11 '12 at 14:40
@Mach9 You can still go back and accept answers from old questions, too. – Thomas Andrews Apr 11 '12 at 15:15
up vote 2 down vote accepted

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

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

share|cite|improve this answer
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? – Mach9 Apr 11 '12 at 14:50
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. – Thomas Andrews Apr 11 '12 at 14:53
It's not obvious what your comment is trying to prove, when you ask "Is that not a valid proof?" – Thomas Andrews Apr 11 '12 at 14:55
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)? – Mach9 Apr 11 '12 at 15:43
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) – Mach9 Apr 11 '12 at 15:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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