5
$\begingroup$

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)

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

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.