Representations found by the greedy algorithm

[Alec Mihailovs]

From: "Kimberling, Clark" <ck6 at evansville.edu>

> Suppose x=(1+sqrt(5))/2.  The greedy algorithm finds that every positive
> integer N has a representation
>
> N = c0/x + c1/x^2 + c2/x^3 + ...
>
> Can someone prove that c1, c2, c3, ... are all 0 except for finitely
> many 1's?
>
> Examples:
>
> 4 = 6/x + 1/x^3 + 1/x^6
>
> 5 = 8/x + 1/x^6
>
> 6 = 9/x + 1/x^2 + 1/x^6
>
> 22 = 35/x + 1/x^3 + 1/x^5 + 1/x^7 + 1/x^10.

Such a representation is not unique. The existence of it follows from

-------------------------------------------------------------------
Proposition. Every integer N such that 1 - F_{2n-1} \le N \le F_{2n}
with integer n > 0 can be written as

N = sum_{i \in S} F_{2i-1} - sum_{j \in T} F_{2j}                     (*)

where F are Fibonacci numbers, S and T are some sets of positive
integers with max(S) \le n and max(T) < n .
------------------------------------------------------------------

Proof. Induction by n. For n=1 we have 0 \le N \le 1. If N=0, S and T
can be chosen as empty sets. If N=1, we can choose S={1} and empty T.

If the proposition is true for n = k, the proof that it is true for n = k + 
1
has 3 cases - with 1 - F_{2k+1} \ le N \le -F_{2k-1}, with
1 - F_{2k-1} \le N \le F_{2k}, and with F_{2k}+1 \le N \le F_{2k+2}.

In the first case, N + F_{2k}; in the second case N; and in the third case
N - F_{2k+1} satisfy the conditions for n = k, so they can be represented
as (*) with some sets S* and T*. Now, sets S=S*, T=T*\cup {k} in the
first case, S=S*, T=T* in the second case, and S=S*\cup {k+1}, T=T*
in the third case give sum (*) for N.
Q.E.D.
-------------------------------------------------------------------

Now, substituting F_{2n-1} = F_{2n}/x + 1/x^{2n} and

F_{2n} = F_{2n+1}/x - 1/x^{2n+1} in (*) gives the desirable representation

for N.

In the examples in the original letter, 4 = 5 - 1 = F_5 - F_2 ,   5 = F_5  ,
6 = 5 + 1 = F_5 + F_1,  22 = 34 - 8 - 3 - 1 = F_9 - F_6 - F_4 - F_2.

The proof of the proposition gives the algorithm for finding such a 
representation.

For example, for N = 1000, F_{16} = 987 < N < 2584 = F_{18}, so

1000 = F_{17} + (1000 - F_{17}) = F_{17} + (1000 - 1597) = F_{17} -597

-597 = -F_{14} + (F_{14} - 597) = - F_{14} + (377 - 597) = -F_{14} - 220

-220 = -F_{12} + (F_{12} - 220) = - F_{12} + (144 - 220) = - F_{12} - 76

-76 =  -F_{10} + (F_{10} - 76) = - F_{10} + (55 - 76) = - F_{10} - 21

-21 = - F_8, and

1000 = F_{17} - F_{14} - F_{12} - F_{10} - F_8 =

(F_{18} - F_{15} - F_{13} - F_{11} - F_9)/x +
1/x^{18}+1/x^{15}+1/x^{13}+1/x^{11}+1/x^9 =

1618/x +1/x^9 +1/x^{11} +1/x^{13}+ 1/x^{15} + 1/x^{18}

Alec Mihailovs
http://mihailovs.com/Alec