# The least number of numbers the differences among which include Fibonacci numbers $F_2, F_3,\cdots, F_n$

The Fibonacci numbers $$F_0,F_1,F_2,\ldots$$ are defined inductively by $$F_0=0$$, $$F_1=1$$, and $$F_{n+1} = F_n + F_{n−1}$$ for $$n\ge1$$. Given an integer $$n\ge2$$, determine the smallest size of a set $$S$$ of integers such that for every $$k=2,3,\ldots,n$$ there exists some $$x,y\in S$$ such that $$x−y=F_k$$.

For each value of $$k$$ there must be two integers $$x$$ and $$y$$ such that $$x-y=F_k$$, and since the condition is required for all integers $$2,3,\ldots,n$$ so there must be at least $$n-1$$ pairs of integers $$(x,y)$$ in $$S$$ ($$F_k$$ is strictly increasing when $$k\ge2$$). If $$S$$ has $$m$$ elements, there are $$\frac{m(m-1)}{2}$$ pairs of integers $$(x,y)$$, so $$\frac{m(m-1)}{2}\ge{n-1}\Rightarrow m(m-1)\ge2n-2$$.

If $$n=2$$, $$S$$ must have at least $$2$$ elements which differ by $$1$$.

If $$n=3$$, $$S$$ must have at least $$3$$ elements, and could be $$\{0,1,3\}$$, which is also a set that works for $$n=4$$.

If $$n=5$$, $$S$$ must have at least $$4$$ elements, and could be $$\{0,1,3,8\}$$ which is also a set that works for $$n=6$$.

If $$n=7$$, $$S$$ must have at least $$5$$ elements, and could be $$\{0,1,3,8,21\}$$, which is also a set that works for $$n=8$$. I don't know if $$n=9$$ can be done with $$5$$ elements.

I don't know where to go from here. Any ideas?

• $n=9$ can't be done with $5$ elements.
– user1034536
Commented Jan 12, 2023 at 14:08

Given $$S$$, $$\newcommand{\d}{\text{diff}}$$let $$\d(S)$$ be the set of the differences between numbers in $$S$$. The question is what is the smallest size of a set $$S$$ such that $$F_{2..n}\subseteq\d(S)$$ where $$F_{2..n}=\{F_2,F_3,\cdots,F_n\}$$.

The answer is $$\lceil\frac{n}2\rceil+1$$. Here is a proof.

## The answer is $$\le\lceil\frac{n}2\rceil+1$$

Consider a set of $$\lceil\frac{n}2\rceil+1$$ elements $$M_n =\{F_0, F_2,F_4,\cdots,F_{2\lceil\frac{n}2\rceil}\}.$$ Note that $$2\lceil\frac{n}2\rceil$$ is the least even number that is $$\ge n$$. Since for all $$k\ge1$$

• $$F_{2k}=F_{2k}-F_0$$ and
• $$F_{2k+1}=F_{2k+2}-F_{2k}$$,

we see that $$F_{2..n}\subseteq\d(M_n)$$.

## The answer is $$\ge\lceil\frac{n}2\rceil+1$$

The idea is that Fibonacci numbers are so much apart from each other at least one more number has to be included so as to generate every two more Fibonacci numbers as the differences.

Since the cases with $$n<6$$ are easy, assume $$n\ge6$$. Suppose we have $$F_{2..n}\subseteq\d(S)$$ for some set $$S$$. Towards a contradiction, assume $$|S|\le\lceil\frac n2\rceil$$.

There are two cases.

#### when $$n$$ is even

Construct a graph $$G$$ with vertex set $$S$$. For each $$k\in \{2, 4, 6, \cdots, n\}$$, we add one edge $$\{a,b\}$$ to $$G$$ where $$a,b\in S$$, $$|b-a|=F_k$$. In total, we have added $$\frac n2$$ edges to $$G$$. Since $$G$$ has $$|S|\le\frac n2$$ vertices, there is a cycle in $$G$$. Suppose the cycle is $$s_1, s_2, \cdots, s_\ell$$ with $$|s_2-s_1|=F_{d_1},\ |s_3-s_2|= F_{d_2},\ \cdots,\ |s_{\ell}-s_{\ell-1}|= F_{d_{\ell-1}},\ |s_1- s_{\ell}|=F_{d_\ell}$$ where $$s_i\in S$$, $$d_i\in\{2,4,6,\cdots, n\}$$, $$d_i$$'s are pairwise distinct. WLOG, suppose $$d_\ell$$ is the maximum of all $$d_i$$'s and $$s_\ell>s_1$$.

\begin{aligned} F_{d_\ell} &=s_\ell-s_1=(s_2-s_1)+ (s_3-s_2)+\cdots+(s_{\ell}-s_{\ell-1})\\ &\le|s_2-s_1|+ |s_3-s_2|+\cdots+|s_{\ell}-s_{\ell-1}|\\ &=F_{d_1} + F_{d_2} + \cdots + F_{d_{\ell-1}}\\ &\le F_2 + F_4 + \cdots + F_{d_\ell-2}\\ &<1 + F_2 + F_4 + \cdots + F_{d_\ell-2}\\ &=F_{d_\ell-1} \end{aligned} In short, $$F_{d_\ell}, which is absurd.

#### when $$n$$ is odd

This case is very similar to the case when $$n$$ is even although slightly harder.

Since $$1=F_2\in\d(S)$$, there are two numbers in $$S$$ with difference of $$1$$. Let $$x, x+1$$ be such two numbers.

Construct a graph $$G$$ with vertex set $$S\setminus\{x+1\}$$. For each $$k\in \{3, 5, 7, \cdots, n\}$$, we add one edge to $$G$$ in the following way: since $$F_k\in\d(S)$$, there exists $$a,b\in S$$ such that $$|a-b|=F_k$$.

• If $$a,b\notin\{x, x+1\}$$, add edge $$\{a,b\}$$.
• Otherwise exactly one of $$a$$ and $$b$$ is either $$x$$ or $$x+1$$. (Since $$|(x+1)-x|=1, it cannot happen that both $$a$$ and $$b$$ are either $$x$$ or $$x+1$$.) WLOG, suppose $$a$$ is either $$x$$ or $$x+1$$ while $$b$$ is neither $$x$$ nor $$x+1$$. Add edge $$\{x, b\}$$.

In total, we have added $$\frac {n-1}2$$ edges to $$G$$. Since $$G$$ has $$|S|-2+1\le\frac {n+1}2-1=\frac{n-1}2$$ vertices, there is a cycle $$\mathcal C$$ in $$G$$. There are two cases.

• $$\mathcal C$$ does not contain vertex $$x$$.
Let $$\mathcal C$$ be $$s_1, s_2, \cdots, s_\ell$$ with $$|s_2-s_1|=F_{d_1},\ |s_3-s_2|= F_{d_2},\ \cdots,\ |s_{\ell}-s_{\ell-1}|= F_{d_{\ell-1}},\ |s_1- s_{\ell}|=F_{d_\ell}\label{***}\tag{***}$$ where $$s_i\in S$$, $$d_i\in\{3,5,7,\cdots, n\}$$, $$d_i$$'s are pairwise distinct. WLOG, suppose $$d_\ell$$ is the maximum of all $$d_i$$'s and $$s_\ell>s_1$$.

\begin{aligned} F_{d_\ell} &=s_\ell-s_1=(s_2-s_1)+ (s_3-s_2)+\cdots+(s_{\ell}-s_{\ell-1})\\ &\le|s_2-s_1|+ |s_3-s_2|+\cdots+|s_{\ell}-s_{\ell-1}|\\ &=F_{d_1} + F_{d_2} + \cdots + F_{d_{\ell-1}}\\ &\le F_3 + F_5 + \cdots + F_{d_\ell-2}\\ &<2 + F_3 + F_5 + \cdots + F_{d_\ell-2}\\ &=F_{d_\ell-1} \end{aligned} In short, $$F_{d_\ell}, which is absurd.

• $$\mathcal C$$ contains vertex $$x$$.
We can reuse the proof above with minor adjustment. All equalities at $$\eqref{***}$$ are still correct except possibly for two equalities that involve $$x$$. Each one of those two equalities is either still correct or off by $$1$$. Hence, instead of
$$F_{d_\ell}=s_\ell-s_1=(s_2-s_1)+ (s_3-s_2)+\cdots+(s_{\ell}-s_{\ell-1})$$ we have $$F_{d_\ell}\le (s_2-s_1)+ (s_3-s_2)+\cdots+(s_{\ell}-s_{\ell-1})+2$$ We can then proceed similarly to the computation above. We will have $$F_{d_\ell}\le F_{d_\ell-1}$$, which is absurd.

Since it is absurd in all cases, we know it is not true that $$|S|\le\lceil\frac n2\rceil$$.

• Thanks. This question finally got solved.
– user1034536
Commented Jan 20, 2023 at 12:26
• You are welcome. Commented Jan 20, 2023 at 13:39
• @youthdoo By the way, congratulations to your first silver badge! That is a great achievement for a junior in high school. Commented Jan 20, 2023 at 14:05
• Thanks you very much!
– user1034536
Commented Jan 20, 2023 at 15:19