Representations found by the greedy algorithm

[Max A.]

On 12/19/06, Kimberling, Clark <ck6 at evansville.edu> wrote:
>
> 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?

Let y = 1/x = (sqrt(5)-1)/2.

The inequality 2y > 1 implies that each of c1, c2, c3, ... is either 0
or 1. Now we need to prove that the number of 1s is finite (i.e., the
greedy algorithms stops after a finite number of steps).

It can be shown that y^k = (-1)^k * (L(k) - F(k)*sqrt(5)) / 2 where
L() and F() are Lucas and Fibonacci numbers respectively.

We have
N - c0*y = ( (2N+c0) - c0*sqrt(5) ) / 2 = c1*y^2 + c2*y^3 + ...

For z = a + b*sqrt(5) where a, b are rational, let f(z) = a+b.
Then f(y^k) = (-1)^k * F(k-1).
It clear that f(z1+z2) = f(z1) + f(z2) and, hence,
N = f(N - c0*y) = f(c1*y^2) + f(c2*y^3) + ... = c1*F(1) - c2*F(2) +
c3*F(3) - ...

Theorem 1. For any non-negative integer N, there exists a representation
N = c1*F(1) - c2*F(2) + c3*F(3) - ...
with coefficients equal 0 or 1, and a finite number of unit coefficients.
Proof.
Write N in the Fibonacci number system: N = b(1)*F(1) + b(2)*F(2) + ...
If b(k)=0 for all even k then we are done.
Otherwise let k be the smallest even k such that b(k)=1. If k=2 then
we can simply re-define
b(1)=1 and b(2)=0, thus removing unwanted non-zero coefficient.
Suppose that k>2.
Then by the property of the Fibonacci number system (no two
consecutive ones), b(k-1)=b(k+1)=0, and since k is the smallest,
b(k-2)=0.
Then we can find a maximum chain:
b(k) = b(k+2) = ... = b(k+2(m-1)) = 1
b(k-1) = b(k+1) = ... = b(k+2m-1) = 0
b(k-2) = b(k-2m) = 0
corresponding to the sum
F(k) + F(k+2) + ... + F(k+2(m-1)) in the Fibonacci representation of N.
We replace this sum with F(k+2m-1)-F(k)+F(k-2), i.e., re-define
b(k-2)=1, b(k)=-1, b(k+2m-1)=1 and let all other b() in between equal
0.
Note that such replacement does not break the property of the
Fibonacci number system for the coefficients b(t), t>=k+2m-1, and
makes the coefficients b(t), t<=k+2m-1 equal 0 or 1 at odd places, and
0 or -1 at even places. Therefore, after a finite number of such
replacement we eliminate positive coefficients at even places and
obtain the required representation:
N = c1*F(1) - c2*F(2) + c3*F(3) - ...
with each coefficient equal 0 or 1, and a finite number of non-zero
coefficients.
Q.E.D.

Theorem 2. For any non-negative integer N, there exists an unique representation
N = c1*F(1) - c2*F(2) + c3*F(3) - ...
where every coefficient is either 0 or 1 with no adjacent unit coefficients.
Proof.
First we will show that the required representation exists. We start
with the representation from Theorem 1:
N = c1*F(1) - c2*F(2) + c3*F(3) - ...
where every coefficient is either 0 or 1.
We scan values 0=c0,c1,c2,c3,.... If there is a triple of coefficients
0,1,1, replace it with a triple 1,0,0 (except when 0,1,1 is at the
very beginning, in which case it is replaced with 0,0,0). That either
eliminates the adjacent unit coefficient or shifts them to the left
with no new adjacencies created. After a finite number of such
scanning and replacement, all adjacent unit coefficients will be
eliminated, delivering the required representation.
Now we prove uniqueness. Suppose that there is two representations:
N = c1*F(1) - c2*F(2) + c3*F(3) - ...
N = c'1*F(1) - c'2'*F(2) + c'3*F(3) - ...
with 0,1 coefficients with no adjacent unit coefficients.
Let k be the largest index with ck not equal c'k. Without loss of
generality we assume that ck=1 and c'k=0.
We note that c(k-1)=0 and the difference between the representation is
bounded from below by F(k) - F(k-2) - F(k-3) - F(k-4) - ... = 1 and
cannot be equal 0.
Therefore, the representation with no adjacent unit coefficients is unique.
Q.E.D.

Theorem 3. Suppose that
N = c1*F(1) - c2*F(2) + c3*F(3) - ...
where each coefficient ci is either 0 or 1 with no adjacent unit coefficients.
Then these coefficient are exactly those produced by the greedy algorithm:
N = c0*y + c1*y^2 + c2*y^3 + ...
Proof.
Let N be represented according to Theorem 2:
N = c1*F(1) - c2*F(2) + c3*F(3) - ...
Consider a number
z = c1*y^2 + c2*y^3 + ...
for which we have f(z)=N. Therefore, z=N+p*y for some integer p.
It is also clear that
z < y^2 + y^4 + y^6 + ... = y^2/(1-y^2) = y
 From the definition of the greedy algorithm, we have
0 < N - c0*y < y
The number z-(N-c0*y) is an integer multiple of y in the interval (-y,y).
Therefore, z-(N-c0*y)=0 or z=N-c0*y, implying that
N = c0*y + c1*y^2 + c2*y^3 + ...
Q.E.D.

Max