Problem of a Fibonacci sequence related to graph theory

Question

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

Solution: The answer is $\left \lceil \frac{n}{2} \right \rceil + 1$, which is achievable by the following construction: [ $\{ F_0, F_2, \dots, F_{2 \cdot \lceil n/2 \rceil} $} ].Now, to prove the bound, construct a graph $G$ with elements of $S$ as its vertices, and for each $1 \le k \le \lceil n/2 \rceil$, connect two pair of unique vertices $(x,y)$ with an edge if $x - y = F_{2k - 1}$, using the fact that $F_1 = F_2$ and the condition of the problem.

Claim. $G$ has no cycle. Proof. Suppose otherwise, that it contains a cycle with elements $(x_1, x_2, \dots, x_{m})$. Consider the largest difference in this cycle (WLOG it is $(x_1,x_m)$ with $|x_1 - x_m| = F_{2i + 1}$.) Therefore, by assumption, since $(x_1, x_2), (x_2, x_3), \dots, (x_{m - 1}, x_m)$ are all an edge, then $|x_{j + 1} - x_j|$ are the elements of $\{ F_1, F_3, \dots, F_{2i - 1} \}$ and are all distinct. However, notice that by Triangle Inequality, \begin{align*} F_{2i + 1} &= |x_{m} - x_1| \\ &\le \sum_{j = 1}^{m - 1} |x_{j + 1} - x_j| \\ &\le F_1 + F_3 + \dots + F_{2i - 1} \\ &= F_{2i} \end{align*}from which this gives us a contradiction.

Can anyone please explain the given approach of the problem .i.e. how can we know what set to assume and how to prove it.Also I am not so familiar with graph theory so any visual graph of smaller case will be very much appreciated. Thank you.

Answer 1

(I'm going for the question behind the question, namely "How to approach this problem". I'm downplaying the graph theoretic interpretation because it's not relevant, though it could help with a representation for those with enough familiarity/comfort.)

• Think of this as a structure avoider and finder problem
  • For now, ignore the specific case of differences $f_i$ are the fibonacci numbers. Think about the more general case of any set of differences (in non-decreasing order).
• Show that if we wanted any $n$ differences $f_i$, then this can clearly be done with a set of at most $n+1$ numbers.
  • For example, by setting $s_0 = 0, s_i = s_{i-1} + f_i$. If we wanted to use a smaller set, then some number will need to be used 3 or more times. (This is the first structure we come across, though it isn't quite the crux.)
  • For example, by setting $s_0 = 0 , s_i = _i$. (This shows why the "need to be used 3 or more times" likely isn't the crux.)
  • Why do we need $n+1$ elements? If we wanted to reduce the total number of elements, then we'd need something like (say) $\pm f_1 \pm f_3 \pm f_4 = 0 $ from reading off the equations. (But we are not yet making such an assumption on the general case.) Without such a "chain", we will need $n+1$ elements. (This is the structure we want to find/avoid).
    • In graph theory notation (which is helpful to express the ideas, but not absolutely necessary), let the vertices be $s_i$, and connect the edges if there is a difference of $f_i$. If there is no chain, then we have a tree, and hence $V \geq E + 1$. More accurately, "number of vertices = number of edges + number of disconnected components". This is the structure that determines the minimal size of the set.
• What's the easiest way of avoiding equations like $\pm f_1 \pm f_3 \pm f_4 = 0 $? Well, if each new difference is much larger than the sum of the previous ones, then this clearly cannot be 0. Intuitively, if we have a lot of small differences, then we cannot form a large difference. (Note that this is a sufficient condition, but not necessary. It may lead us on a wild goose chase, but let's explore it for now.)
  • Specifically, suppose we had the smallest (by number of elements) set with differences $f_1$ to $f_{k-1}$, and $f_k > f_1 + f_2 + \ldots f_{k-1}$, then show that this set doesn't contain the difference $f_k$. (This can be a bit tricky for you to cleanly argue. Think about what happens if we shift a subset of the set by a certain amount. The graph theory idea could help, but isn't needed.)
  • Hence, to get the difference $f_k$, we will need to add another element to the set. This is the "structure finder". It tells us when we need another element.
  • Hence, show that if we wanted the differences of $1, 2, \ldots, 2^n$, then show that we will need exactly $n+1$ numbers. This in a sense is the extremal set of difference, and we can start to reduce the size of set $S$.
• Can we determine when we HAVE to add another element to get the next larger difference?
  • In fact, with the condition $f_k > f_1 + f_2 + \ldots f_{k-1}$, we didn't have to use every smaller difference. We could use a subset of them.
  • For example, if we wanted to get a set of 6 differences where $f_4 > f_1, f_5 > f_1 + f_4 + f_5, f_6 > f_1 + f_4 + f_5$, then show that we need at least 5 numbers to form these differences.
  • More generally, show that if we had $K$ such inequalities, then to get these differences we'd need at least $K+1$ elements.
  • As it turns out, this is exactly the structure that we want. If we can set up a chain of inequalities where the next difference is larger than the sum of the previous differences, then we know that the size of the set has a lower bound.
  • Now, applying this to the case of the Fibonacci numbers, we have $F_3 > F_1, F_5 > F_3 + F_1, F_7 > F_5 + F_3 + F_1, \ldots$. Hence, the result follows.
• It remains to find a set that satisfies these conditions, which OP has done.