# 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)

• Do you consider $0$ a Fibonacci number? Oct 28 '16 at 17:56
• Do the $a_j$ have to be pairwise distinct, or can there be repeats among them? Oct 28 '16 at 17:57
• Thinking about it some more I assume $0$ does not count, or that would make $a$ not too hard. Oct 28 '16 at 17:59
• $F_0=0$ is a Fibonacci number, so you need to exclude it explicitly. Oct 28 '16 at 18:08
• Fibonacci sequence is a complete sequence. Maybe, can be useful for your question. Nov 2 '16 at 8:51

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

• In the induction step, what if one of your $a_j$ are one? Oct 28 '16 at 19:21
• @Nitin $1=2-1.$ Oct 28 '16 at 19:28
• $-1$ isn't a Fibonacci number though? Oct 28 '16 at 19:32
• For example what are you doing about (2+1) - (1+1)? Oct 28 '16 at 19:33
• @Nitin $2$ would be included with the Fibonacci numbers being added, and $1$ would be included with the Fibonacci numbers being subtracted. Oct 28 '16 at 21:04

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