Fibonacci numbers in two sets

Is there a way to split all natural numbers (without zero) into two sets, so that no two elements in the same set add up to a Fibonacci number? I made a c++ program and it worked for the first 100'000 natural numbers. So there has to be a proof for that...

I really love the elementary argument presented in the paper of Erdos, Alladi and Hoggatt, which proves inductively that the Fibonacci numbers, or infact any linear recurrence of the Fibonacci type, provides a partition of the integers which is sum-free with respect to that subset, and in fact the split is unique. What I will do is to present the result and proof of Erdos where I outline key steps and leave the details hidden for interested readers. The argument is elementary and really nice as a read-through.

Result : Let $u_n$ be a sequence given by $u_1 = 1$, $u_2 = b>1$ and $u_{n+2} = u_{n+1} + u_n$, $n >0$. There exist unique subsets $A_1,A_2 \subset \mathbb N$ such that

• $A_1 \cap A_2 = \emptyset$ and $A_1 \cup A_2 = \mathbb N$.
• For $i=1,2$ and $a , b\in A_i$, $i=1,2$, we have $a+b \notin \{u_j\}$.

Erdos' proof is an existential one. Turns out we have explicit descriptions for the Fibonacci sequence, as per the sequences A005652 and A005653 of the OEIS.

Anyway, the proof starts with constructing the $A_i$, and will show by induction that no $u_i$ is the sum of two elements from the same $A_i$.

• For starters, why must each of $u_1,u_3,...$ and $u_2,u_4,...$ be parts of different subsets?

Of course : if $u_1$ is in one of the sets, then $u_2$ can't be in there because $u_1+u_2 = u_3$ will be a contradiction. Then $u_3$ can't be in the same subset as $u_2$ otherwise $u_2 + u_3 = u_4$ is a contradiction, so $u_1$ and $u_3$ are in the same subset. The argument continues.

Now we assume that $b$ is even and $b = 2a$.

• All of $1,2,...,a-1,a$ must lie in the same set (taken as $A_1$ wlog). More precisely, if $c <a$ then $c,c+1$ must lie in the same set. (Hint : Consider which subset $d = b-c$ would go in!)

Which would it go in? We have $d+c = u_2$ and $d+(c+1) = u_2 + 1 = u_3$ so $d$ can't be in the same subset as either $c$ or $c+1$. If $c,c+1$ themselves belonged to different subsets, we'd have nowhere to fit $d$!

• Of course, then $\{a+1,...,2a\} \subset A_2$.

$b = (a-x) + (a+x)$ for any $x<a$ so we can't have $a-x,a+x$ in the same subset.

Ok, now let's look at $b = 2a+1$ odd.

• Use a similar reasoning to above to get that $\{1,...,a-1\}$ belong in the same subset , wlog $A_1$.

• $a \in A_1$. (Hint : study where $a+1$ and $a+2$ can go)

If $a \in A_2$, we must have $a+1 \in A_2$ as $a+a+1 = b$. But now $a+2 + a = b+1$ and $a+2 + a-1 =b$ means $a+2$ can go nowhere!

• Now by a similar argument to earlier, $\{a+1,a+2,...,2a+1\} \subset A_2$.

This sorts out everything until $u_2$ for the odd and even cases. Now for the part after $u_2$, the following is proposed as a construction of the $A_i$. It is inductive in nature.

• Pick an $n > u_2$. If $n$ is one of the $u_i$ we already know where it is. Otherwise, there is a unique $u_m < n < u_{m+1}$. Let $i = n - u_m$. Why is $i < u_{m-1}< n$?

The second is obvious, the first from $u_{m-1} + u_m = u_{m+1} > n$ and subtract $u_m$ from both sides.

Now $i$ has already been assigned, as per the inductive build up. We have two parts to this :

• If $i$ is never half any element of $\{u_i\}$ then put $n$ in the same subset as $i$.

• If $i = \frac{1}{2} u_{k-1}$ for some $k>1$, then $ m> k-1$ (why?) so if $m \neq k$, put $n$ and $i$ in the same subset, else put them in different subsets.

Finally, we need to show that this works! Each positive integer has been put in exactly one subset, so that is not a problem. What we need to look at is the second property.

Assume that $\{1,2,...,n-1\}$ have been sorted into two subsets $A_1$ and $A_2$ in the fashion above such that no two elements of the same subset add up to some $u_i$. We prove that when $n$ is inserted according to our rule then the property remains.

There is a unique $m$ with $u_m \leq n < u_{m+1}$.

• $n = u_m$ is not a problem. (Hint : how can $u_m$ be made to add up to some $u_i$ with only elements smaller than $u_m$?)

There's only $u_m + u_{m-1} =u_{m+1}$ as a possibility, but these already belong in different subsets.

• We then have $u_m < n < u_{m+1}$. Let $a<n$. Then the only possibilities for $a+n$ being some $u_i$, are $a+n= u_{m+1}$ and $a+n = u_{m+2}$.

Of course, $a+n > u_m$ but $a+n < 2n < u_{m+1} + u_{m+2} = u_{m+3}$ so we can get only two values for $a+n$.

We split into the cases $a+n = u_{m+1}$ and $a+n = u_{m+2}$, and want to show that for any $a$ in the same subset as $n$ neither of these will happen. Basically, the point is : for $n$, neither $u_{m+1}-n$ or $u_{m+2} -n$ should be in the same subset as $n$.

Let $a+n = u_{m+1}$ and $i = n-u_m < n$.Then $a+i = u_{m-1}$.

• If $a = i$ then $n$ and $a$ are in different subsets.

Then $a=i = \frac 12 u_{m-1}$ are in the same subset but according to the rules, $n$ and $i$ are in different subsets.

• If $a=i$ then $a,n$ are in different subsets.

Well, in that case $i \neq \frac 12u_{m-1}$ so whatever happens, the rules say that $n$ and $i$ are in the same subset. $a$ and $i$ can't be since $a+i = u_{m-1}$ and they are distinct.

So either way, this case is done.

Let $a+n = u_{m+2}$. Let's use case $1$ : $n$ and $u_{m+1} - n$ belong in different subsets from there.

• $u_{m+1} - n$ and $u_{m} + (u_{m+1}-n)$ belong in the same subset. (Hint : let $I = u_{m+1} - n$ , then $N= u_{m} + (u_{m+1}-n) = u_m + i$ so $N- u_m = I$. Our rules say that $N$ and $I$ belong in the same subset unless something happens, but that doesn't happen actually!)

Yes, $N$ and $I$ can belong in different subsets , but for that to happen we must have $I = \frac 12 u_{m-1}$. But then $u_{m+1} - n = \frac 12 u_{m-1}$ and multiply by two and rearrange to get $2n= u_{m+2} = a+n$ so $a = n$, a problem.

But we just proved that $u_{m+1} - n$ and $u_{m} + (u_{m+1}-n) = u_{m+2}-n$ belong in the same subset. $n$ doesn't belong in the same subset as the first one by case $1$, so it doesn't belong in the same subset as $u_{m+2} - n = a$ either!

Consequently, we are done!

Uniqueness : We prove by induction that this holds. We can skip some numbers, though.

• The base case is made clear in the proof, there's only one way to assign everything up till $u_2$. Also, the $u_i$ themselves are assigned uniquely as well from the proof again.

• For any $n$, let $u_m < n < u_{m+1}$. Then $j = u_{m+1} - n < n$ and $n$ are not in the same subset, so as $j$ is uniquely assigned, $n$ is uniquely assigned as well.

This completes the proof of the result.