Notes on Fibonacci Partitions

Abstract

Let $f_1=1,f_2=2$ and $f_i=f_{i-1}+f_{i-2}$ for $i>2$ be the sequence of Fibonacci numbers. Let ${\Phi }_h(n)$ be the quantity of partitions of natural number $n$ into $h$ different Fibonacci numbers. In terms of Zeckendorf partition of $n$ I deduce a formula for the function $\Phi (n;t):={\sum }_{h\ge 1}{\Phi }_h(n)t^h$, and use it to analyze the functions $F(n):=\Phi (n;1)$ and $\chi (n):=\Phi (n;-1)$. I obtain the least upper bound for $F(n)$ when $f_i-1\<n\<f_{i+1}-1$. It implies that $F(n)\<\sqrt{n+1}$ for any natural $n$. I prove also that $|χ(n)|\<1$, and $\mathop{\lim}\limits_{N\to\infty}\frac{1}{N} \left(χ^2(1)+χ^2(2)\dptχ^2(N)\right)=0$. For any $k2$, I define a special finite set $\mathbb{G}(k)$ of solutions of the equation $F(n)=k$, all solutions can be easily obtained from $\mathbb{G}(k)$. This construction uses a representation of rational numbers as certain continued fractions and provides with a canonical identification $\coprod_{k\>2}\mathbb{G}(k)=\G_+$, where $\G_+$ is the monoid freely generated by the positive rational numbers $<1$. Let $\Psi (k)$ be the cardinality of $\mathbb{G}(k)$. I prove that, for $i2k$ and $k2$, the interval $[f_i-1,f_{i+1}-1]$ contains exactly $2\Psi (k)$ solutions of the equation $F(n)=k$ and offer a formula for the Dirichlet generating function of the sequence $\Psi (k)$. I formulate conjectures on the set of minimal solutions of the equations $F(n)=k$ as $k$ varies and pose some questions concerning such solutions.

arXiv comment23 pages, 2 figures. This version closely corresponds the version published in "Experimental Mathematics", with minor misprint and rearrangement corrections

Cited by in corpus (1)

• On a Theorem of J. Shallit Concerning Fibonacci Partitions