Date: Tue, 19 Dec 2006 21:31:41 -0800 From: Max Alekseyev Subject: Re: Representations found by the greedy algorithm On 12/19/06, Kimberling, Clark 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