Representation of integers by Fibonacci numbers Denote by $F$ the set of all Fibonacci numbers.
It is our conjecture that:
(a) For every integer $n$ there exist a number $k=2^q$ (for some positive integer $q$) and  numbers $a_1,\cdots,a_k\in F$ such that 
$$
n=a_1+\cdots+a_{\frac{k}{2}}-(a_{\frac{k}{2}+1}+\cdots+a_k).
$$
Now, denote by $k(n)$ the least $k$ obtained from (a). 
(b) The set of all $k(n)$, where $n$ runs over all integers, is unbounded above.
(the second part is very important for me)
 A: Here's a proof of (a).  First we'll prove a little fact:
Claim: Every positive Fibonacci number can be written in the form $a_1+\cdots+a_{\frac{k}{2}}-(a_{\frac{k}{2}+1}+\cdots+a_k)$ for every $k\ge 2$ that is a power of $2.$
You can prove this by induction on $k,$ as follows:
$\bullet\;$ For $k=2,$ $F_n=F_{n+2}-F_{n+1}.$
$\bullet\;$ If $F_n=a_1+\cdots+a_{\frac{k}{2}}-(a_{\frac{k}{2}+1}+\cdots+a_k),$ then write each of the $a_j$ as a difference of two Fibonacci numbers (each $a_j,$ being a Fibonacci number itself, is the difference of the next two Fibonacci numbers).  That expresses $F_n$ as a formula of the same form but with twice as many terms, as desired, proving the claim.
Here's a more detailed description of the induction step above.  We're assuming that $F_n=a_1+\cdots+a_{\frac{k}{2}}-(a_{\frac{k}{2}+1}+\cdots+a_k),$ where each $a_k$ is some Fibonacci number; say $a_k$ is the $s_k^{\,\text{th}}$ Fibonacci number, so that $a_k=F_{s_k}.$ Then
\begin{align}
F_n&=\sum_{j=1}^{k/2}a_j -\sum_{j=k/2 + 1}^{k}a_j
\\&=\sum_{j=1}^{k/2}F_{s_j} -\sum_{j=k/2 + 1}^{k}F_{s_j}
\\&=\sum_{j=1}^{k/2}(F_{s_j+2}-F_{s_j+1}) -\sum_{j=k/2 + 1}^{k}(F_{s_j+2}-F_{s_j+1})
\\&=\sum_{j=1}^{k/2}F_{s_j+2}+\sum_{j=k/2 + 1}^{k}F_{s_j+1}-\big(\sum_{j=1}^{k/2}F_{s_j+1}+\sum_{j=k/2 + 1}^{k}F_{s_j+2}\big),
\end{align}
which is the sum of $k$ Fibonacci numbers minus the sum of $k$ Fibonacci numbers, as desired.
$$ $$
Now, let $x$ be any positive number; we'll show by induction that we can write $x$ in the required form. If $x$ is a Fibonacci number, we're done. If not, let $F_n$ be the greatest positive Fibonacci number less than $x$ (we know that $x\gt 1,$ so $F_n$ exists).  By induction, we can write $x-F_n$ in the required form for some $k.$ By the claim, we can write $F_n$ in the required form for the same $k,$ and this lets us write $x$ in the desired form for $2k.$
A: For the first claim - it suffices to show this for natural numbers, since for the negative integers you can replace the labels $a_i \mapsto a_{k-i}$. It's clear that $0 = a_1 - a_2$, where $a_1 = a_2$ are any Fibonacci number. 
Suppose this holds up to $m$. Then we can write 
$$ m=a_1+\cdots+a_{\frac{k}{2}}-(a_{\frac{k}{2}+1}+\cdots+a_k). $$
$$ 1=2+1\cdots+1-(1+\dots + 1). $$
so that $m+1$ is the sum of $k$ positive terms follows by $k$ negative terms. 
For the second claim - I don't have a full answer yet. It's trivial to write any Fibonacci number $F_n > 3$ in such a form with $k = 2$, so by the above construction any number $x$ should be expressible with $k = 2^{F_{n-1}}$ terms, where $F_n$ is the greatest Fibonacci number less than $x$. 
And in fact, for any number of the form $x = F_n + b$ where $1 \leq b \leq 8$ we have $k(x) \leq 4$, since each of the number $1$ through $8$ can be written as the difference of two Fibonacci terms. 
The first natural number we can't express as a difference of two Fibonacci terms is $9$. I'm still trying to show that $k(F_n + 9) > 4$ for $n > 8$. 
