A note on the power sums of the number of Fibonacci partitions

A note on the power sums of the number of Fibonacci partitions, Discrete Analysis 2025:2, 13 pp.

This article concerns the number of ways of writing a positive integer $n$ as a sum of strictly increasing Fibonacci numbers. Denote this number by $r_F(n)$. The function $r_F$ is sometimes called the Fibonacci partition function.

The Fibonacci partition function behaves in quite a strange way: it appears in OEIS (the Online Encyclopaedia of Integer Sequences) as sequence A000119, and starts 1, 1, 1, 2, 1, 2, 2, 1, 3, 2, 2, 3, 1, 3, 3, 2, 4, 2, 3, 3. Various authors have found recursive definitions of it and some have even found formulae that are explicit enough to make it possible to calculate it efficiently. In particular, Sam Chow and Tom Slattery found a way to describe $r_F(n)$ in terms of how $n$ decomposes as a sum of non-consecutive Fibonacci numbers (it is an easy exercise to show that there is exactly one way of doing this for each $n$, which is known as the Zeckendorf expansion of $n$).

One simple fact that sheds a little light on the sequence is that if $F_n$ is the $n$th Fibonacci number, then $r_F(F_n-1)=1$. To see this, note that for every $m$, the sum $1+2+3+\dots+F_m$ is equal to $F_{m+1}+F_{m-1}+F_{m-3}+\dots$ (with the exact form of the end of the sum depending on the parity of $m$), which one can show by induction to be strictly less than $F_{m+2}-1$. It follows that in any representation of $F_n-1$, we must use $F_{n-1}$, but since $F_n-1=F_{n-1}+(F_{n-2}-1)$, we then find by induction that the only representation of $F_n-1$ is $F_{n-1}+F_{n-3}+\dots$. (For example, $20=13+5+2$ and $33=21+8+3+1$.)

Paul Stockmeyer also showed that $r_F(n)\leq\sqrt{n+1}$, with equality if and only if $n=F_m^2$ for some positive integer $m$.

When a number-theoretic function on the positive integers is far from smooth, one way to understand it better is to smooth it out by looking at sums or averages. Chow and Slattery used their formula to determine the asymptotic growth rate of the sum $\sum_{n=1}^Nr_F(n)$, showing that the sum is within a constant factor of $N^{\log 2/\log\phi}$. Here, $\phi$ is the golden ratio $(\sqrt 5+1)/2$, the presence of which in the formula is clearly to be expected. More surprisingly, the limit of $N^{-\log 2/\log\phi}\sum_{n=1}^Nr_F(n)$ does not exist.

Chow and Slattery also suggested that it would be interesting to look at higher moments. In a later paper, Chow and Owen Jones made a start on this by determining the rate of growth of $\sum_{n=1}^Nr_F(n)^2$, which turns out to be $N^{\log\lambda_1/\log\phi}$, where $\lambda_1$ is the largest root of the cubic $x^3-2x^2-2x+2$. This result was interesting, because it was a higher power than the obvious lower bound one obtains from the estimate for $\sum_{n=1}^Nr_F(n)$ combined with the Cauchy-Schwarz inequality.

This paper, using quite different methods, tackles all the moments. That is, it determines the growth rate of $\sum_{n=1}^Nr_F(n)^p$ for every positive integer $p$. The basic approach is to build on a construction by Berstel of a deterministic finite automaton that accepts a pair $(x,y)$ of 01 sequences if and only if $y$ starts with a 1 and has no pair of consecutive 1s, and the Fibonacci sums corresponding to $x$ and $y$ are equal (where we let the earlier bits represent larger Fibonacci numbers). Thus, the number of pairs of length up to $n$ accepted by the automaton counts the sum over all pairs $(x,y)$ where $y$ represents the Zeckendorf expansion of some integer less than $F_n$ and $x$ represents some expansion of that integer.

A deterministic finite automaton is a directed graph where each vertex represents a state, one of which is the initial state and some subset of which are designated as accepting states. The edges are labelled with the elements of some alphabet. Then a sequence of letters from that alphabet is fed in and one walks around the graph, starting at the initial state and then for each term in the sequence moving along the edge labelled by that term. Here the sequence consists of pairs $(x_i,y_i)$, which belong to the alphabet $\{0,1\}^2$. A sequence is said to be accepted if at the end of this walk one has landed on an accepting state.

One can obtain asymptotics for the number of accepted sequences by thinking of the directed graph as a transition matrix and finding its largest eigenvalue. If this is $\lambda$, then the number of accepted sequences of length $\ell$ is asymptotic to $\lambda^\ell$.

If one wishes to use a similar method to determine the asymptotics for $\sum_{n=1}^Nr_F(n)^p$, then one is counting sequences $(x^{(1)},\dots,x^{(p)},y)$ such that each $(x^{(j)},y)$ is accepted by Berstel’s automaton. The obvious way to attempt to do this is to take $p$ copies of Berstel’s automaton and run them in parallel with the same $y$ and different $x$s. However, if one does that, then most of the states of the resulting automaton cannot be reached, whereas to apply the method for counting accepted states one needs a graph that is strongly connected (meaning that there is a directed path from each vertex to each other vertex). The main work of this paper is to understand the automaton that results when one throws away the inaccessible states, and to understand it well enough to prove that it is strongly connected and to determine the largest eigenvalue $\lambda_p$ of the transition matrix.

This eigenvalue is not given in closed form. Rather, what emerges from the analysis is an efficient algorithm that can compute, for each $p$, the minimal polynomial of $\lambda_p$, which is a monic polynomial with integer coefficients and degree $p$ if $p$ is odd and $p+1$ if $p$ is even. The paper also includes a proof that $\lambda_p^{1/p}$ converges to $\sqrt\phi$, so the growth rate of $\lambda_p$ is also now understood.