Some observations on the Lekkerkerker-Zeckendorf decomposition of integers

In our youth, we learned of a nice arithmetic theorem of Lekkerkerker (more popularly known after Zeckendorf; hereinafter L-Z) that relates to the famous Mātrā-meru sequence : 0, 1, 1, 2, 3, 5, 8… defined by the recurrence relationship . The theorem states that all positive integers can be uniquely expressed as a sum of one or more distinct non-consecutive terms of . A proof for this theorem can be visualized through a simple geometric construction (Figure 1).

The graphical L-Z decomposition of integers from 1..12

Pile rectangles whose sides are two successive terms of so as to make a half-square (Figure 1). One can see that every integer can be reached by a horizontal path of such rectangles. This also specifies the algorithm for the L-Z decomposition of an integer . Find the largest term of such that . If then continue the same procedure on the difference till . This gives us the decompositions shown in Figure 1.

One can define sequence that counts the length of the L-Z decomposition of each integer . For example, we see that 12=8+3+1, i.e., it is decomposed into 3 terms. Thus, ; similarly . goes as: 1, 1, 1, 2, 1, 2, 2, 1, 2, 2, 2, 3, 1, 2, 2, 2, 3, 2, 3, 3, 1, 2, 2, 2, 3, 2, 3, 3, 2, 3, 3, 3, 4, 1, 2,

One see that the value jumps by 1 for the first time at certain values of (Figure 2): . Using these we define a new sequence : 1, 4, 12, 33 We can then ask what is its convergent? We found that,

,

where is the Golden ratio .

We can then ask if there is a closed expression for . We derived this to be:

Figure 2

Another class of sequences we explored was , the lengths of the L-Z decompositions of , where and , i.e., the powers of integers. For example, goes thus: 1, 1, 2, 1, 2, 3, 3, 3, 3, 6 . Plots of against show a good fit for a linear growth in the range in which we computed these values (Figure 3; it is computationally intensive), albeit with increasing dispersion as increases. If we take their growth to be linear, we then can ask the question: what would be the slope of these lines? Interestingly, we empirically found the slopes of the lines approximating the L-Z decomposition lengths of to be respectively . Can this be proven or is there an alternative description of the growth of these sequences?

Figure 3