The following is from Clark Kimberling’s problems page. 

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 i≥2

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

Proposition 3(Zeckendorf representation of F_i−1) For integer i≥3

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(L_m−1) and U(L_m−1−1) are known.  The Lucas representations of the L_m−1 numbers from L_m up to L_m+1−1 are got by appending L_m to the representations of 0 to L_m−1−1.  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 L_m and L_m+1−1 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(L_m−1)=mF_m−1, and the result follows from Proposition 4.  ■

For integer n≥0, 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 0≤i≤F_k+2−1 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 k≥5.  In the following table, the LH column shows the Zeckendorf representations of F_k+4 to F_k+4+F_k+2−1.  Replacing F_k+4 by F_k, we obtain the sums in the RH column, which are (not necessarily Zeckendorf) representations of F_k to F_k+2+F_k−1.  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 F_k+F_k−1 by F_k+1 (resp. F_k+F_k+1 by F_k+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 F_k−1 sums each containing F_k 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 k−2 blocks whose lengths are successively F_k−3, F_k−4, …, F₁ 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 F_k 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 F_k+F_k.) The number of terms on each side is (b+4)/2.  On each side we can append the Zeckendorf representations of 0,…,F_k−3−b−1.  This gives a block of length F_k−3−b.  We cannot simply append the next term F_k−3−b, because on the RHS this fails to give a Zeckendorf representation.  Instead, the terms F_k−2−b, F_k−3−b on the RHS combine into a term F_k−1−b, 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,…,F_k−3−b−1.  The next term F_k−3−b 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,…,k−5 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 k−4 there are 2 lines left to do. 

If k is even, block k−4 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 F₄ to F₄+F₂ on the LHS and F₂ to F₃ on the RHS.  This creates the final block k−3, in which the RHS has 1 fewer term than the LHS. 

If k is odd, block k−4 begins

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

There are (k+1)/2 terms the LHS and (k−1)/2 terms on the RHS.  Adding 1 to each side changes F₂ to F₃ on the LHS and F₄ to F₄+F₂ on the RHS.  This creates the final block k−3, in which the RHS and LHS have the same number of terms.  ■

For integer n≥0 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 n≥0. 

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

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

Define f(n)=d(n)−d(n−L_m). 

Consider first the range L_m≤n<F_m+2, where F_m+2−L_m=F_m+2−F_m+1−F_m−1=F_m−2.  Here the Lucas representation of n is that of n−L_m with 1 extra term L_m.  The Zeckendorf representation of n is that of n−L_m with 2 extra terms F_m+1+F_m−1, because n−L_m<F_m−2 and so its Zeckendorf representation has no terms greater than F_m−3.  Hence

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

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

Now consider the range F_m+2≤n<L_m+1.  Here l(n)=l(n−L_m)+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<Fm.

By Proposition 1 this is equivalent to

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

Hence in this range f(n)=d(n)−d(n−L_m)=−1 or 0. 

For L_m≤n<L_m+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 L_m to L_m+1−1 the RHS is at first positive and increasing, and then decreasing.  Its final value, from the LHS, is S(L_m+1−1)−S(L_m−1−1)=0 (Theorem 7).  Hence for L_m≤n<L_m+1 we have S(n)−S(n−L_m)≥0.  Since 0≤n−L_m<L_m−1 we have S(n−L_m)≥0 by inductive hypothesis; hence S(n)≥0.  ■

Michael Behrend  8 August 2013