Background
In a recent question about Fibonacci numbers, it was claimed that
every integer can be written in the form $\sum_{i=1}^6 \epsilon_i F_{n_i}$ with $\epsilon_i \in \{0,-1,1\}$. The upper limit on the summation isn't a typo: every number is the sum/difference of at most 6 fibonacci's.
I believe this is false, even for larger (but still finite) values of $6$:
First of all, without loss of generality, we may assume that the representations do not repeat any Fibonacci number (i.e., the $n_i$s are distinct) and moreover, do not contain any two consecutive Fibonacci numbers (i.e., $n_i \ne n_j+1$). We may arrive at such a representation by using the following simplifications repeatedly:
- If two consecutive Fibonacci numbers appear with opposite signs, simplify the expansion with the identity $F_n – F_{n-1} = F_{n-2}$.
- If two consecutive Fibonacci numbers appear with the same sign, simplify the expansion with the identity $F_n + F_{n-1} = F_{n+1}$.
- If the same Fibonacci number appears with opposite signs, simply cancel the two terms.
- If the same Fibonacci number appears with the same sign, then use the identity $F_n + F_n = F_{n-2} + F_{n-1} + F_n = F_{n-2} + F_{n+1}$ to replace them with two non-identical Fibonacci numbers.
The first three operations reduce the number of terms in the expansion and thus strictly simplify the expression (in terms of how many terms there are), but the last may need to be used several times before it "simplifies" the expression (for example, in terms of how many repeated terms there are). Nonetheless, this simplification procedure terminates, as it is impossible to get stuck in an infinite loop using the last operation alone. (Proof: we may assume that the $n_i$ are positive. Then all of the operations either reduce the number of terms, or leaves that unchanged and reduces the sum of the $n_i$.)
Now, assume we have such a representation (no identical terms, no consecutive terms) and suppose the largest Fibonacci number appearing is $F_n$. Then the next largest term (in absolute value) that may appear is $F_{n-2}$, the next largest after that $F_{n-4}$, and so on. All in all, the sum of the terms excluding $F_n$ is at most $F_{n-2} + F_{n-4} + \cdots \le F_{n-1}$ (proof by induction: add $F_n$ to both sides). By the triangle inequality, the sum of all the terms must be at least $F_n – F_{n-1} = F_{n-2}$. The point of this calculation is that if you want to represent a number that's less than $F_{n-2}$, you can't use terms that are $F_n$ or greater.
This leads us to our contradiction. Consider the integers between $0$ and $F_{n-2}-1$. How many possible representations are there of numbers in this range? Well, we have six terms all of which are 0 or $\pm F_k$ for $k\lt n$ (from the above discussion), so we have at most $(2n+1)^6$ representations that could possibly fall into the range. (We're over-counting here because it won't matter and this is easier.) However, there are clearly $F_{n-2}$ different integers in the given range. Assume for contradiction that it were always possible to represent numbers as the sum/difference of at most 6 Fibonacci's. Then we would have
$$ (2n+1)^6 \ge F_{n-2}. $$
Finally, because the left side grows polynomially while the right side grows exponentially, a large enough value of $n$ will produce a contradiction.
My questions
-
Is the proof above correct? (If not, and the original claim is correct, can you give me a representation of the number 5473?)Edit: Please see Michael Lugo's answer for a paper which finds the representation with the fewest nonzero digits in this "signed Fibonacci base". Please consider the following the actual question here: -
Assuming the proof is correct, is the original claim true for other non-integer bases? What I mean is the following:
Does there exist a natural number $k$ and a real number $b>1$ such that every integer has a representation as $\sum_{i=1}^k \epsilon_i \lfloor b^{n_i} + \frac12 \rfloor$? That is, does every number have a representation in "base $b$" (because $b$ is probably irrational, we round $b^n$ to the nearest integer) with at most $k$ non-zero "digits", but where the "digits" may be $\pm 1$?
Note that the original claim is an instance of this: $k=6$ and $b=\varphi = \frac{1+\sqrt 5}{2}$.
I don't think my proof works directly because I used special properties of $\varphi$/the Fibonacci numbers. Is it possible to remove this reliance? In particular, the second step of the proof shows that it's not "useful" to have large Fibonacci numbers in the representation of a small number. Is the same true for every base $b$?
Note: if the digits were not allowed be negative, then my proof would go through. The main issue is whether or not $\pm b^n$ for large $n$ can cancel and produce small numbers.
Thanks!
Best Answer
This is an answer to your "actual question" (2), building on some of the ideas in Douglas Zare's answer.
Lemma 1: Suppose that $0 < r < 1$. Let $S=\lbrace \epsilon r^i : \epsilon = \pm 1 \text{ and } i \in \mathbb{Z}_{\ge 0} \rbrace$. Fix $k \ge 1$. Let $S_k$ be the set of sums of the form $s_1+\cdots+s_k$ such that $s_i \in S$ and $|s_1|=1$ and there is no nonempty subset $I \subset \lbrace 1,\ldots,k \rbrace$ with $\sum_{i \in I} s_i = 0$. Then $0$ is not in the closure of $S_k$.
Proof: Use induction on $k$. The base case is trivial: $S_1=\lbrace -1,1\rbrace$. Now suppose $k \ge 2$. If a sequence $(x_i)$ in $S_k$ converges to $0$, then the smallest summand in the sum giving $x_i$ must tend to $0$, since a lower bound on the absolute values of the summands rules out all but finitely many elements of $S_k$, which are all nonzero. Discarding the finitely many $x_i$ for which the smallest summand is $\pm 1$ and removing the smallest summand from each remaining $x_i$ yields a sequence $(y_i)$ in $S_{k-1}$ tending to $0$, contradicting the inductive hypothesis.
Now fix $b>1$ and $k$. Let $T=\lbrace \epsilon \lfloor b^n + 1/2 \rfloor : \epsilon = \pm 1 \text{ and } n \in \mathbb{Z}_{\ge 0} \rbrace$. Let $T_k$ be the set of sums of the form $t_1+\cdots+t_k$ with $t_i \in T$.
Lemma 2: Each $t=t_1+\cdots+t_k \in T_k$ equals $u_1+\cdots+u_\ell+\delta$ for some $\ell \le k$ and some $u_i \in T$ with $u_i = O(t)$ and $\delta = O(1)$.
Proof: Examine the powers of $b$ used in the $t_i$. If any nonempty subsum (with signs) of these powers equals $0$, the corresponding $t_i$ sum to $O(1)$. If $b^n$ is the largest power that remains after removing all such subsums, divide all the remaining $t_i$ by $b^n$, and apply Lemma 1 with $r=1/b$ to see that $|t|/b^n$ is bounded away from $0$, so all these remaining $t_i$, which are $O(b^n)$, are $O(t)$.
Corollary: The number of elements of $T_k$ of absolute value less than $B$ is $O((\log B)^k)$ as $B \to \infty$.
Corollary: $T_k \ne \mathbb{Z}$.