Compression Theorems for Periodic Tilings and Consequences

Arthur T. Benjamin Department of Mathematics Harvey Mudd College Claremont, CA 91711 USA

                   benjamin@hmc.edu

Alex K. Eustis Department of Mathematics UC San Diego La Jolla, CA 92037 USA

                  akeustis@gmail.com

Mark A. Shattuck Department of Mathematics University of Tennessee Knoxville, TN 37996 USA

                 shattuck@math.utk.edu

Abstract

We consider a weighted square-and-domino tiling model obtained by assigning real number weights to the cells and boundaries of an n-board. An important special case apparently arises when these weights form periodic sequences. When the weights of an nm-tiling form sequences having period m, it is shown that such a tiling may be regarded as a meta-tiling of length n whose weights have period 1 except for the first cell (i.e., are constant). We term such a contraction of the period in going from the longer to the shorter tiling as “period compression.” It turns out that period compression allows one to provide combinatorial interpretations for certain identities involving continued fractions as well as for several identities involving Fibonacci and Lucas numbers (and their generalizations).

1 Introduction

In what follows, ℤ, ℕ, and ℙ denote, respectively, the integers, the nonnegative integers, and the positive integers. Empty sums take the value 0 and empty products the value 1, with 0^{0} := 1. Let F_{n} and L_{n} denote the Fibonacci and Lucas numbers, defined, respectively, by F_{0} = 0, F_{1} = 1 with F_{n} = F_{n−1} +F_{n−2} if n ⩾ 2 and by L_{0} = 2, L_{1} = 1 with L_{n} = L_{n−1} +L_{n−2} if n ⩾ 2.

We start with a slight generalization of the weighted tiling model described in Graham, Knuth and Patashnik [5] where we assign real number weights not only to the cells but also to the boundaries of an n-board. We then consider the special case when these weights form periodic sequences. When the weights of an nm-tiling form sequences having period m, it is shown that such a tiling may be regarded as a meta-tiling of length n whose weights have period 1 except for the first cell (i.e., are constant). Such a contraction of the period in going from the longer to the shorter tiling we term as “period compression.”

In the next section, we recall (and slightly generalize) the weighted tiling model described in [5], and in the third, we establish our three main period compression theorems for tilings having periodic weights. In the fourth section, we then use these theorems to simplify infinite periodic continued fractions and to supply a combinatorial interpretation for a certain finite continued fraction identity involving Fibonacci and Lucas numbers, answering a question raised by Benjamin and Quinn [2, p. 146]. In the final section, we use the compression theorems to provide combinatorial arguments of generalizations of several formulas for F_{km} and L_{km} which occur in Vajda [11], as requested by Benjamin and Quinn [2, p. 145]. (Taking all weights to be unity will yield the identities in Vajda [11].)

2 Weighted Tilings

In this section, we recall (and slightly generalize) the weighted tiling model described in Graham, Knuth, and Patashnik [5, Section 6.7] and review some of its properties. First consider a board of length n with cells labelled 1 to n from left to right. A tiling of this board (termed an n-tiling) is an arrangement of indistinguishable squares and indistinguishable dominos which cover it completely, where pieces do not overlap, a domino is a rectangular piece covering two cells, and a square is a piece covering a single cell. Let F_{n} denote the set of all n-tilings; recall that

|F_{n}| = F_{n+1}, n ∈ ℙ.  (2.1)

(If we set F_{0} = {ϕ}, the “empty tiling,” then (2.1) holds for n = 0 as well.)

Let (a_{i})_{i⩾1} and (b_{i})_{i⩾1} be sequences of real numbers and suppose n ∈ ℙ. Given T ∈ F_{n}, assign a weight to each tile of T according to its location as follows: (i) a square covering cell k receives weight a_{k}, and (ii) a domino covering the k^{th} boundary receives weight b_{k} (by the k^{th} boundary, we mean the boundary between cells k and k + 1, 1 ⩽ k ⩽ n − 1).

a_{1} a_{2} a_{3} ⋯ a_{n}
b_{1} b_{2} b_{3} ⋯ b_{n−1}

Define the weight w(T) to be the product of the weights of tiles and define the weighted sum |1 : n| by

|1 : n| := ∑_{T ∈F_{n}} w(T).  (2.2)

For example, when n = 4, there are the five 4-tilings pictured below,

\begin{aligned}a_{1} a_{2} a_{3} a_{4} & & & a_{1} a_{2}  b_{3} & & & a_{1}  b_{2}  a_{4} \\ & b_{1} & a_{3} & a_{4} & b_{1} & b_{3} \end{aligned}

which implies

|1 : 4| = a_{1}a_{2}a_{3}a_{4} + a_{1}a_{2}b_{3} + a_{1}b_{2}a_{4} + b_{1}a_{3}a_{4} + b_{1}b_{3}.

If a_{i} = b_{i} = 1 for all i, then each tiling receives unit weight and |1 : n| = F_{n+1}.

Remarks. If a_{i} = 1 and b_{i} = q^{i}t or if a_{i} = q^{i} and b_{i} = t for all i, then one gets, respectively, the q-Fibonacci polynomials studied by Carlitz [3] and Cigler [4] and by Shattuck and Wagner [9]. If b_{i} = 1 for all i, then (2.2) reduces to the continuant polynomial described in Graham, Knuth and Patashnik [5, p. 301–309].

For integers 1 ⩽ i ⩽ j ⩽ n, we write |i : j| to mean the sum of weights of tilings of the sub-board starting at cell i and ending at cell j. For example, |i : i| = a_{i} and |i : i + 1| = a_{i}a_{i+1} + b_{i}. We’ll take |i : i − 1| = 1 and |i : i − 2| = 0 as conventions.

Considering whether or not the k^{th} boundary of a tiling is covered by a domino yields the identity

|i : j| = |i : k||k + 1 : j| + b_{k}|i : k − 1||k + 2 : j|, i ⩽ k ⩽ j,  (2.3)

the k = i and k = j − 1 cases of which give the recurrences

|i : j| = a_{i}|i + 1 : j| + b_{i}|i + 2 : j|  (2.4)

and

|i : j| = a_{j}|i : j − 1| + b_{j−1}|i : j − 2|.  (2.5)

Let L_{n} denote the set of n-tilings in which a domino can wrap around from cell n back to cell 1 (termed Lucas n-tilings or n-bracelets). When a bracelet has a wraparound domino, it is called out-of-phase; otherwise, it is called in-phase. Recall that

|L_{n}| = L_{n}, n ∈ ℙ,  (2.6)

the n^{th} Lucas number (see, e.g., [2, p. 18], [10, p. 246]. If we interpret L_{0} = 2 to mean that there are two empty 0-bracelets, one of which is in-phase, the other out-of-phase, then (2.6) holds for n = 0 as well.

We extend slightly the prior model for n-tilings to n-bracelets by keeping all weights the same as before and assigning a wraparound domino weight b_{n}. One gets the weighted sum

|1 :: n| := ∑_{T ∈L_{n}} w(T),  (2.7)

which reduces to L_{n} when a_{i} = b_{i} = 1 for all i.

Remark. If a_{i} = 1 and b_{i} = q^{i}t or if a_{i} = q^{i} and b_{i} = t for all i, then one gets, respectively, the q-Lucas polynomials studied by Carlitz [3] and by Shattuck and Wagner [9].

Considering whether or not a member of L_{n} contains a wraparound domino gives

|1 :: n| = |1 : n| + b_{n}|2 : n − 1|, n ⩾ 1.  (2.8)

The |1 :: n| do not appear to satisfy simple two-term recurrences like (2.4) or (2.5).

Given 1 ⩽ i ⩽ j ⩽ n, let |i :: j| denote the sum of weights of tilings of the sub-board starting at cell i and ending at cell j in which a domino can wrap around from cell j back to cell i. For example, |i :: i| = a_{i} and |i :: i + 1| = a_{i}a_{i+1} + b_{i} + b_{i+1}. By convention, we’ll take |i :: i − 1| = 2.

3 Periodic Boards

Throughout this section, we consider the important special case of |1 : n| in which the a_{i} and b_{i} are both periodic sequences. For m ⩾ 1, we say that a board has period m if a_{i+m} = a_{i} and b_{i+m} = b_{i} for all i. It will be convenient to think of such tilings within a rectangular grid of width m, where a domino’s left half may end one row whenever its right half starts the next.

\begin{matrix}a_{1} a_{2} ⋯ a_{nm} \\ b_{1} b_{2} ⋯ b_{nm−1} \end{matrix}  ⟹  \begin{aligned}⋮  ⋮ & \} & n \\ & & rows \\ a_{1} a_{2} ⋯  a_{m} \\ b_{1} b_{2} ⋯ b_{m−1} b_{m} \end{aligned}

Generalizing the tail-swapping technique extends the identity [2, p. 28]

F_{2m+1} = L_{m}F_{m+1} + (−1)^{m+1}, m ⩾ 0,  (3.1)

to Proposition 3.1. If a board has period m, then

|1 : 2m| = L|1 : m| + β, m ⩾ 0,  (3.2)

where

L := |1 :: m| and β := (−1)^{m+1}∏_{k=1}^{m} b_{k}.  (3.3)

Proof. If λ ∈ F_{2m}, then arrange λ in two parallel rows of length m, breaking a domino covering cells m and m + 1 if necessary. Suppose that j is the largest i, 0 ⩽ i ⩽ m, such that neither boundary i nor boundary i + m is covered by a domino (in which case, we say that a fault occurs at i; we’ll assume for now that λ has at least one fault). Exchange the portion of the first row to the right of boundary j with the portion of the second row to the right of boundary j + m (i.e., perform a tailswap). This yields a pair of tilings: row 1 is an ordinary m-tiling, but row 2 is a Lucas m-tiling because it can begin and end with a half-domino. Specifically, this happens if row 1 of the original tiling ends in a half-domino, because the tailswap in this case moves the half-domino to row 2 where the other half is located, as illustrated below.

Figure 3.1: Tiling before tailswap, m = 7.

Figure 3.2: Tiling after tailswap.

Observe that tailswapping is its own inverse since it does not change the location of the last fault. It also preserves weight by m-periodicity, since all tiles stay in their original column. There is exactly one fault-free configuration (accounted for by the β term) and it must consist of all dominos in staggered formation (since any square will necessarily have a fault line either to its left or to its right). A quick exercise in visualization shows that this configuration has weight ∏_{k=1}^{m} b_{k} and belongs to F_{2m} if m is odd and to F_{m} × L_{m} if m is even, as shown below.

Figure 3.3: The fault-free configuration, m = 7.

Figure 3.4: The fault-free configuration, m = 6.

Arranging a (j + 2m)-tiling in two parallel rows of length j + m and m (flush right) and applying the preceding argument extends identity (3.2) to

|1 : j + 2m| = L|1 : j + m| + β|1 : j|, j ⩾ 0,  (3.4)

and starting tilings at cell i gives the further generalization

|i : j + 2m| = L|i : j + m| + β|i : j|, 1 ⩽ i ⩽ j.  (3.5)

(Note that L = |1 :: m| = |i :: i + m − 1| for all i ⩾ 1, by m-periodicity.)

Consider the sequence G_{n} := |1 : nm|, n ⩾ 0, where the associated a_{i} and b_{i} both have period m. Taking j = nm in (3.4) gives a second order recurrence for G_{n} with constant coefficients:

Proposition 3.2. If a board has period m, then

G_{n+2} = LG_{n+1} + βG_{n}, n ⩾ 0,  (3.6)

where G_{0} = 1 and G_{1} = |1 : m|.

When all weights are unity, recurrence (3.6) reduces to

F_{(n+2)m+1} = L_{m}F_{(n+1)m+1} + (−1)^{m+1}F_{nm+1},  (3.7)

which generalizes (3.1). Induction combining (2.5) when i = 1 and j = n with recurrence (3.6) yields our first period-compression theorem.

Theorem 3.3. If a board has period m, then

|1 : nm| = ∥1 : n∥, n ⩾ 0,  (3.8)

where ∥1 : n∥ is the sum of weights of n-tilings using the meta-weights

\begin{matrix}A_{1} = |1 : m|, \\ A_{2} = ⋯ = A_{n} = L = |1 :: m|, \end{matrix}

and

B_{1} = ⋯ = B_{n−1} = β = (−1)^{m+1} ∏_{k=1}^{m} b_{k}.

Proof. It is instructive to provide a combinatorial proof of (3.8). Note first that ∥1 : n∥ is a weighted sum of meta-tilings on n cells, where meta-squares are themselves (weighted) m-bracelets (except for cell 1, which cannot contain an out-of-phase bracelet) and where meta-dominos each have weight β. First suppose m is odd, and let λ be such a meta-tiling of length n. We’ll construct, in an inductive manner, an nm-tiling (in rectangular form) with period m of the same weight. We’ll call meta-squares in-phase or out-of-phase depending on whether or not they correspond to in-phase or out-of-phase bracelets.

Let c_{i}, i ⩾ 1, denote the i^{th} piece of λ (going from left to right). We’ll consider the three cases:

(i) c_{1} is an in-phase meta-square and c_{2} isn’t an out-of-phase meta-square;

(ii) c_{1} is an in-phase meta-square and c_{2} is an out-of-phase meta-square;

(iii) c_{1} is a meta-domino.

For (i), fill out the first row of an n×m rectangle with the (in-phase) m-tiling corresponding to c_{1}. For (ii), let c_{ℓ}, ℓ ⩾ 2, be the last out-of-phase square in a run of out-of-phase squares directly following c_{1}. Swap (right) tails of c_{1} and c_{ℓ} to obtain c′_{1} and c′_{ℓ} (which can always be done since m is odd). Note that c′_{1} ends with a half-domino but doesn’t start with one and that c′_{ℓ} starts with a half-domino but doesn’t end with one. Fill out the first ℓ rows of an n × m rectangle with c′_{1}, c_{2}, …, c_{ℓ−1}, c′_{ℓ}.

For (iii), if c_{ℓ} again denotes the last square in a run (possibly of length zero, in which case ℓ = 1) of out-of-phase meta-squares directly following c_{1}, then fill out the first ℓ + 1 rows of the rectangle with d_{1}, c_{2}, …, c_{ℓ}, d_{2}, where d_{1} consists of \frac{m−1}{2} dominos followed by a half-domino and d_{2} is a half-domino followed by \frac{m−1}{2} dominos. Now repeat the above argument using any remaining pieces of λ.

If m is even, then proceed as in the first two cases above provided that the tails of c_{1} and c_{ℓ} can be swapped in (ii). The cases in which (I) c_{1} is a meta-domino, or (II) c_{1} is an inphase meta-square and c_{ℓ} is an out-of-phase meta-square, with both tilings consisting solely of dominos, conveniently cancel (in general, toggle on the first occurrence of a meta-domino or a c_{1}/c_{ℓ} pair with all staggered dominos) since the meta-domino in (I) contributes β and the two meta-squares in (II) contribute −β (as m is even) towards the overall weight of a meta-tiling, which completes the proof.

We call (3.8) a “period-compression” theorem because it allows us to rewrite a period-m board in terms of a meta-board with period 1 (except for the first cell). It will be immediately applicable to periodic continued fractions, once we also state the version of the theorem for |2 : nm|.

Theorem 3.4. For a board with period m,

|2 : nm| = |2 : m| · ∥2 : n∥, n ⩾ 0,  (3.9)

with meta-weights defined as before.

Proof. Applying (3.5) once with i = 2, j = nm and again with i = 2, j = n, m = 1 yields (3.9), by induction on n ⩾ 0.

Period compression takes an even simpler form for Lucas bracelets.

Theorem 3.5. For a board with period m,

|1 :: nm| = ∥2 :: n + 1∥, n ⩾ 0,  (3.10)

with meta-weights defined as before.

Proof. Note that both sides of (3.10) are equal when n = 0 and n = 1 and can be expressed, using (2.8), as linear combinations of terms which satisfy the same recurrence in n, by (3.5).

We were unable to find a formula comparable to (3.9) for bracelets. Slight modifications of the combinatorial proof given for (3.8) apply to (3.9) and (3.10). If we take all weights to be unity, then Theorems 3.4 and 3.5 reduce to

Corollary 3.6. For all n, m ∈ ℕ,

F_{nm} = F_{m}∥2 : n∥  (3.11)

and

L_{nm} = ∥2 :: n + 1∥,  (3.12)

where the weighted sums refer to the board with constant weights A_{i} = L_{m} and B_{i} = (−1)^{m+1} for all i ⩾ 2.

Remark. Writing out (3.11) and (3.12) explicitly, one gets the following pair of identities, the first of which occurs in [6] and [7], the second as (V82) in Benjamin and Quinn [2, p. 145]:

F_{nm} = F_{m} ∑_{i=0}^{⌊ \frac{n−1}{2} ⌋}(−1)^{(m+1)i}\binom{n − 1 − i}{i}L_{m}^{n−1−2i}  (3.13)

and

L_{nm} = ∑_{i=0}^{⌊ \frac{n}{2} ⌋}(−1)^{(m+1)i} \frac{n}{n − i}\binom{n − i}{i}L_{m}^{n−2i}.  (3.14)

4 Applications to Continued Fractions

The weighted tiling model described in the second section is closely associated with finite continued fractions. The proposition below, the proof of which we include for completeness, is a slight generalization of Identity (6.135) of Graham, Knuth, and Patashnik [5] and provides a simple combinatorial interpretation for the numerator and the denominator of a finite continued fraction. For other combinatorial interpretations of continued fractions, see [1] as well as Chapter 4 of [2].

Proposition 4.1. Let a_{1}, b_{1}, a_{2}, b_{2}, …, b_{n−1}, a_{n} be any real numbers. Then

a_{1} + \frac{b_{1}}{a_{2} + _{\frac{b_{2}}{...+ \frac{b_{n−1}}{an}}}} = \frac{|1 : n|}{|2 : n|},  (4.1)

excluding division by zero. Furthermore, if a_{i} ∈ ℤ and b_{i} ∈ \{−1, 1\}, then \frac{|1:n|}{|2:n|} is a fraction in lowest terms.

Proof. We’ll prove, more generally, that

[i : j] = \frac{|i : j|}{|i + 1 : j|},  1 ⩽ i ⩽ j ⩽ n,  (4.2)

where [i : j] denotes the continued fraction

a_{i} + \frac{b_{i}}{a_{i+1} + _{\frac{b_{i+1}}{...+ \frac{b_{j−1}}{a_{j}}}}} .

Induct on the length, j − i + 1, of the continued fraction, the case in which j = i clear. If j > i, then

[i : j] = a_{i} + \frac{b_{i}}{[i + 1 : j]} = a_{i} + \frac{b_{i}}{|i + 1 : j|/|i + 2 : j|}
= \frac{a_{i}|i + 1 : j| + b_{i}|i + 2 : j|}{|i + 1 : j|} = \frac{|i : j|}{|i + 1 : j|},

by recurrence (2.4).

For the second part of the theorem, we’ll show, more generally, that |i : n| and |i + 1 : n| are relatively prime for all i, 1 ⩽ i ⩽ n, by induction on i starting with i = n, where n ∈ ℙ is fixed. If i < n, then by (2.4),

gcd(|i : n|, |i + 1 : n|) = gcd(a_{i}|i + 1 : n| ± |i + 2 : n|, |i + 1 : n|)
= gcd(|i + 2 : n|, |i + 1 : n|) = 1,

completing the proof.

If b_{i} = 1 for all i, then (4.1) reduces to (6.135) in [5]. Combining (4.1) with the periodcompression theorems provides a way of simplifying infinite periodic continued fractions.

Theorem 4.2. Let a_{1}, a_{2}, … and b_{1}, b_{2}, … be m-periodic sequences of real numbers. Then

a_{1} + \frac{b_{1}}{a_{2} + \frac{b_{2}}{...}} = \frac{1}{|2 : m|}(|1 : m| + \frac{β}{L + _{\frac{β}{L+ \frac{β}{...}}}} ),  (4.3)

provided that the fraction on the left converges, where L and β are as in (3.3).

Proof. Let n ⩾ 1. By Theorems 3.3 and 3.4,

\frac{|1 : nm|}{|2 : nm|} = \frac{1}{|2 : m|}(\frac{∥1 : n∥}{∥2 : n∥}).

Using (4.1) and taking the limit as n → ∞ then gives (4.3).

Example. Consider a regular periodic continued fraction: b_{i} = 1 for all i and let a_{1}, a_{2}, a_{3}, … be the period-3 sequence 3, 4, 5, 3, 4, 5,. . .. Since bounded, monotonic sequences converge, all regular continued fractions (i.e., those with b_{i} = 1 and a_{i} > 0 for all i) converge, so we can use Theorem 4.2 with m = 3. The relevant calculations are |1 : 3| = 68, |2 : 3| = 21, L = |1 : 3| + |2 : 2| = 72, β = 1. Therefore,

3 + \frac{1}{4 + _{\frac{1}{5+ \frac{1}{...}}}} = \frac{1}{21}(68 + \frac{1}{72 + _{\frac{1}{72+ \frac{1}{...}}}} ).

Observe that the continued fraction on the right side must be the positive solution to x = \frac{1}{72+x}, and the quadratic formula gives x = −36 + \sqrt{1297}. Therefore, the original continued fraction is equal to \frac{1}{21}(32 + \sqrt{1297}). This method will work with any regular periodic continued fraction, but note that β = −1 when m is even.

Period compression for periodic tilings can now be used to provide a combinatorial proof of a finite continued fraction identity involving Fibonacci and Lucas numbers, answering a question raised by Benjamin and Quinn [2, p. 146].

Theorem 4.3. For all m, n ∈ ℙ,

\frac{F_{(n+1)m}}{F_{nm}} = L_{m} − \frac{(−1)^{m}}{L_{m} − _{\frac{(−1)^{m}}{...− \frac{(−1)^{m}}{Lm}}}} ,  (4.4)

where L_{m} appears n times in the continued fraction.

Proof. By (3.11),

\frac{F_{(n+1)m}}{F_{nm}} = \frac{F_{m}∥2 : n + 1∥}{F_{m}∥2 : n∥} = \frac{∥2 : n + 1∥}{∥3 : n + 1∥},

where we have shifted the indices of the denominator in the last step, which can be done since the weights are constant. Identity (4.4) now follows from (4.2) when a_{i} = L_{m} and b_{i} = (−1)^{m+1} for all i ⩾ 2.

Observe that we have shown that the numerator and denominator of the rational number given by the algebraically-defined continued fraction in (4.4) are the combinatorially-defined quantities ∥2 : n + 1∥ and ∥3 : n + 1∥, respectively (they are relatively prime by Proposition 4.1). Note that (4.4) occurs as (V106) on p. 146 of [2].

5 Fibonacci/Lucas Generalizations

In this section, we use periodic tilings to derive (by combinatorial arguments) generalizations of identities for Fibonacci and Lucas numbers found in [2, p. 145] and in [11]. Our strategy will be first to establish identities for tilings in which the weight sequences are constant and then to generalize them to identities for periodic tilings by applying the compression theorems of the third section. Our first identity involves relating a weighted tiling of odd length to shorter sub-tilings of even length.

Identity 5.1. For a board with constant weights a_{i} = A and b_{i} = B,

|1 : 2n + 1| = A ∑_{k=0}^{n} B^{k}|1 : 2n − 2k|.  (5.1)

Proof. The sum of the weights of the (2n + 1)-tilings ending with exactly k dominos is AB^{k}|1 : 2n − 2k|. Summing over k gives (5.1).

We can generalize this to period-m tilings by “uncompressing” (5.1) :

Theorem 5.2. For a board with period m,

|2 : (2n + 2)m| = L ∑_{k=0}^{n} β^{k}|2 : (2n + 1 − 2k)m|,  (5.2)

where L and β are defined by (3.3) above. In particular,

F_{(2n+2)m} = L_{m} ∑_{k=0}^{n}(−1)^{(m+1)k}F_{(2n+1−2k)m}.  (5.3)

Proof. Starting tilings at cell 2 in (5.1) gives, equivalently,

|2 : 2n + 2| = A ∑_{k=0}^{n} B^{k}|2 : 2n + 1 − 2k|  (5.4)

for a board with constant weights a_{i} = A and b_{i} = B, i ⩾ 2. Taking A = L and B = β in (5.4) gives

∥2 : 2n + 2∥ = L ∑_{k=0}^{n} β^{k}∥2 : 2n + 1 − 2k∥.  (5.5)

Multiply both sides of (5.5) by |2 : m|,

|2 : m| · ∥2 : 2n + 2∥ = L ∑_{k=0}^{n} β^{k}|2 : m| · ∥2 : 2n + 1 − 2k∥,

and Theorem 3.4 gives (5.2). To obtain (5.3), set a_{i} = b_{i} = 1 for all i in (5.2).

Our next identity relates tilings of odd length with shorter bracelets.

Identity 5.3. For a board with constant weights A and B,

|1 : 2n + 1| = ∑_{k=0}^{n}(−1)^{k}B^{k}|1 :: 2n + 1 − 2k|.  (5.6)

Proof. Let U denote the set of all ordered pairs (C, D), where C is a bracelet (starting at cell 1) and D is a line of dominos such that the combined length of the pair is 2n + 1. Define the sign of such a pair to be (−1)^{k}, where k is the number of dominos in D, and define the weight of such a pair to be the product of B^{k} and the weight of C. Note that the right side of (5.6) is the sum of the signed weights of the elements of U.

Define a sign-reversing, weight-preserving involution on U as follows: (i) If C is out-of-phase, then move the domino covering the first and last cells from C to D to get an in-phase bracelet two units shorter; (ii) If C is in-phase, take a domino from D (provided there is one) and place it on boundary 0 to get an out-of-phase bracelet two units longer. Observe that if two elements of U are paired, then their weights are negatives of one another, and that all elements of U are paired except those for which C is an in-phase (2n + 1)-bracelet and D contains no dominos; the sum of the signed weight of these elements is |1 : 2n + 1|.

Theorem 5.4. For a board with period m,

|2 : (2n + 2)m| = |2 : m| ∑_{k=0}^{n}(−1)^{k}β^{k}|1 :: (2n + 1 − 2k)m|.  (5.7)

In particular,

F_{(2n+2)m} = F_{m} ∑_{k=0}^{n}(−1)^{mk}L_{(2n+1−2k)m}.  (5.8)

Proof. As in the proof of Theorem 5.2, we start our tilings at cell 2. Taking A = L and B = β in (5.6), multiplying both sides by |2 : m|, and applying Theorems 3.4 and 3.5 yields (5.7). To obtain (5.8), set a_{i} = b_{i} = 1 in (5.7).

The next identity is like (5.6) except that we will start with an even-length rather than an odd-length tiling.

Identity 5.5. For a board with constant weights A and B,

|1 : 2n + 2| = (−1)^{n+1}B^{n+1} + ∑_{k=0}^{n}(−1)^{k}B^{k}|1 :: 2n + 2 − 2k|.  (5.9)

Proof. Let U denote the set of all ordered pairs (C, D) in which C is a bracelet (starting at cell 1) and D is a line of dominos such that the combined length of the pair is 2n + 2. Define the sign and weight of such a pair as in the proof of (5.6). Note that in this case, the sign-reversing involution in the proof of (5.6) has two types of fixed points: elements of U in which C is an in-phase (2n + 2)-bracelet and D is empty and the element in which C is an out-of-phase 0-bracelet and D contains n + 1 dominos. Therefore,

|1 : 2n + 2| + (−1)^{n+1}B^{n+1} = ∑_{k=0}^{n+1}(−1)^{k}B^{k}|1 :: 2n + 2 − 2k|,  (5.10)

which is equivalent to (5.9).

The same proof as before then gives

Theorem 5.6. For a board with period m,

|2 : (2n + 3)m| = |2 : m|((−1)^{n+1}β^{n+1} + ∑_{k=0}^{n}(−1)^{k}β^{k}|1 :: (2n + 2 − 2k)m|).  (5.11)

In particular,

F_{(2n+3)m} = (−1)^{(n+1)m}F_{m} + F_{m} ∑_{k=0}^{n}(−1)^{mk}L_{(2n+2−2k)m}.  (5.12)

Our final identity relates bracelets of odd length with shorter bracelets of even length.

Identity 5.7. For a board with constant weights A and B,

|1 :: 2n + 3| = AB^{n+1} + A ∑_{k=0}^{n} B^{k}|1 :: 2n + 2 − 2k|.  (5.13)

Proof. The right side counts (2n + 3)-bracelets according to k, the number of dominos at the beginning, where we start counting from the domino covering either boundary 1 or 2, depending on whether or not a bracelet is in-phase. For 0 ⩽ k ⩽ n, we see that the total weight of all bracelets beginning with exactly k dominos (when counted this way) is AB^{k}|1 :: 2n+2−2k|, since we can choose any bracelet of length 2n+2−2k with either phase and then insert k dominos followed by a square at the beginning (where the inserted dominos start at either cell 1 or 2 depending on whether or not the chosen bracelet is in-phase). For k = n + 1, we are forced to have an in-phase bracelet consisting of n + 1 dominos followed by a square.

Letting A = L and B = β, and applying Theorem 3.5 to both sides of (5.13), then gives

Theorem 5.8. For a board with period m,

|1 :: (2n + 3)m| = Lβ^{n+1} + L ∑_{k=0}^{n} β^{k}|1 :: (2n + 2 − 2k)m|.  (5.14)

In particular,

L_{(2n+3)m} = (−1)^{(n+1)(m+1)}L_{m} + L_{m} ∑_{k=0}^{n}(−1)^{(m+1)k}L_{(2n+2−2k)m}.  (5.15)

Remarks. Taking A = B = 1 in (5.6) gives Identity 55 in [2] and taking A = B = 1 in (5.1) and (5.13) gives two special cases of Identity 62 in [2]. Identities (5.3), (5.8), (5.12), and (5.15) occur as Identities (V88), (V86), (V85), and (V87), respectively, in Benjamin and Quinn [2, p. 145], which were originally given in Vajda [11], but were lacking combinatorial proofs. See also Shattuck [8] for shorter, more direct combinatorial proofs and different generalizations of these identities.

Finally, note that the m = 1 case of (5.3), (5.8), (5.12), and (5.15) is the case A = B = 1 of (5.1), (5.6), (5.9), and (5.13), respectively. The methods of this section then illustrate a way to generalize certain Fibonacci/Lucas identities. For instance, the well-known identity

F_{2n+1} = 1 + ∑_{k=1}^{n} F_{2k}  (5.16)

is easily generalized to the constant-weight identity

|1 : 2n| = B^{n} + A ∑_{k=1}^{n} B^{n−k}|1 : 2k − 1|.  (5.17)

Taking A = L, B = β in (5.17), multiplying by |2 : m|, and applying Theorem 3.4 then gives

|2 : (2n + 1)m| = β^{n}|2 : m| + L ∑_{k=1}^{n} β^{n−k}|2 : 2km|,  (5.18)

for m-periodic tilings, and, in particular,

F_{(2n+1)m} = (−1)^{(m+1)n}F_{m} + L_{m} ∑_{k=1}^{n}(−1)^{(m+1)(n−k)}F_{2km},  (5.19)

which generalizes (5.16).

References

[1] A. Benjamin, J. Quinn, and F. Su, Counting on continued fractions, Math. Mag. 73 (2000), 98–104.

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

[3] L. Carlitz, Fibonacci notes 3: q-Fibonacci numbers, Fibonacci Quart. 12 (1974), 317– 322.

[4] J. Cigler, q-Fibonacci polynomials, Fibonacci Quart. 41 (2003), 31–40.

[5] R. Graham, D. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd Edition, Addison-Wesley, 1989.

[6] R. Johnson, Matrix methods for Fibonacci and related sequences, preprint available at

http://maths.dur.ac.uk/dma0rcj/PED/fib.pdf, 2003.

[7] J. McLaughlin, Combinatorial identities deriving from the n^{th} power of a 2 × 2 matrix, Integers 4 (2004), #A19. Available from

http://www.integers-ejcnt.org/vol4.html.

[8] M. Shattuck, Tiling proofs of some Fibonacci-Lucas identities, Integers 8 (1) (2008),

#A18. Available from http://www.integers-ejcnt.org/vol8.html.

[9] M. Shattuck and C. Wagner, A new statistic on linear and circular rmino arrangements, Electron. J. Combin. 13 (2006), #R42. Available from

http://www.combinatorics.org/Volume 13/Abstracts/v13i1r42.html.

[10] R. Stanley, Enumerative Combinatorics, Vol. I, Wadsworth and Brooks/Cole, 1986.

[11] S. Vajda, Fibonacci and Lucas Numbers, and the Golden Section: Theory and Applications, John Wiley & Sons, Inc., 1989.

2000 Mathematics Subject Classification: Primary 11B39; Secondary 05A19. Keywords: continued fraction, polynomial generalization, Fibonacci number, Lucas number, tiling.

(Concerned with sequences \underline{A000032} and \underline{A000045}.)

Received January 27 2009; revised version received August 2 2009. Published in Journal of Integer Sequences, August 30 2009.

Return to Journal of Integer Sequences home page.