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
L_{i}=F_{i}_{+1}+F_{i}_{−1}=F_{i}_{+2}−F_{i}_{−2}. ■ 

Proposition 2For integer i≥2
F_{i}=F_{i}_{−2}+F_{i}_{−3}+F_{i}_{−4}+⋯+F_{1}+1. ■ 

Proposition 3(Zeckendorf representation of F_{i}−1) For integer i≥3
F_{i}−1=F_{i}_{−1}+F_{i}_{−3}+F_{i}_{−5}+⋯+F_{q}, 

where q=2 or 3 according as i is odd or even. ■
Proposition 4For every positive integer m,
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(L_{m}_{+1}−1)  =U(L_{m}−1)  (for 0 to L_{m}−1) 
 +L_{m}_{−1}+U(L_{m}_{−1}−1)  (for L_{m} to L_{m}_{+1}−1) 

By inductive hypothesis and Proposition 1,
U(L_{m}_{+1}−1)  =mF_{m}_{−1}+(F_{m}+F_{m}_{−2})+(m−1)F_{m}_{−2} 
 =m(F_{m}_{−1}+F_{m}_{−2})+F_{m}=(m+1)F_{m}. ■ 

Proposition 5For every positive integer m,
V(F_{m}−1)=[(2m−1)F_{m}−mF_{m}_{−1}]/5. 

ProofSame method as for Proposition 4. ■
Lemma 6For every positive integer m,
2V(F_{m}−1)−V(F_{m}_{−1}−1)=(m−1)F_{m}_{−2}. 

ProofRoutine calculation from Proposition 5. ■
Theorem 7For every positive integer m,
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: F_{m}_{−2} representations with leading term F_{m}_{+1} 
L_{m} 
=F_{m}_{+1}+F_{m}_{−1} 
⋮  ⋮ 
L_{m}+F_{m}_{−2}−1 
=F_{m}_{+1}+F_{m}_{−1}+F_{m}_{−3}+⋯ 
Block B: F_{m} representations with leading term F_{m}_{+2} 
L_{m}+F_{m}_{−2} 
=F_{m}_{+2} 
⋮  ⋮ 
L_{m}_{+1}−1 
=F_{m}_{+2}+F_{m}_{−1}+F_{m}_{−3}+⋯ 
Hence
V(L_{m}_{+1}−1)−V(L_{m}−1)  =F_{m}_{−2}+V(F_{m}−1)−V(F_{m}_{−1}−1) (from Block A) 
 +F_{m}+V(F_{m}−1) (from Block B) 
 =F_{m}_{−2}+F_{m}+(m−1)F_{m}_{−2} (by Lemma 6) 
 =F_{m}+m(F_{m}−F_{m}_{−1}) 
 =(m+1)F_{m}−mF_{m}_{−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 nonnegative integer.
For 0≤i≤F_{k}_{+2}−1 we have
z(F_{k}_{+4}+i)−z(F_{k}+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 
F_{k}_{+4} 
F_{k} 

F_{k}_{+4}+1 
F_{k}+1 

⋮  ⋮ 

F_{k}_{+4}+F_{k}_{−2}+F_{k}_{−4}+⋯ 
F_{k}+F_{k}_{−2}+F_{k}_{−4}+⋯ 
Block B 
F_{k}_{+4}+F_{k}_{−1} 
F_{k}+F_{k}_{−1} 

⋮  ⋮ 

F_{k}_{+4}+F_{k}_{−1}+F_{k}_{−3}+⋯ 
F_{k}+F_{k}_{−1}+F_{k}_{−3}+⋯ 
Block C 
F_{k}_{+4}+F_{k} 
F_{k}+F_{k} 

⋮  ⋮ 

F_{k}_{+4}+F_{k}+F_{k}_{−2}+⋯ 
F_{k}+F_{k}+F_{k}_{−2}+⋯ 
Block D 
F_{k}_{+4}+F_{k}_{+1} 
F_{k}+F_{k}_{+1} 

⋮  ⋮ 

F_{k}_{+4}+F_{k}_{+1}+F_{k}_{−1}+⋯ 
F_{k}+F_{k}_{+1}+F_{k}_{−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_{1} and 1
(cf. Proposition 2). Number the blocks 0,1,2,….
In the evennumbered blocks the Zeckendorf representation on the RHS
has the same number of terms as the representation on the LHS; in the oddnumbered 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
F_{k}+F_{k}+⋯+F_{k}_{−b}=F_{k}_{+1}+F_{k}_{−1}+⋯+F_{k}_{+1−b}+F_{k}_{−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
F_{k}+F_{k}+⋯+F_{k}_{−b}+F_{k}_{−3−b}=F_{k}_{+1}+F_{k}_{−1}+⋯+F_{k}_{+1−b}+F_{k}_{−1−b} 

or on redefining b as the previous b+1,
F_{k}+F_{k}+⋯+F_{k}_{+1−b}+F_{k}_{−2−b}=F_{k}_{+1}+F_{k}_{−1}+⋯+F_{k}_{+2−b}+F_{k}_{−b} 

We have now started an oddnumbered 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
F_{k}+F_{k}+⋯+F_{k}_{+1−b}+F_{k}_{−1−b}=F_{k}_{+1}+F_{k}_{−1}+⋯+F_{k}_{−b}+F_{k}_{−3−b} 

or on redefining b as the previous b+1,
F_{k}+F_{k}+⋯+F_{k}_{+2−b}+F_{k}_{−b}=F_{k}_{+1}+F_{k}_{−1}+⋯+F_{k}_{+1−b}+F_{k}_{−2−b} 

We are now back with an evennumbered block and the process is repeated.
When blocks 0,…,k−5 have been done, the number of lines completed is
F_{k}_{−3}+F_{k}_{−2}+⋯+F_{2}=F_{k}_{−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
F_{k}+F_{k}+⋯+F_{6}+F_{4}=F_{k}_{+1}+F_{k}_{−1}+⋯+F_{5}+F_{2}. 

There are k/2 terms on each side. Adding 1 to each side changes F_{4} to F_{4}+F_{2} on the LHS
and F_{2} to F_{3} 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
F_{k}+F_{k}+⋯+F_{5}+F_{2}=F_{k}_{+1}+F_{k}_{−1}+⋯+F_{6}+F_{4}. 

There are (k+1)/2 terms the LHS and (k−1)/2 terms on the RHS.
Adding 1 to each side changes F_{2} to F_{3} on the LHS and F_{4} to F_{4}+F_{2} 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(L_{m})+d(L_{m}+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−L_{m})+1 and z(n)=z(n−L_{m})+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(F_{m}_{+2}+i)−z(F_{m}_{−2}−1)=0 or 1 for 0≤i<F_{m}. 

By Proposition 1 this is equivalent to
z(n)−z(n−L_{m})=0 or 1 for F_{m}_{+2}≤n<L_{m}. 

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−L_{m})  =[d(L_{m})+d(L_{m}+1)+⋯+d(n)]−[d(0)+d(1)+⋯+d(n−L_{m})] 
 =f(L_{m})+f(L_{m}+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