# 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

## 2 Answers

No. The Mian-Chowla sequence is such a sequence and it begins 1, 2, 4, 8, 13... ; it also grows only polynomially fast, no faster than n3.

-

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

-
Looks like a monotonicity condition is needed to make the question nontrivial. – anon Jul 30 '13 at 4:56
@amitesh Datta: I have edited the question in response to your clever answer. – Hans Jul 30 '13 at 5:05
@anon: I just added the increasing condition. – Hans Jul 30 '13 at 5:06
@Amitesh Datta: any ideas on the modified question? – Hans Jul 30 '13 at 5:25
Hi @Hans, thanks for your comment and sorry for my delayed response. Yes, I do have some ideas on your modified question but I don't have the time right at this moment to respond in detail. However, when I'm next active on Stack Exchange (in a few hours of time?), I'll try to give you a detailed response. – Amitesh Datta Jul 30 '13 at 5:42