What is the largest number of elements in a subset of $\{1,2,3, \ldots, N\}$ such that the sum of every pair of distinct elements in it is different? The original question from my textbook was

What is the largest number of elements in a subset of $\{1,2,3, \ldots, 9\}$ such that the sum of every pair of distinct elements in the subset is different?

I got the answer $5$ purely by trying out a few combinations.
I would like to know how to solve it mathematically, and also how we can generalise this up till the $N$th natural number.
 A: $5$ is the largest cardinality. A set of $5$ elements is $\{1,2,3,5,8\}$ (as you already noted it contains Fibonacci numbers).
If we have a subset $S$ with $6$ elements such that the sum of every pair of distinct elements in $S$ is different then the number of such values is $\binom{6}{2}=15$. On the other hand, by summing two different numbers in $\{1,2,3,\dots,9\}$ we obtain $15$ different numbers: $3,4,5,\dots,17$. Since we have $15$ distinct values among $15$, we must have them all.
Therefore  we have $3$, which can be obtained only as $1+2$, and $17$, which can be obtained only as $8+9$. Hence $1,2,8,9\in S$ and we have a contradiction because $1+9=2+8=10$.
A: The generalization is an open problem related to Sidon sequences, also called $B_2$ sequences.
As pointed out by Misha Lavrov it is possible to get subsets with $O(\sqrt{N})$ elements.
See also a similar question in Stack Overflow here where I got the reference to Sidon sequences and where you see e.g. that any $b^0, b^1, ... b^m \le N$ with $b \ge 2$ is a Sidon sequence, but the Fibonacci series seems optimal (only for small values of $N$!).
