Compositions and Fibonacci Identities

Ira M. Gessel and Ji Li Department of Mathematics Brandeis University Waltham, MA 02453 USA

                      gessel@brandeis.edu
                      vieplivee@gmail.com

Abstract We study formulas for Fibonacci numbers as sums over compositions. The Fibonacci number F_{n+1} is the number of compositions of n with parts 1 and 2. Compositions with parts 1 and 2 form a free monoid under concatenation, and our formulas arise from free submonoids of this free monoid.

1. Introduction

A composition of an integer n is a sequence a_{1} a_{2} ⋯ a_{k} of positive integers, called the parts of the composition, with sum n. Richard Stanley’s Enumerative Combinatorics, Vol. 1 [12, Chapter 1, Exercise 35, pp. 109 and 152–153], contains several formulas expressing Fibonacci numbers in terms of sums over compositions:

(i) F_{n+1} is the number of compositions of n into parts equal to 1 or 2.

(ii) F_{n−1} is the number of compositions of n into parts greater than 1.

(iii) F_{n} is the number compositions of n into odd parts.

(iv) F_{2n} = ∑ a_{1}a_{2} ⋯ a_{k}.

(v) F_{2n−2} = ∑(2^{a_{1}−1} − 1) ⋯ (2^{a_{k}−1} − 1)

(vi) F_{2n+1} = ∑ 2^{#{i: a_{i}=1}} Here the Fibonacci numbers are defined by F_{0} = 0, F_{1} = 1, and F_{n} = F_{n−1} + F_{n−2} for n ≥ 2, and the sums in (iv)–(vi) are over all compositions a_{1} a_{2} ⋯ a_{k} of n. We note that these formulas are generally not true for n = 0.

Our goal in this paper is to study identities of this form systematically, and to explain how to find such identities, how to prove them with generating functions, and how to prove them combinatorially.

It is easy to express sums over compositions in terms of generating functions. Let C(n) be the set of compositions of n. Then we will write ∑_{a∈C(n)} for a sum over all compositions a_{1} ⋯ a_{k} of n, with any number of parts. The following result is well known and easily proved. (See, for example, Moser and Whitney [8] and Hoggatt and Lind [6].)

Lemma 1. Let u_{1}, u_{2}, u_{3}, … be any sequence of numbers. Then the sum

∑_{a∈C(n)} u_{a_{1}}u_{a_{2}} ⋯ u_{a_{k}}

is the coefficient of x^{n} in

(1 − ∑_{i=1}^{∞} u_{i}x^{i})^{−1}.

Then formulas (i)–(vi) follow from Lemma 1, the easily verifiable identities

(i′)  \frac{1}{1 − x − x^{2}} = (1 − x − x^{2})^{−1}
(ii′)  1 + \frac{x^{2}}{1 − x − x^{2}} = (1 − x^{2} − x^{3} − x^{4} − ⋯)^{−1}
(iii′)  1 + \frac{x}{1 − x − x^{2}} = (1 − x − x^{3} − x^{5} − ⋯)^{−1}
(iv′)  1 + \frac{x}{1 − 3x + x^{2}} = (1 − x − 2x^{2} − 3x^{3} − ⋯)^{−1}
(v′)  1 + \frac{x^{2}}{1 − 3x + x^{2}} = (1 − x^{2} − 3x^{3} − 7x^{4} − 15x^{5} − ⋯)^{−1}
(vi′)  \frac{1 − x}{1 − 3x + x^{2}} = (1 − 2x − x^{2} − x^{3} − x^{4} − x^{5} − ⋯)^{−1} ,

and the formulas

∑_{n=0}^{∞} F_{n}x^{n} = \frac{x}{1 − x − x^{2}}  (1a)

∑_{n=0}^{∞} F_{2n}x^{n} = \frac{x}{1 − 3x + x^{2}}  (1b)

∑_{n=0}^{∞} F_{2n+1}x^{n} = \frac{1 − x}{1 − 3x + x^{2}} .  (1c)

Formula (1a) follows easily from the Fibonacci recurrence F_{n} = F_{n−1} + F_{n−1}. For (1b) and (1c), we have

∑_{n=0}^{∞} F_{n}x^{n} = \frac{x}{1 − x − x^{2}} · \frac{1 + x − x^{2}}{1 + x − x^{2}}

= \frac{x + x^{2} − x^{3}}{1 − 3x^{2} + x^{4}} = x \frac{1 − x^{2}}{1 − 3x^{2} + x^{4}} + \frac{x^{2}}{1 − 3x^{2} + x^{4}} .  (2)

Then (1b) and (1c) follow by extracting the even odd powers of x from (2).

The proofs we have just sketched (essentially the generating function proofs given by Stanley), though straightforward, do not really explain why these formulas are true, nor how one might find them or other similar formulas. To do this, we study a combinatorial structure that lies behind them.

2. Free monoids

Let A be a set, which we call an alphabet. Let A^{∗} be the set of words (finite sequences) of elements of A. Then with the operation of concatenation, A is a monoid (a semigroup with unit), where the unit is the empty word. We call A^{∗} the free monoid on A. The length l(x) of an element x = a_{1}a_{2} ⋯ a_{k}, where each a_{i} is in A, is k.

More generally, a free monoid M is a monoid isomorphic to a free monoid of the form A^{∗}. So if M is a free monoid, then there exists a subset P of M such that every element of M has a unique factorization as a product of elements of P. We call P the set of primes of M. (It is easy to see that P is unique.)

A weight function on a free monoid M is a function ω : M → ℕ, where ℕ is the set of nonnegative integers, with the properties that ω(m_{1}m_{2}) = ω(m_{1})+ω(m_{2}) for all m_{1}, m_{2} ∈ M and ω(m) = 0 if and only if m is the unit element of M. It is easy to see that a weight function on M is determined by its values on the primes of M.

If L is any submonoid of a free monoid, we call an element p of L irreducible (in L) if p is not the unit element of M and p cannot be expressed as a product of two non-unit elements of L. (Note that the irreducibility of p depends on both p and L.) It is clear that every element of L can be factored as a product of irreducibles, but in general this factorization is not unique. If L is a free monoid, then the factorization is always unique and the irreducible elements are the primes of L.

Let M be a free monoid with a weight function ω. If x is an indeterminate then the map m ↦ x^{ω(m)} is a homomorphism from M to the monoid of powers of x under multiplication, and unique factorization in M gives the well-known identity for formal power series

∑_{m∈M} x^{ω(m)} = (1 − ∑_{p∈P} x^{ω(p)})^{−1},  (3)

where P is the set of primes of M. Equivalently, the number of words in M of weight n is the sum

∑_{a∈C(n)} u_{a_{1}}u_{a_{2}} ⋯ u_{a_{k}},

where u_{i} is the number of primes of M of weight i. We will see that formulas (i)–(vi) can all be interpreted in this way.

We will be especially interested in free monoids that are submonoids of A^{∗} for some alphabet A. For example, the set of words in {a}^{∗} of even length is a free submonoid of {a}^{∗}. The set of words in {a}^{∗} of length not equal to 1 is also a submonoid but it is not free, since a^{5} has two factorizations, a^{5} = a^{2} · a^{3} = a^{3} · a^{2} into words that cannot be further factored. The set of words in {a, b}^{∗} that start with a, together with the empty word, is a free submonoid in which the primes are of the form ab^{i}, for i ∈ ℕ.

Next we discuss some lemmas that are helpful in proving that submonoids of free monoids are free.

Lemma 2. Suppose that M is a submonoid of a free monoid A^{∗} with the property that every nonempty word in M has a unique factorization of the form xy where x is irreducible in M and y ∈ M. Then M is free.

Proof. We prove by induction on n that every word in M of length n has a unique factorization into irreducibles of M. The assertion holds trivially for n = 0. Now suppose that w is a word in M of length n > 0 and that all words in M of length less than n have unique factorizations into irreducibles. Let w = x_{1}x_{2} ⋯ x_{k} be a factorization of w into irreducibles. Since w has a unique factorization of the form w = xy where x is irreducible in M and y ∈ M, we must have x_{1} = x and x_{2} ⋯ x_{k} = y. By the induction hypothesis, y has a unique factorization into irreducibles, so x_{2}, …, x_{k} are uniquely determined.

Let us say that a submonoid M of the free monoid A^{∗} satisfies Schützenberger’s criterion if it has the property that for every p, q, and r in A^{∗}, if p, pq, qr, and r are in M then q is in M. The following useful result is due to Schützenberger [9, Theorem 1.4]; see also Tilson [13].

Lemma 3. Let M be a submonoid of the free monoid A^{∗}. Then M is free if and only if M satisfies Schützenberger’s criterion.

Proof. First, suppose that M satisfies Schützenberger’s criterion. It is enough to show that the hypothesis of Lemma 2 holds. Let w be a nonempty word of M, and suppose that w = xv where x is irreducible in M and v ∈ M. Suppose also that w can also be factored as xy · z where y is nonempty and xy and z are in M. It is enough to show that xy is not irreducible. Since x, yz = v, xy, and z are in M, by Schützenberger’s criterion we have y ∈ M, and this implies that xy is not irreducible.

Next, suppose that M is free, and suppose that p, pq, qr, and r are in M. Let w = pqr. Then w has a unique factorization w = u_{1}u_{2} ⋯ u_{k} into primes of M. The factorizations w = p · qr = pq · r into elements of M imply that for some i ≤ j, we have p = u_{1} ⋯ u_{i}, q = u_{i+1} ⋯ u_{j}, and r = u_{j+1} ⋯ u_{k}, and thus q ∈ M, so Schützenberger’s criterion holds.

Now let u and v be words. We say that u overlaps with v if there exist words x and y such that ux = yv and l(y) < l(u) (and thus l(x) < l(v)). For example, ab overlaps with bc because ab · c = a · bc. We call a word w non-overlapping if it does not overlap with itself. Thus ab is non-overlapping, but aa overlaps with itself.

Let w be a word in the free monoid A^{∗}. Let us denote by A_{w} the set of words in A^{∗} that start with w, together with the empty word. Then A_{w} is a submonoid of A^{∗}. If A = {a} and w = a^{2}, then A_{w} is not free, since A_{w} is the set of words in {a}^{∗} of length not equal to 1. On the other hand, if A = {a, b} and w = ab then A_{w} is easily seen to be free.

It will be conveniently to refer to A_{w} as “the monoid of words in A^{∗} that start with w,” and more generally, whenever we speak of the monoid of words with some property, it will be understood that the empty word is included, even if it does not have the property.

Lemma 4. The submonoid A_{w} of the free monoid A^{∗} is free if and only if w is nonoverlapping.

Proof. We first show that the condition is sufficient. Suppose that w is non-overlapping. We will show that Schützenberger’s criterion holds. Suppose that p, pq, qr, and r are in A_{w} and that r is nonempty. Then since qr and r both start with w, and w is non-overlapping, we must have l(q) ≥ l(w). This implies that since qr starts with w, so does q, so q ∈ A_{w}.

For necessity, we show that if w is overlapping then A_{w} is not free. Suppose that w is overlapping, so there exist words t, u, and v such that t = wu = vw, where v (and thus also u) is shorter than w. We will show that wt has two different factorizations into irreducibles in A_{w}. Any word in A_{w} that is not irreducible must have length at least twice the length of w, so wu and wv are irreducible. Therefore w · wu and wv · w are two different factorizations of wt into irreducibles of A_{w}, so A_{w} is not free.

We can show similarly that if u does not overlap with v then the submonoid of A^{∗} of words that start with u and end with v is free.

3. Fibonacci compositions

Let us define a Fibonacci composition of n to be a composition of n with parts 1 and 2. Thus the set of all Fibonacci compositions is the free monoid {1, 2}^{∗}. Most of our results are consequences of the fact there are F_{n+1} Fibonacci compositions of n. (Many other identities are proved using this interpretation of Fibonacci numbers in Benjamin and Quinn [1].)

Applying (3) to this free monoid with the weight function ω(1) = 1, ω(2) = 2, together with the fact that there are F_{n+1} Fibonacci compositions of n, gives the generating function

∑_{n=0}^{∞} F_{n+1}x^{n} = \frac{1}{1 − x − x^{2}} ,

which is equivalent to (1a). Our proofs of (i)–(vi) and other similar formulas are all based on free submonoids of the free monoid of Fibonacci compositions.

Now let us consider the monoid {1, 2}_{1} of Fibonacci compositions that start with 1 (including the empty Fibonacci composition). By Lemma 4, this monoid is free (though this is easy to see directly), and the primes are the compositions of the form 1 2^{i}, for i ≥ 0. So the generating function for primes in this free monoid is ∑_{i=0}^{∞} x^{2i+1}.

It follows that if s_{n} is the number of Fibonacci compositions of n that start with 1, with s_{0} = 1, then

∑_{n=0}^{∞} s_{n}x^{n} = (1 − ∑_{i=0}^{∞} x^{2i+1})^{−1},  (4)

and the right side of (4) is the generating function for compositions with odd parts. But the number of Fibonacci compositions of n that start with 1 is just the number of Fibonacci compositions of n − 1, so we see that for n > 0, the number of compositions of n with odd parts is equal to the number of Fibonacci compositions of n − 1, which is F_{n}. So (iii) holds. (This result seems to have been first given by Hoggatt [3] and Hoggatt and Lind [5].)

Our approach gives a simple bijective proof of this fact. Suppose that c is a Fibonacci composition of n − 1. Thus 1 c is a Fibonacci composition of n that starts with 1, which can be expressed uniquely as 1 2^{i_{1}} 1 2^{i_{2}} ⋯ 1 2^{i_{k}}. Then the corresponding composition of n with odd parts is 1 + 2i_{1} 1 + 2i_{2} ⋯ 1 + 2i_{k}.

We could apply exactly the same analysis with the roles of 1 and 2 switched, and we would find that the number of Fibonacci compositions of n that start with 2 is equal to the number of compositions of n with all parts greater than 1, and this is (ii).

A similar result applies to compositions with any set of two parts (cf. Sills [10], Zeilberger [14], and Munagi [7, Theorem 1.2]):

Proposition 5. Let p and q be distinct integers. Then for n ≥ p, the number of compositions of n − p with parts p and q is equal to the number of compositions of n with parts of the form p + qi, where i ∈ ℕ.

Proof. First we note that prepending a part p to a composition of n − p with parts p and q gives a composition of n that starts with p. In the free monoid {p, q}_{p}^{∗} of compositions with parts p and q that start with p, the primes are compositions of the form p q^{i}. Thus a bijection from the compositions of n > 0 that start with p to the compositions of n with parts of the form p + qi is given by the map that takes p q^{i_{1}} p q^{i_{2}} ⋯ p q^{i_{k}} to the composition p + qi_{1} p + qi_{2} ⋯ p + qi_{k}.

The generating function identity that corresponds to Proposition 5 is

1 + \frac{x^{p}}{1 − x^{p} − x^{q}} = (1 − \frac{x^{p}}{1 − x^{q}} )^{−1} .

More generally, we can show that for any k ≥ 1,

1 + x^{k} ∑_{n=0}^{∞} F_{n+1}x^{n} = 1 + \frac{x^{k}}{1 − x − x^{2}}

is the generating function for a free monoid.

Proposition 6. Fix an integer k ≥ 2. The monoid M of Fibonacci compositions starting with 2 1^{k−2} is a free monoid in which the primes are of the form 2 1^{k−2} 1^{i} q, where i is a nonnegative integer and q is empty or is a Fibonacci composition that starts with 2 and contains no 2 1^{k−2}.

The generating function for the primes of M is x^{k}/(1 − x − x^{2} + x^{k}), and thus we have a combinatorial interpretation to the identity:

1 + \frac{x^{k}}{1 − x − x^{2}} = (1 − \frac{x^{k}}{1 − x − x^{2} + x^{k}} )^{−1}.  (5)

Proof. By Lemma 4, M is a free monoid, and it is easy to see that the primes of M are as stated in the proposition. Let Q be the monoid of Fibonacci compositions that start with 2 and contain no 2 1^{k−2}. Then Q is a free monoid in which the set of primes consists of compositions 2 1^{i}, with 0 ≤ i ≤ k − 3. Thus the generating function for Q is

(1 − ∑_{j=2}^{k−1} x^{j})^{−1} = \frac{1 − x}{1 − x − x^{2} + x^{k}} ,

and the generating function for the primes of M is

\frac{x^{k}}{1 − x} · \frac{1 − x}{1 − x − x^{2} + x^{k}} = \frac{x^{k}}{1 − x − x^{2} + x^{k}} .

For k = 2, M is the free monoid of compositions that start with 2, and the primes, as we saw before, are of the form 2 1^{i}, for i ≥ 0.

For k = 3, the generating function for the primes of M is

\frac{x^{3}}{1 − x − x^{2} + x^{3}} = \frac{x^{3}}{(1 − x)^{2}(1 + x)} = \frac{x^{3} + x^{4}}{(1 − x^{2})^{2}} = ∑_{n=3}^{∞} ⌊\frac{n − 1}{2}⌋ x^{n}

This gives the formula

F_{n−2} = ∑_{a∈C(n)} ⌊\frac{a_{1} − 1}{2}⌋ ⋯ ⌊\frac{a_{k} − 1}{2}⌋ ,  (6)

for n ≥ 2. (Recall that C(n) is the set of compositions a_{1} … a_{k} of n.) We can explain this formula combinatorially by showing that there are ⌊(n − 1)/2⌋ primes of M of weight n. In this case, the primes are of the form 2 1^{i+1} 2^{j} for i, j ∈ ℕ. If such a word is a composition of n, then i+1+2(j+1) = n so i = n−2j−3, and this is nonnegative for j = 0, 1, …, ⌊n/2⌋−1.

There is a slightly simpler interpretation of (6). Instead of Fibonacci compositions that start with 2 1, we consider Fibonacci compositions that start with 1 and end with 2. These form a free monoid in which the primes are of the form 1^{i} 2^{j}, where i, j ≥ 1, and there are ⌊(n − 1)/2⌋ of them of weight n.

The cases when k = 2, 3, 4, or 5 in (5) are specializations of the identities

1 + \frac{a}{1 − a − b} = (1 − \frac{a}{1 − b})^{−1},  (7)
1 + \frac{ab}{1 − a − b} = (1 − \frac{ab}{(1 − a)(1 − b)})^{−1},  (8)
1 + \frac{a^{2}b}{1 − a − b} = (1 − \frac{a^{2}b}{(1 − a)(1 − b − ab)})^{−1},  (9)

which can also be interpreted in terms of free monoids.

There are other interesting applications of these formulas. Taking a = b = x in (7), shows that the total number of compositions of n, for n > 0, is 2^{n−1}. Taking a = b = x in (8) gives

2^{n−2} = ∑_{a∈C(n)}(a_{1} − 1) ⋯ (a_{k} − 1), n ≥ 2.

Taking a = b = x in (9), and using the fact that

\frac{x^{3}}{(1 − x)(1 − x − x^{2})} = \frac{x}{1 − x − x^{2}} − \frac{x}{1 − x} = ∑_{n=1}^{∞}(F_{n} − 1)x^{n},

gives

2^{n−3} = ∑_{a∈C(n)}(F_{a_{1}} − 1) ⋯ (F_{a_{k}} − 1), n ≥ 3.  (10)

(the nonzero terms come from compositions into parts greater than 2). Formula (10) “explains” why the first three nonzero values of F_{n} − 1 are the first three powers of 2 (i.e., F_{3} − 1 = 1, F_{4} − 1 = 2, F_{5} − 1 = 4), since for 3 ≤ n < 6 there is just one nonzero term in the sum in (10). That F_{n} − 1 = 2^{n−3} for 3 ≤ n < 6 can also be seen from the formula

\frac{x}{1 − x − x^{2}} − \frac{x}{1 − x} = \frac{x^{3}}{1 − 2x + x^{3}} .

Taking a = x, b = x^{m} in (8) gives a generalization of (6):

Proposition 7. Fix m ≥ 1 and define the numbers r_{n} by

∑_{n=0}^{∞} r_{n}x^{n} = \frac{1}{1 − x − x^{m}} .

Then for n ≥ m + 1 we have

r_{n−m−1} = ∑_{a∈C(n)} ⌊\frac{a_{1} − 1}{m}⌋ ⋯ ⌊\frac{a_{k} − 1}{m}⌋ ,

where the only nonzero terms come from compositions in which every part is at least m + 1.

Proof. By (8) with a = x, b = x^{m}, we have

1 + ∑_{n=m+1}^{∞} r_{n−m−1}x^{n} = 1 + \frac{x^{m+1}}{1 − x − x^{m}} = (1 − \frac{x^{m+1}}{(1 − x)(1 − x^{m})})^{−1} .

We have

\frac{x^{m+1}}{(1 − x)(1 − x^{m})} = x^{m+1} \frac{1 + x + ⋯ + x^{m−1}}{(1 − x^{m})^{2}}

= x(x^{m} + x^{m+1} + ⋯ + x^{2m−1})(1 + 2x^{m} + 3x^{2m} + ⋯)

= ∑_{n=1}^{∞} ⌊\frac{n − 1}{m}⌋ x^{n}

and the result follows.

It is not hard to give a combinatorial interpretation to Proposition 7. The number r_{n} counts compositions of n with parts 1 and m, so for n ≥ m+1, r_{n−m−1} is the number of such compositions of n that start with 1 and end with m. These compositions form a free monoid in which the primes are of the form form 1^{i} m^{j}, where i, j ≥ 1, and there are ⌊(n − 1)/m⌋ of them of weight n.

The numbers r_{n} for m = 3, 4, 5, 6, …, 15 are sequences \underline{A000930}, \underline{A003269}, \underline{A003520}, \underline{A005708}–\underline{A005711}, and \underline{A017898}–\underline{A017909}.

4. Multisection

To explain results such as (iv)–(vi) of Section 1, we need to consider Fibonacci compositions of only even or only odd numbers. More generally, given m and i, we may consider Fibonacci compositions of numbers congruent to i modulo m.

The following result, which follows easily from Lemma 3, tells us that the relevant monoids are free.

Lemma 8. Let M be a free monoid with a weight function and let m be a positive integer. Then the submonoid of M consisting of elements of weight divisible by m is free.

We shall apply Lemma 8 to free monoids of Fibonacci words. Let

f_{m,i} = ∑_{n=0}^{∞} F_{mn+i+1}x^{n},

so that the coefficient of x^{n} in f_{m,i} is the number of Fibonacci compositions of mn + i.

It follows from Lemma 8 that the monoid of Fibonacci compositions of multiples of m is free. Let us define a weight function on this monoid by taking the weight of a composition of mn to be n. Then the generating function for this monoid is f_{m,0}.

Now let w be a non-overlapping Fibonacci composition of an integer r = mk − i, where k ≥ 1 and 0 ≤ i < m. Then by Lemmas 4 and 8, the monoid of Fibonacci compositions of multiples of m, starting with w, is a free monoid, and the generating function for this free monoid is 1 + x^{k}f_{m,i}.

In this section, we consider a few cases of these generating functions for arbitrary m, and in sections 5 and 6 we look in more detail at the cases m = 2 and m = 3.

It is not hard to show (e.g., by using the Binet formula for Fibonacci numbers) that

∑_{n=0}^{∞} F_{mn+j}x^{n} = \frac{F_{j} + (−1)^{j}F_{m−j}x}{1 − L_{m}x + (−1)^{m}x^{2}} ,  (11)

where L_{n} is the nth Lucas number (L_{0} = 2 and L_{n} = F_{n−1} + F_{n+1}). See, for example, Hoggatt and Lind [4, equation (4.18)]. We can find simple free monoid interpretations for generating functions for F_{mn+1} and F_{mn−1}.

For F_{mn+1}, we have the following formula, due to Hoggatt [3].

Proposition 9.

f_{m,0} = ∑_{n=0}^{∞} F_{mn+1}x^{n} = \frac{1 − F_{m−1}x}{1 − L_{m}x + (−1)^{m}x^{2}} = (1 − F_{m+1}x − \frac{F_{m}^{2}x^{2}}{1 − F_{m−1}x})^{−1} .  (12)

Proof. The formula is a straightforward computation, using the case j = 1 of (11), the formula L_{m} = F_{m−1} + F_{m+1}, and Cassini’s identity F_{m+1}F_{m−1} − (−1)^{m} = F_{m}^{2}.

We can interpret Proposition 9 combinatorially by describing the primes of the free monoid of Fibonacci compositions of multiples of m. The primes of weight one are the Fibonacci compositions of m, which are counted by F_{m+1}. The primes of weight n > 1 are of the form u 2 v_{1} 2 v_{2} 2 … 2 v_{k} 2 w where u and w are Fibonacci compositions of m − 1 and each v_{i} is a Fibonacci composition of m − 2.

There is an analogous formula for F_{mn−1}, corresponding to compositions of multiples of m that start with 2, which have the generating function 1 + xf_{m,m−2}. A straightforward computation gives the following result, also due to Hoggatt [3].

Proposition 10.

1 + xf_{m,m−2} = 1 + ∑_{n=1}^{∞} F_{mn−1}x^{n} = (1 − F_{m−1}x − \frac{F_{m}^{2}x^{2}}{1 − F_{m+1}x})^{−1} .  (13)

There is a simple combinatorial interpretation for Proposition 10. In the free monoid of Fibonacci compositions of multiples of m that start with 2, the primes of weight 1 are the Fibonacci compositions of m that start with 2, and there are F_{m−1} of them. Every other prime of this free monoid is of the form 2 u v_{1} … v_{k} w, for k ≥ 0, where u and w are Fibonacci composition of m − 1 (counted by F_{m}) and each v_{i} is a Fibonacci composition of m (counted by F_{m+1}).

There don’t seem to be results as simple as Propositions 9 and 10 for f_{m,i} with i not equal to 0 or m − 2.

For i = m − 1, we have by (11)

f_{m,m−1} = ∑_{n=0}^{∞} F_{m(n+1)} = \frac{F_{m}}{1 − L_{m}x + (−1)^{m}x^{2}} ,  (14)

and a straightforward calculation gives

1 + xf_{m,m−1} = (1 − \frac{F_{m}x}{1 − 2F_{m−1}x + (−1)^{m}x^{2}} )^{−1}.  (15)

It is possible to describe the corresponding primes explicitly, but there doesn’t seem to be a simple combinatorial explanation for their generating function (15).

We note also that if m is odd then by (11),

f_{m,m−1} = ∑_{n=0}^{∞} F_{mn+m}x^{n} = \frac{F_{m}}{1 − L_{m}x − x^{2}} .

Although this formula looks like it should have a simple combinatorial explanation, there does not seem to be one.

In the next two sections we consider bisection and trisection in more detail.

5. Bisection

We now consider the case m = 2 of (11), which gives

f_{2,0} = \frac{1 − x}{1 − 3x + x^{2}}

and

f_{2,1} = \frac{1}{1 − 3x + x^{2}} .

We leave it to the reader to give a combinatorial interpretation of the formula f_{2,1} = (1 − x)^{−1}f_{2,0}.

The case m = 2 of (12) is

f_{2,0} = \frac{1 − x}{1 − 3x + x^{2}} = (1 − 2x − x^{2} − x^{3} − ⋯)^{−1} = (1 − 2x − \frac{x^{2}}{1 − x})^{−1}.  (16)

and the primes of the free monoid of Fibonacci compositions of even integers are the composition 2 and compositions of the form 1 2^{i} 1 for non-negative integers i. The generating function for the primes, together with (3), gives formula (vi) of section 1,

F_{2n+1} = ∑_{a∈C(n)} 2^{#{i:a_{i}=1}}.

We also have the identity

1 + x^{k}f_{2,0} = 1 + \frac{x^{k}(1 − x)}{1 − 3x + x^{2}} = (1 − \frac{x^{k}(1 − x)}{1 − 3x + x^{2} + x^{k} − x^{k+1}} )^{−1},  (17)

so x^{k}(1 − x)/(1 − 3x + x^{2} + x^{k} − x^{k+1}) is the generating function for primes in the free monoid of Fibonacci compositions of even integers that start with 2 1^{2k−2}. Only the case k = 1 of (17), which is also the case m = 2 of (13), is especially simple (though the prime counting sequence for k = 2 is \underline{A052921}). Here we have

1 + xf_{2,0} = (1 − x − \frac{x^{2}}{1 − 2x})^{−1} = (1 − x − x^{2} − 2x^{3} − 4x^{4} − 8x^{5} − ⋯)^{−1},

which gives the formula

F_{2n−1} = ∑_{a∈C(n)} 2^{#{i:a_{i}=1}+n−2k},

where k is the number of parts of the composition a.

We note also that the continued fraction formula

1 + xf_{2,0} = \frac{1 − 2x}{1 − 3x + x^{2}} = \frac{1}{1 − \frac{x}{1 − \frac{x}{1 − x}}}

shows that F_{2n−1}, for n > 0, is the number of Dyck paths of length 2n and height at most 3 (see, e.g., Flajolet [2]).

The analogous formulas for f_{2,1} are somewhat simpler than those for f_{2,0}.

Proposition 11. Fix an integer k ≥ 1. The set of Fibonacci compositions of even numbers that start with 1 2^{k−1} is a free monoid whose primes are of the form 1 2^{k−1} 2^{i} q 1 2^{j}, where i and j are nonnegative integers and q is an element of the free monoid Q with primes

1 2^{l} 1 2^{m}, for l ≥ 0 and 0 ≤ m ≤ k − 2.

This gives identity

1 + x^{k}f_{2,1} = 1 + \frac{x^{k}}{1 − 3x + x^{2}} = (1 − \frac{x^{k}}{1 − 3x + x^{2} + x^{k}} )^{−1}.  (18)

For k = 1, the free monoid Q contains only the empty word, and the primes are of the form 1 2^{i} 1 2^{j} for i, j ≥ 0.

Proof. Let M be the monoid of Fibonacci compositions of even numbers that start with 1 2^{k−1}. By Lemma 4, M is a free monoid. A prime of M is a Fibonacci composition that starts with 1 2^{k−1} and contains an even number of parts 1, where the jth part 1, for j > 1 and odd, is followed by at most k − 2 parts 2. It is clear that these primes are as described in the proposition.

The generating function for Q is

u(x) = (1 − ∑_{i=1}^{k−1} \frac{x^{i}}{1 − x})^{−1} = \frac{(1 − x)^{2}}{1 − 3x + x^{2} + x^{k}} .

Thus the generating function for the primes of M is

x^{k} · \frac{1}{1 − x} · u(x) · \frac{1}{1 − x} = \frac{x^{k}}{1 − 3x + x^{2} + x^{k}} .

For k = 1, (18) gives

1 + \frac{x}{1 − 3x + x^{2}} = (1 − \frac{x}{(1 − x)^{2}} )^{−1} = (1 − x − 2x^{2} − 3x^{3} − ⋯)^{−1}.

We can see directly that there are n prime compositions of 2n, since these are compositions of 2n of the form 1 2^{i} 1 2^{j} and there are n solutions of i + j = n − 1.

This identity gives formula (iv) of Section 1,

F_{2n} = ∑_{a∈C(n)} a_{1}a_{2} ⋯ a_{k},  (19)

for n ≥ 1, as shown by Moser and Whitney [8].

Stanley [12, p. 52] gives a combinatorial interpretation of (19): The sum ∑ a_{1}a_{2} ⋯ a_{k} is the number of ways of inserting at most one vertical bar in each of the n−1 spaces separating a line of n dots, and then circling one dot in each compartment. Replacing each bar by a 1, each uncircled dot by a 2, and each circled dot by a 1 gives all Fibonacci compositions of 2n − 1 exactly once. As an example for n = 8, we have

• ⊙ | ⊙ • | ⊙ | • • ⊙ ⟺ 21112111221

We can explain this bijection in terms of our free monoid approach: if we insert a bar at the beginning of one of these arrangements of bars and dots, then we have a sequence of configurations of the form | •^{i} ⊙ •^{j}, and this configuration corresponds to the prime 1 2^{i} 1 2^{j}.

For k = 2, the generating function for the primes in Proposition 11 is

\frac{x^{2}}{1 − 3x + 2x^{2}} = \frac{x^{2}}{(1 − 2x)(1 − x)} = ∑_{n=2}^{∞} ∑_{i=0}^{n−2} 2^{i}x^{n} = ∑_{n=2}^{∞}(2^{n−1} − 1)x^{n}.

This gives formula (v) of Section 1:

F_{2n−2} = ∑_{a∈C(n)}(2^{a_{1}−1} − 1)(2^{a_{2}−1} − 1) ⋯ (2^{a_{k}−1} − 1),  (20)

for n ≥ 1. From Proposition 11, the prime compositions corresponding to (20) are of the form

1 2 2^{l_{0}} 1 2^{l_{1}} 1^{2} 2^{l_{2}} 1^{2} ⋯ 1^{2} 2^{l_{m}} 1^{2} 2^{l_{m+1}},

with m ≥ 0, where l_{0}, …, l_{m+1} are nonnegative integers. To see combinatorially that there are 2^{n−1} − 1 such compositions of 2n, we start with the composition of 2n − 2 with n − 1 parts, all equal to 2. We choose some nonempty subset of the parts, which we can do in 2^{n−1} − 1 ways. We replace the first selected 2 with 1 and replace each other selected 2 with 1 1. Finally we insert 1 2 at the beginning.

For k > 2, the primes in Proposition 11 are more complicated, but for k = 3 and k = 4 the sequences that count them are \underline{A048739} and \underline{A077849}.

6. Trisection

Now we consider trisections of the Fibonacci sequence, for which we have

f_{3,0} = \frac{1 − x}{1 − 4x − x^{2}}

f_{3,1} = \frac{1 + x}{1 − 4x − x^{2}}

f_{3,2} = \frac{2}{1 − 4x − x^{2}} .

Proposition 9 and its combinatorial interpretation give us a combinatorial interpretation to the identity

f_{3,0} = (1 − 3x − 4x^{2} − 4x^{3} − ⋯)^{−1} = (1 − 3x − 4 \frac{x^{2}}{1 − x})^{−1},  (21)

which gives the formula

F_{3n+1} = ∑_{a∈C(n)} 3^{#{i: a_{i}=1}}4^{#{j: a_{j}≠1}},

for n ≥ 0: the free monoid of Fibonacci compositions of numbers divisible by 3 has three primes of weight one, 1 1 1, 1 2, and 2 1, and four primes of weight n for each n ≥ 2, each of which is of the form

a b c,

where a and c are either 1 1 or 2, and b is the composition

2 1 2 1 ⋯ 2 1 2

with n − 2 parts 1 and n − 1 parts 2.

Next, we give a free monoid interpretation to the case m = 3 of (15):

1 + xf_{3,2} = 1 + \frac{2x}{1 − 4x − x^{2}} = (1 − \frac{2x}{1 − 2x − x^{2}} )^{−1}.  (22)

The left side of (22) counts Fibonacci compositions of numbers divisible by 3 that start with a part 1. In this free monoid there are two primes of weight one, 1 1 1 and 1 2. For n ≥ 2, a prime p of weight n ends with 2 1, 2 1 1 or 2 2, so it must be of one the following three kinds:

(1) p is obtained from a prime of weight n − 1 by attaching 2 1 in the end;

(2) p is obtained from a prime of weight n − 1 ending with a part 1 by replacing the 1 with 2 1 1;

(3) p is obtained from a prime of weight n − 1 ending with a part 1 by replacing the 1 with 2 2.

Let a_{n} be the number of primes of weight n and let b_{n} be the number of primes of weight n that end with a part 1. Then we have a_{n} = a_{n−1} + 2b_{n−1} and b_{n} = a_{n−1} + b_{n−1}. Thus

a_{n} = a_{n−1} + 2b_{n−1} = a_{n−1} + 2(a_{n−2} + b_{n−2})
= (a_{n−1} + a_{n−2}) + (a_{n−2} + 2b_{n−2}) = (a_{n−1} + a_{n−2}) + a_{n−1}
= 2a_{n−1} + a_{n−2}

for n ≥ 3, and since a_{2} = a_{1} + 2b_{1} = 2 + 2 = 4 = 2a_{1} + a_{0}, where a_{0} = 0, the recurrence holds for n ≥ 2. Thus we find that the generating function for primes is

\frac{2x}{1 − 2x − x^{2}} ,  (23)

and (22) follows. The coefficients of (23) are sequence \underline{A052542} or \underline{A163271}. They are twice the Pell numbers, sequence \underline{A000129}.

The case m = 3 of Proposition 10 is

1 + xf_{3,1} = (1 − x − \frac{4x^{2}}{1 − 3x})^{−1} = (1 − x − ∑_{n=1}^{∞} 4 · 3^{n−2}x^{n})^{−1} ,

where the counting sequence for the primes is \underline{A003946} We note also that

1 + xf_{3,0} = (1 − \frac{x(1 − x)}{1 − 3x − 2x^{2}} )^{−1} ,

where the primes are counted by \underline{A104934}, and

1 + xf_{4,3} = (1 − \frac{3x}{1 − 4x + x^{2}} )^{−1} ,

where the primes are counted by \underline{A005320}.

7. Acknowledgment

This work was partially supported by a grant from the Simons Foundation (#229238 to Ira Gessel).

References

[1] A. T. Benjamin and J. J. Quinn, Proofs That Really Count: The Art of Combinatorial Proof, Dolciani Mathematical Expositions, Vol. 27, Mathematical Association of America, 2003.

[2] P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32 (1980), 125–161.

[3] V. E. Hoggatt, Jr., Generalized rabbits for generalized Fibonacci numbers, Fibonacci Quart. 6 (1968), 105–112.

[4] V. E. Hoggatt, Jr. and D. A. Lind, A primer for the Fibonacci numbers: Part VI, Fibonacci Quart. 5 (1967), 445–460.

[5] V. E. Hoggatt, Jr. and D. A. Lind, Fibonacci and binomial properties of weighted compositions, J. Combinatorial Theory 4 (1968), 121–124.

[6] V. E. Hoggatt, Jr. and D. A. Lind, Compositions and Fibonacci numbers, Fibonacci Quart. 7 (1969), 253–266.

[7] A. O. Munagi, Euler-type identities for integer compositions via zig-zag graphs, Integers 12 (2012), Paper #A60.

[8] L. Moser and E. L. Whitney, Weighted compositions, Canad. Math. Bull. 4 (1961), 39–43.

[9] M.-P. Schützenberger, Une théorie algébrique du codage, Séminaire Paul Dubreil et Charles Pisot, 9e année: 1955/56, Algèbre et théorie des nombres, Exp. No. 15, Secrétariat mathématique, Paris, 1956.

[10] A. V. Sills, Compositions, partitions, and Fibonacci numbers, Fibonacci Quart. 49 (2011), 348–354.

[11] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org.

[12] R. P. Stanley, Enumerative Combinatorics, Volume 1, 2nd edition, Cambridge University Press, 2011.

[13] B. Tilson, The intersection of free submonoids of a free monoid is free, Semigroup Forum 4 (1972), 345–350.

[14] D. Zeilberger, The composition enumeration reciprocity theorem, preprint, http://

    www.math.rutgers.edu/~zeilberg/pj.html, February 28 2012.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 11B39, 68R15. Keywords: Fibonacci number, composition, free monoid.

(Concerned with sequences \underline{A000045}, \underline{A000129}, \underline{A000930}, \underline{A001519}, \underline{A001906}, \underline{A003269}, \underline{A003520}, \underline{A003946}, \underline{A005320}, \underline{A005708}, \underline{A005709}, \underline{A005710}, \underline{A005711}, \underline{A014445}, \underline{A015448}, \underline{A017898}, \underline{A017900}, \underline{A017901}, \underline{A017902}, \underline{A017903}, \underline{A017904}, \underline{A017905}, \underline{A017906}, \underline{A017907}, \underline{A017908}, \underline{A017909}, \underline{A033887}, \underline{A048739}, \underline{A052542}, \underline{A052921}, \underline{A077849}, \underline{A104934}, \underline{A122367}, and \underline{A163271}.)

Received March 8 2013; revised version received March 16 2013. Published in Journal of Integer Sequences, March 16 2013.

Return to Journal of Integer Sequences home page.