Take the 2-minute tour ×
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.

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

share|improve this question
2  
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
1  
@Dan: pairwise sum uniqueness $\implies$ no repeated elements. –  Hans Jul 30 '13 at 4:52

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer

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

share|improve this answer
    
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

Your Answer

 
discard

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.