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?
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$
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}<F_{d_\ell-1}$, 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$.
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}<F_{d_\ell-1}$, 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$.