Notes on Fibonacci Partitions

Abstract

Let f₁ = 1, f₂ = 2, and f_i = f_{i − 1} + f_{i − 2} for i > 2 be the sequence of Fibonacci numbers. Let Φ_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 Φ(n; t) ≔ ∑_{h ⩾ 1}Φ_h(n)t^h, and use it to analyze the functions F(n) ≔ Φ(n; 1) and χ(n) ≔ Φ(n; −1). I obtain the least upper bound for F(n) when f_i − 1 ⩽ n ⩽ f_{i + 1} − 1. It implies that for any natural n.

I prove also that |χ(n)| ⩽ 1, and .

For any k ⩾ 2, I define a special finite set of solutions of the equation F(n) = k; all solutions can be easily obtained from . This construction uses a representation of rational numbers as certain continued fractions and provides with a canonical identification , where Γ₊ is the monoid freely generated by the positive rational numbers < 1.

Let Ψ(k) be the cardinality of . I prove that, for i ⩾ 2k and k ⩾ 2, the interval [f_i − 1, f_{i + 1} − 1] contains exactly 2Ψ(k) solutions of the equation F(n) = k and offer a formula for the Dirichlet generating function of the sequence Ψ(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.

KEYWORDS:

• Fibonacci numbers
• partitions
• generating functions

2000 AMS Subject Classification:

• 05A17
• 11P99

Acknowledgments

I am grateful to N. J. A. Sloane who read my 1995 report and included some of the integer sequences from it in [Sloane]. I also would like to thank R. Munafo for a kind letter, where he explained his result, N. Robbins for sending me a draft of his article [Robbins 96], R. P. Stanley who pointed me to the paper [Ardila 04], and A. M. Vershik for useful discussions.

Notes

1 The “conventional” indexing of Fibonacci numbers is different from indexing in this article (see http://en.wikipedia.org/wiki/Fibonacci_number). The formulations of main statements are more neat with our indexing than with “conventional” one (cf. [Robbins 96], where the same problem is encountered).

2 The solutions of the equation F(n) = k for k = 1, 2, 3 were earlier obtained in [Klarner 68].

3 This claim appeared also in [Robbins 96] in the proof of Theorem 9.