## 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).

The 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$

Figure 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?

Figure 3

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