The following is from Clark Kimberling’s problems page

# 22.  Lucas and Zeckendorf representations

Let U(n) and V(n) be the number of terms in the Lucas and Zeckendorf representations, respectively, of all the numbers 1,2,,n.  Prove or disprove that V(n)U(n) for all n and that V(n)=U(n) for infinitely many n.

## Accepted solution

It is proved below that both parts of the conjecture are true.  In particular, V(n)=U(n) if n+1 is a Lucas number.

Propositions 1, 2, 3 are well known:

Proposition 1For every integer i

 Li=Fi+1+Fi−1=Fi+2−Fi−2.  ■

Proposition 2For integer i2

 Fi=Fi−2+Fi−3+Fi−4+⋯+F1+1.  ■

Proposition 3(Zeckendorf representation of Fi1) For integer i3

 Fi−1=Fi−1+Fi−3+Fi−5+⋯+Fq,

where q=2 or 3 according as i is odd or even.  ■

Proposition 4For every positive integer m,

 U(Lm−1)=mFm−1.

ProofBy induction on m.  The result is easily checked for m=1,2.  Suppose U(Lm1) and U(Lm11) are known.  The Lucas representations of the Lm1 numbers from Lm up to Lm+11 are got by appending Lm to the representations of 0 to Lm11.  Hence

 U(Lm+1−1) =U(Lm−1) (for 0 to Lm−1) +Lm−1+U(Lm−1−1) (for Lm to Lm+1−1)

By inductive hypothesis and Proposition 1,

 U(Lm+1−1) =mFm−1+(Fm+Fm−2)+(m−1)Fm−2 =m(Fm−1+Fm−2)+Fm=(m+1)Fm.  ■

Proposition 5For every positive integer m,

 V(Fm−1)=[(2m−1)Fm−mFm−1]/5.

ProofSame method as for Proposition 4.  ■

Lemma 6For every positive integer m,

 2V(Fm−1)−V(Fm−1−1)=(m−1)Fm−2.

ProofRoutine calculation from Proposition 5.  ■

Theorem 7For every positive integer m,

 V(Lm−1)=U(Lm−1).

ProofBy induction.  The result is easily checked for m=1,2.  The argument is similar to that for Proposition 4.  We need to look at the Zeckendorf representations of numbers between Lm and Lm+11 inclusive.  The range splits into two blocks:

 Block A:  Fm−2 representations with leading term Fm+1 Lm =Fm+1+Fm−1 ⋮ ⋮ Lm+Fm−2−1 =Fm+1+Fm−1+Fm−3+⋯ Block B:  Fm representations with leading term Fm+2 Lm+Fm−2 =Fm+2 ⋮ ⋮ Lm+1−1 =Fm+2+Fm−1+Fm−3+⋯

Hence

 V(Lm+1−1)−V(Lm−1) =Fm−2+V(Fm−1)−V(Fm−1−1) (from Block A) +Fm+V(Fm−1) (from Block B) =Fm−2+Fm+(m−1)Fm−2 (by Lemma 6) =Fm+m(Fm−Fm−1) =(m+1)Fm−mFm−1.

So by induction V(Lm1)=mFm1, and the result follows from Proposition 4.  ■

For integer n0, denote the number of terms in the Zeckendorf representation of n by z(n).  As usual, the empty sum is considered to be zero, so that z(0)=0

Lemma 8Let k be a non-negative integer.  For 0iFk+21 we have

 z(Fk+4+i)−z(Fk+i)=0 or 1.

ProofThe result is easily checked for k<5.  The rest of the proof assumes k5.  In the following table, the LH column shows the Zeckendorf representations of Fk+4 to Fk+4+Fk+21.  Replacing Fk+4 by Fk, we obtain the sums in the RH column, which are (not necessarily Zeckendorf) representations of Fk to Fk+2+Fk1.  We need to convert the RH sums to Zeckendorf representations and compare their lengths with those on the left.

 Block A Fk+4 Fk Fk+4+1 Fk+1 ⋮ ⋮ Fk+4+Fk−2+Fk−4+⋯ Fk+Fk−2+Fk−4+⋯ Block B Fk+4+Fk−1 Fk+Fk−1 ⋮ ⋮ Fk+4+Fk−1+Fk−3+⋯ Fk+Fk−1+Fk−3+⋯ Block C Fk+4+Fk Fk+Fk ⋮ ⋮ Fk+4+Fk+Fk−2+⋯ Fk+Fk+Fk−2+⋯ Block D Fk+4+Fk+1 Fk+Fk+1 ⋮ ⋮ Fk+4+Fk+1+Fk−1+⋯ Fk+Fk+1+Fk−1+⋯

In Block A, the RH sums are already Zeckendorf representations; hence the lengths are equal.  In Block B (resp. D), the RH sums become Zeckendorf representations on replacing Fk+Fk1 by Fk+1 (resp. Fk+Fk+1 by Fk+2); hence the Zeckendorf lengths on the right are 1 less than on the left.

This leaves the trickier case of Block C, consisting of Fk1 sums each containing Fk twice.  In the following example (k=8), the sums on the LHS are copied from the RHS of Block C in the previous table, and the RHS shows their Zeckendorf representations.

 Block 0 21 + 21 = 34 + 8 equal lengths 21 + 21 + 1 = 34 + 8 + 1 „ 21 + 21 + 2 = 34 + 8 + 2 „ 21 + 21 + 3 = 34 + 8 + 3 „ 21 + 21 + 3 + 1 = 34 + 8 + 3 + 1 „ Block 1 21 + 21 + 5 = 34 + 13 RHS 1 term fewer 21 + 21 + 5 + 1 = 34 + 13 + 1 „ 21 + 21 + 5 + 2 = 34 + 13 + 2 „ Block 2 21 + 21 + 8 = 34 + 13 + 3 equal lengths 21 + 21 + 8 + 1 = 34 + 13 + 3 + 1 „ Block 3 21 + 21 + 8 + 2 = 34 + 13 + 5 RHS 1 term fewer Block 4 21 + 21 + 8 + 3 = 34 + 13 + 5 + 1 equal lengths Block 5 21 + 21 + 8 + 3 + 1 = 34 + 13 + 5 + 2 RHS 1 term fewer

Block C subdivides into k2 blocks whose lengths are successively Fk3, Fk4, …, F1 and 1 (cf. Proposition 2).  Number the blocks 0,1,2,.  In the even-numbered blocks the Zeckendorf representation on the RHS has the same number of terms as the representation on the LHS; in the odd-numbered blocks, 1 term fewer.  The proof will be completed by generalizing this example.

Note that the sums on the LHS of the last table are Zeckendorf representations, except for the repeated Fk at the start.

Start with an even b (initially b=0) and suppose the first line in block b is

 Fk+Fk+⋯+Fk−b=Fk+1+Fk−1+⋯+Fk+1−b+Fk−2−b

(If b=0 the LHS is just Fk+Fk.) The number of terms on each side is (b+4)/2.  On each side we can append the Zeckendorf representations of 0,,Fk3b1.  This gives a block of length Fk3b.  We cannot simply append the next term Fk3b, because on the RHS this fails to give a Zeckendorf representation.  Instead, the terms Fk2b, Fk3b on the RHS combine into a term Fk1b, and we start a new block with

 Fk+Fk+⋯+Fk−b+Fk−3−b=Fk+1+Fk−1+⋯+Fk+1−b+Fk−1−b

or on redefining b as the previous b+1,

 Fk+Fk+⋯+Fk+1−b+Fk−2−b=Fk+1+Fk−1+⋯+Fk+2−b+Fk−b

We have now started an odd-numbered block.  The number of terms on the LHS is (b+5)/2, on the RHS (b+3)/2, i.e.  1 fewer.  Again we can append to each side Zeckendorf representations 0,,Fk3b1.  The next term Fk3b now requires a modification on the LHS, and we start a new block with

 Fk+Fk+⋯+Fk+1−b+Fk−1−b=Fk+1+Fk−1+⋯+Fk−b+Fk−3−b

or on redefining b as the previous b+1,

 Fk+Fk+⋯+Fk+2−b+Fk−b=Fk+1+Fk−1+⋯+Fk+1−b+Fk−2−b

We are now back with an even-numbered block and the process is repeated.  When blocks 0,,k5 have been done, the number of lines completed is

 Fk−3+Fk−2+⋯+F2=Fk−1−2 (Proposition 2)

so as we move into block k4 there are 2 lines left to do.

If k is even, block k4 begins

 Fk+Fk+⋯+F6+F4=Fk+1+Fk−1+⋯+F5+F2.

There are k/2 terms on each side.  Adding 1 to each side changes F4 to F4+F2 on the LHS and F2 to F3 on the RHS.  This creates the final block k3, in which the RHS has 1 fewer term than the LHS.

If k is odd, block k4 begins

 Fk+Fk+⋯+F5+F2=Fk+1+Fk−1+⋯+F6+F4.

There are (k+1)/2 terms the LHS and (k1)/2 terms on the RHS.  Adding 1 to each side changes F2 to F3 on the LHS and F4 to F4+F2 on the RHS.  This creates the final block k3, in which the RHS and LHS have the same number of terms.  ■

For integer n0 define:

 l(n)= number of terms in the Lucas representation of n d(n)=z(n)−l(n) S(n)=d(0)+d(1)+⋯+d(n)

Then S(n)=V(n)U(n), and the first part of the conjecture is equivalent to the following theorem.

Theorem 9S(n)0 for all integer n0

ProofWe show by induction on m that S(n)0 for 0n<Lm.  This is easily cheked for small m.  Suppose the result holds for some m and consider n such that Lmn<Lm+1.  Since S(Lm1)=0 (Theorem 7) we have

 S(n)=d(Lm)+d(Lm+1)+⋯+d(n).

Define f(n)=d(n)d(nLm)

Consider first the range Lmn<Fm+2, where Fm+2Lm=Fm+2Fm+1Fm1=Fm2.  Here the Lucas representation of n is that of nLm with 1 extra term Lm.  The Zeckendorf representation of n is that of nLm with 2 extra terms Fm+1+Fm1, because nLm<Fm2 and so its Zeckendorf representation has no terms greater than Fm3.  Hence

 l(n)=l(n−Lm)+1 and z(n)=z(n−Lm)+2,

whence, by subtracting, d(n)=d(nLm)+1, i.e.  f(n)=1

Now consider the range Fm+2n<Lm+1.  Here l(n)=l(nLm)+1 as before.  For the Zeckendorf representation we use Lemma 8 with m=k+2.  This says that

 z(Fm+2+i)−z(Fm−2−1)=0 or 1 for 0≤i

By Proposition 1 this is equivalent to

 z(n)−z(n−Lm)=0 or 1 for Fm+2≤n

Hence in this range f(n)=d(n)d(nLm)=1 or 0

For Lmn<Lm+1 we have

 S(n)−S(n−Lm) =[d(Lm)+d(Lm+1)+⋯+d(n)]−[d(0)+d(1)+⋯+d(n−Lm)] =f(Lm)+f(Lm+1)+⋯+f(n).

The results proved for f show that as n runs from Lm to Lm+11 the RHS is at first positive and increasing, and then decreasing.  Its final value, from the LHS, is S(Lm+11)S(Lm11)=0 (Theorem 7).  Hence for Lmn<Lm+1 we have S(n)S(nLm)0.  Since 0nLm<Lm1 we have S(nLm)0 by inductive hypothesis; hence S(n)0.  ■

Michael Behrend  8 August 2013