[Math] A conjecture about Fibonacci numbers

Question

Let $\{F_n\}_{n=1}^\infty $ be the Fibonacci sequence (defined by
$ F_n=F_{n-1}+F_{n-2}$ with $F_1=F_2=1$).

Is it true that for every integer number $N$ there exist positive integers
$n,m,k,l$ such that $N=F_n+F_m-F_k-F_l$ ?

Answer 1

Short answer: No, because the Fibonacci sequence grows exponentially.

Longer answer: First suppose $\{n,m\} \cap \{k,\ell\} \neq \emptyset$, say $n=l$. Then $N = F_m - F_k$. This implies that $N = F_m - F_k \geq F_m - F_{m-1} = F_{m-2}$. It follows that $m = O(\log(N))$ because the Fibonacci sequence is exponential. Similarly we have $k = O(\log(N))$. It follows that for large $N$ we can choose $m$ and $k$ in at most $O(\log(N)^2)$ ways.

Now suppose $\{n,m\}$ and $\{k,\ell\}$ are disjoint. Then we similarly find that we can choose $n$, $m$, $k$, $\ell$ in at most $O(\log(N)^4)$ ways.

Consequently, to write the numbers $1$, $2$, ..., $N$ in the desired form, there are at most $O(\log(N)^2 + \log(N)^4)$ possible choices for $n$, $m$, $k$, $\ell$. However this becomes strictly smaller than $N$ for large $N$.