# Is Fibonacci sequence the minimum of unique pairwise sum sequence?

Let $(a_n)_{n=1}^\infty$ be a strictly increasing (condition added per earlier answer of Amitesh Datta) sequence of natural numbers where all pairwise element sums are unique. Can anyone prove or disprove whether the Fibonacci sequence $(f_n)_{n=1}^\infty=(1,2,3,5,8,\cdots)$ is the "minimum" of such sequences, i.e., $f_n\le a_n$, for all such sequences $(a_n)$?

-
Do you mean $(1,1,2,3,5,8,\ldots)$ for $(f_n)$? Because otherwise this is such a "smaller" sequence in your ordering. (Unless I misunderstood your description of the sequences under consideration.) – Dan Jul 30 '13 at 4:36
@Dan: pairwise sum uniqueness $\implies$ no repeated elements. – Hans Jul 30 '13 at 4:52

Unfortunately, no. Let $\phi:\mathbb{N}\to \mathbb{N}$ be any bijection that isn't the identity. The sequence $(a_n)_{n=1}^{\infty}$ defined by the rule $a_n=f_{\phi(n)}$ for all natural numbers $n$ has the property that all pairwise element sums are unique. However, it's not true that $f_n\leq a_n$ for all natural numbers $n$.