Representation of integers by Fibonacci numbers

Question

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)

Answer 1

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.$

Answer 2

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$.