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 M: 0, 1, 1, 2, 3, 5, 8… defined by the recurrence relationship f[n+2]=f[n+1]+f[n]. The theorem states that all positive integers can be uniquely expressed as a sum of one or more distinct non-consecutive terms of M. A proof for this theorem can be visualized through a simple geometric construction (Figure 1).

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

Pile rectangles whose sides are two successive terms of M so as to make a n \times n 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 n. Find the largest term m of M such that m \le n. If m < n then continue the same procedure on the difference n-m till n-m=0. This gives us the decompositions shown in Figure 1.

One can define sequence f that counts the length of the L-Z decomposition of each integer n. For example, we see that 12=8+3+1, i.e., it is decomposed into 3 terms. Thus, f[12]=3; similarly f[11]=2= f[10]= f[9]=2. f 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, \cdots

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

\displaystyle n \to \infty, \; \dfrac{f_m[n+1]}{f_m[n]}=\phi^2=\phi+1,

where \phi is the Golden ratio \tfrac{1+\sqrt{5}}{2}.

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

\displaystyle f_m[n] = \left\lfloor 2\sum_{k=0}^{\infty} -1^k \phi^{2n-3k-1} \right\rfloor

LZ_Fig2Figure 2

Another class of sequences we explored was f_k, the lengths of the L-Z decompositions of k^n, where k=2, 3, 4, 5 and n=0, 1, 2 \cdots, i.e., the powers of integers. For example, f_2 goes thus: 1, 1, 2, 1, 2, 3, 3, 3, 3, 6 \cdots. Plots of f_k against n 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 n 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 2^n, 3^n, 4^n, 5^n to be respectively 2^{-4/3}, 2^{-2/3}, 2^{-1/3}, 2^{-1/9}. Can this be proven or is there an alternative description of the growth of these sequences?

LZ_Fig3Figure 3

This entry was posted in Scientific ramblings and tagged , , , , , , , , , . Bookmark the permalink.