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}<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$.
- 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<F_k$, 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}<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$.
