Tilings, Compositions, and Generalizations

Ralph P. Grimaldi Department of Mathematics Rose-Hulman Institute of Technology Terre Haute, Indiana 47803 USA

            ralph.grimaldi@rose-hulman.edu

Abstract

For n ≥ 1, let a_{n} count the number of ways one can tile a 1 × n chessboard using 1 × 1 square tiles, which come in w colors, and 1 × 2 rectangular tiles, which come in t colors. The results for a_{n} generalize the Fibonacci numbers and provide generalizations of many of the properties satisfied by the Fibonacci and Lucas numbers. We count the total number of 1 × 1 square tiles and 1 × 2 rectangular tiles that occur among the a_{n} tilings of the 1 × n chessboard. Further, for these a_{n} tilings, we also determine: (i) the number of levels, where two consecutive tiles are of the same size; (ii) the number of rises, where a 1 × 1 square tile is followed by a 1 × 2 rectangular tile; and, (iii) the number of descents, where a 1 × 2 rectangular tile is followed by a 1 × 1 square tile. Wrapping the 1 × n chessboard around so that the nth square is followed by the first square, the numbers of 1 × 1 square tiles and 1 × 2 rectangular tiles, as well as the numbers of levels, rises, and descents, are then counted for these circular tilings.

1 Determining a_{n}

For n ≥ 1, let a_{n} count the number of ways one can tile a 1×n chessboard using 1×1 square tiles, which come in w colors, and 1 × 2 rectangular tiles, which come in t colors. Then for n ≥ 2, we have

a_{n} = wa_{n−1} + ta_{n−2}, a_{0} = 1, a_{1} = w.  (1)

This follows by considering how the last square in the 1 × n chessboard is covered. If we have a 1 × 1 square tile in the nth square, then the preceding n − 1 squares can be covered in a_{n−1} ways. The coefficient w accounts for the number of different colors available for the 1 × 1 square in the nth square. Should the last square be covered (along with the (n − 1)st square) by a 1 × 2 rectangular tile, then the preceding n − 2 squares of the 1 × n chessboard can be covered in a_{n−2} ways. Here the coefficient t accounts for the number of colors available for the 1 × 2 rectangular tile covering squares n − 1 and n. (The value of a_{0} = 1 follows from this recurrence relation, since a_{2} = w^{2} + t and a_{1} = w.) If we follow the methods for solving linear recurrence relations, as set forth in [6, 7], we substitute a_{n} = Ar^{n} into this recurrence relation and arrive at the characteristic equation

r^{2} − wr − t = 0,

for which the characteristic roots are

r = \frac{w ± \sqrt{w^{2} − 4(1)(−t)}}{2} = \frac{w ± \sqrt{w^{2} + 4t}}{2}.

Throughout this work we shall assign the following symbols for these characteristic roots:

γ = \frac{w + \sqrt{w^{2} + 4t}}{2}; δ = \frac{w − \sqrt{w^{2} + 4t}}{2}.

Consequently, we may write the solution for a_{n} as

a_{n} = c_{1} γ^{n} + c_{2} δ^{n}, n ≥ 0.

From 1 = a_{0} = c_{1} + c_{2} and w = a_{1} = c_{1}γ + c_{2}δ we learn that

c_{1} = \frac{1}{2} (1 + \frac{w}{\sqrt{w^{2} + 4t}}) = \frac{1}{2} (1 + \frac{γ + δ}{γ − δ} ), and
c_{2} = \frac{1}{2} (1 − \frac{w}{\sqrt{w^{2} + 4t}}) = \frac{1}{2} (1 − \frac{γ + δ}{γ − δ} ), so
a_{n} = \frac{1}{2} (1 + \frac{γ + δ}{γ − δ} ) γ^{n} + \frac{1}{2} (1 − \frac{γ + δ}{γ − δ} ) δ^{n}
= \frac{1}{2} (\frac{2γ}{γ − δ} ) γ^{n} + \frac{1}{2} (\frac{−2δ}{γ − δ} ) δ^{n} = \frac{γ^{n+1} − δ^{n+1}}{γ − δ}, n ≥ 0.

If we define G_{n} as

G_{n} = \frac{γ^{n} − δ^{n}}{γ − δ}, n ≥ 0, then

a_{n} = G_{n+1}, for n ≥ 0  (2)

We shall refer to \frac{γ^{n}−δ^{n}}{γ−δ} as the Binet form for G_{n}. Before proceeding we observe the following:

\begin{matrix}(1) & γδ = −t \\ (2) & γ − δ = \sqrt{w^{2} + 4t} \\ (3) & γ + δ = w \\ (4) & δ < 0 and |δ| < |γ| \\ (5) & γ^{2} = wγ + t \\ (6) & δ^{2} = wδ + t \\ (7) & γ^{2} + δ^{2} = w^{2} + 2t \\ (8) & γ^{2} − δ^{2} = w \sqrt{w^{2} + 4t} \\ (9) & lim_{n→∞} \frac{G_{n+1}}{G_{n}} = γ \end{matrix}

Also, we mention the following special cases:

(1) When w = 1 and t = 1, then γ = \frac{1+\sqrt{5}}{2} = α, the golden ratio, and δ = \frac{1−\sqrt{5}}{2} = β, the negative reciprocal of α. In this case,

G_{n} = F_{n} = \frac{α^{n} − β^{n}}{α − β}, the nth Fibonacci number.  (3)

(The Fibonacci numbers are defined recursively by F_{0} = 0, F_{1} = 1, F_{n} = F_{n−1}+F_{n−2}, n ≥ 2.)

(2) When w = 1 and t = 2, then γ = \frac{1+\sqrt{9}}{2} = 2 and δ = \frac{1−\sqrt{9}}{2} = −1. In this case, G_{n+1} = J_{n} = (\frac{1}{3}) (−1)^{n} + (\frac{2}{3}) 2^{n}, the nth Jacobsthal number. (The Jacobsthal numbers are defined recursively by J_{0} = 1, J_{1} = 1, J_{n} = J_{n−1} +2 J_{n−2}, n ≥ 2; they are sequence \underline{A001045} in Sloane’s Encyclopedia.)

(3) When w = 2 and t = 1, then γ = \frac{2+\sqrt{8}}{2} = 1+\sqrt{2} and δ = \frac{2−\sqrt{8}}{2} = 1−\sqrt{2}. In this case,

G_{n} = P_{n} = \frac{γ^{n}−δ^{n}}{γ−δ} = (\frac{1}{2\sqrt{2}}) (1 + \sqrt{2})^{n} − (\frac{1}{2\sqrt{2}}) (1 − \sqrt{2})^{n}, the nth Pell number. (The Pell numbers, sometimes called the Lambda numbers, are defined recursively by P_{0} = 0, P_{1} = 1, P_{n} = 2 P_{n−1} + P_{n−2}, n ≥ 2; they are sequence \underline{A000129} in Sloane’s Encyclopedia.)

2 The Numbers of 1 × 1 and 1 × 2 Tiles among the a_{n} Tilings

For n ≥ 1, let b_{n} count the number of 1 × 1 tiles that are used in the a_{n} tilings of the 1 × n chessboard. Then b_{1} = w and b_{2} = 2w^{2}, for there are w^{2} tilings of a 1 × 2 chessboard using only 1 × 1 tiles and each such tiling has two 1 × 1 tiles. For n ≥ 3, we find that

b_{n} = wb_{n−1} + tb_{n−2} + wa_{n−1},

where (i) the summand wb_{n−1} accounts for the b_{n−1} 1 × 1 tiles we get for each of the w different 1 × 1 tiles that we can place on the nth square of the 1 × n chessboard; (ii) the summand tb_{n−2} accounts for the b_{n−2} 1 × 1 tiles we get for each of the t different 1 × 2 tiles that we can place on the (n − 1)st and nth squares of the 1 × n chessboard; and, (iii) the summand wa_{n−1} accounts for the w 1 × 1 tiles we get for each of the a_{n−1} tilings of the 1 × (n − 1) chessboard. Consequently,

b_{n} = wb_{n−1} + tb_{n−2} + w\frac{γ^{n} − δ^{n}}{γ − δ}
= wb_{n−1} + tb_{n−2} + \frac{w}{\sqrt{w^{2} + 4t}}(γ^{n} − δ^{n}), n ≥ 3.

The solution to this recurrence relation has the form

b_{n} = c_{1}γ^{n} + c_{2}δ^{n} + Anγ^{n} + Bnδ^{n}, n ≥ 1.

To determine the particular part of the solution, namely Anγ^{n} + Bnδ^{n}, substitute Anγ^{n} for b_{n} into the recurrence relation

b_{n} = wb_{n−1} + tb_{n−2} + \frac{w}{\sqrt{w^{2} + 4t}}γ^{n}.

This leads to

Anγ^{n} = wA(n − 1)γ^{n−1} + tA(n − 2)γ^{n−2} + \frac{w}{\sqrt{w^{2} + 4t}}γ^{n}.

Dividing through by γ^{n−2} we find that

Anγ^{2} = wA(n − 1)γ + tA(n − 2) + \frac{w}{\sqrt{w^{2} + 4t}}γ^{2},

from which it follows that

A = \frac{w(wγ + t)}{(wγ + 2t)\sqrt{w^{2} + 4t}} = \frac{w^{2}t + wt\sqrt{w^{2} + 4t}}{2w^{2}t + 8t^{2}}.

In a similar way we find that

B = \frac{w^{2}t − wt\sqrt{w^{2} + 4t}}{2w^{2}t + 8t^{2}}.

Consequently,

b_{n} = c_{1}γ^{n} + c_{2}δ^{n} + (\frac{w^{2}t + wt\sqrt{w^{2} + 4t}}{2w^{2}t + 8t^{2}}) nγ^{n} + (\frac{w^{2}t − wt\sqrt{w^{2} + 4t}}{2w^{2}t + 8t^{2}}) nδ^{n}.

From w = b_{1} = c_{1}γ + c_{2}δ + Aγ + Bδ and 2w^{2} = b_{2} = c_{1}γ^{2} + c_{2}δ^{2} + 2Aγ^{2} + 2Bδ^{2}, it follows that

c_{1} = \frac{2wt}{(w^{2} + 4t)^{3/2}} , c_{2} = \frac{−2wt}{(w^{2} + 4t)^{3/2}} ,

so

b_{n} = \frac{2wt}{(w^{2} + 4t)^{3/2}} (γ^{n} − δ^{n}) + (\frac{2w^{2}t + 2wt\sqrt{w^{2} + 4t}}{4w^{2}t + 16t^{2}}) n γ^{n}

+ (\frac{2w^{2}t − 2wt\sqrt{w^{2} + 4t}}{4w^{2}t + 16t^{2}}) nδ^{n}.

To simplify the form of the solution, we introduce the following idea which parallels the way the Lucas numbers, L_{n}, are given in Binet form. For α and β, as mentioned earlier in (3), we have L_{n} = α^{n} + β^{n}, for n ≥ 0. Here we define H_{n} by

H_{n} = γ^{n} + δ^{n}, n ≥ 0.  (4)

Using this definition of H_{n}, we now have

b_{n} = \frac{2wt}{w^{2} + 4t}G_{n} + \frac{w}{2}nG_{n} + \frac{w^{2}}{2 (w^{2} + 4t)}nH_{n}, n ≥ 1.  (5)

This solution can also be given for n ≥ 0 by defining b_{0} = 0.

For the case when w = t = 1, we find that b_{n} = \frac{2}{5}F_{n} + \frac{1}{2}nF_{n} + \frac{1}{10}nL_{n}, the total number of 1 × 1 square tiles used in making all of the a_{n} square-and-domino tilings of the 1 × n chessboard. Using the fact that L_{n} = F_{n−1} + F_{n+1}, for n ≥ 1, we find the following alternate way to express b_{n} in this case:

\frac{1}{10}nL_{n} + \frac{2}{5}F_{n} + \frac{1}{2}nF_{n}

= \frac{1}{10}nL_{n} + \frac{1}{10} (4F_{n} + n (5F_{n}))
= \frac{1}{10}nL_{n} + \frac{1}{10} (4F_{n} + n (F_{n−1} + 2F_{n−1} + F_{n−2} + 2F_{n−2} + 2F_{n}))
= \frac{1}{10}nL_{n} + \frac{1}{10} (n (F_{n−1} + F_{n+1} + 2F_{n−2} + 2F_{n}) + 4F_{n})
= \frac{1}{10}nL_{n} + \frac{1}{10} (n (F_{n−1} + F_{n+1}) + 2n(F_{n−2} + F_{n}) + 4F_{n})
= \frac{1}{10}nL_{n} + \frac{1}{10} (nL_{n} + 2nL_{n−1} + 2(F_{n} + F_{n−1}) + 2(F_{n} − F_{n−1}))
= \frac{1}{10}nL_{n} + \frac{1}{10} (nL_{n} + 2nL_{n−1} + 2F_{n+1} + 2F_{n−2})
= \frac{1}{10} (2nL_{n} + 2nL_{n−1} + 2F_{n+1} + 2F_{n−2})
= \frac{1}{5} (nL_{n} + nL_{n−1} + F_{n+1} + F_{n−2})
= \frac{1}{5} (nL_{n} + nL_{n−1} + (L_{n} − F_{n−1}) + (L_{n−1} − F_{n}))
= \frac{1}{5} ((n + 1) (L_{n} + L_{n−1}) − (F_{n} + F_{n−1})) = \frac{1}{5} ((n + 1) L_{n+1} − F_{n+1})

From 1 × 1 tiles, we now turn our attention to the number of 1 × 2 tiles that appear among the a_{n} tilings of the 1 × n chessboard. We denote this number by d_{n}. We see that d_{1} = 0 and d_{2} = t. For n ≥ 3 it follows that

d_{n} = wd_{n−1} + td_{n−2} + ta_{n−2},

where (i) the summand wd_{n−1} accounts for the d_{n−1} 1 × 2 tiles we get for each of the w different 1 × 1 tiles that we can place on the nth square of the 1 × n chessboard; (ii) the summand td_{n−2} accounts for the d_{n−2} 1 × 2 tiles we get for each of the t different 1 × 2 tiles that we can place on the (n − 1)st and nth squares of the 1 × n chessboard; and, (iii) the summand ta_{n−2} accounts for the t 1 × 2 tiles we get for each of the a_{n−2} tilings of the 1 × (n − 2) chessboard. Consequently,

d_{n} = wd_{n−1} + td_{n−2} + t (\frac{γ^{n−1} − δ^{n−1}}{γ − δ} )
= wd_{n−1} + td_{n−2} + \frac{t}{\sqrt{w^{2} + 4t}} (γ^{n−1} − δ^{n−1}) .

So the solution for this recurrence relation has the form

d_{n} = c_{3}γ^{n} + c_{4}δ^{n} + A_{1}nγ^{n} + B_{1}n δ^{n}.

Substituting A_{1}nγ^{n} into the recurrence relation

d_{n} = wd_{n−1} + td_{n−2} + \frac{t}{\sqrt{w^{2} + 4t}}γ^{n−1},

we obtain

A_{1}nγ^{n} = wA_{1}(n − 1)γ^{n−1} + tA_{1}(n − 2)γ^{n−2} + \frac{t}{\sqrt{w^{2} + 4t}}γ^{n−1}.

From this it follows that

(wγ + 2t)A_{1} = \frac{tγ}{\sqrt{w^{2} + 4t}}, so A_{1} = \frac{t}{w^{2} + 4t}.

A comparable calculation leads to

(wδ + 2t)B_{1} = \frac{−tδ}{\sqrt{w^{2} + 4t}} and B_{1} = \frac{t}{w^{2} + 4t}.

Consequently,

d_{n} = c_{3}γ^{n} + c_{4}δ^{n} + (\frac{t}{w^{2} + 4t}) n(γ^{n} + δ^{n}).

From 0 = d_{1} = c_{3}γ + c_{4}δ + (\frac{t}{w^{2}+4t}) (γ + δ) and t = d_{2} = c_{3}γ^{2} + c_{4} δ^{2} + (\frac{t}{w^{2}+4t}) 2(γ^{2} + δ^{2}), it follows that

c_{3} = \frac{−wt}{(w^{2} + 4t)^{3/2}} and c_{4} = \frac{wt}{(w^{2} + 4t)^{3/2}} .

Therefore, for n ≥ 1,

d_{n} = (\frac{−wt}{(w^{2} + 4t)^{3/2}} ) γ^{n} + (\frac{wt}{(w^{2} + 4t)^{3/2}} ) δ^{n} + \frac{t}{w^{2} + 4t}n (γ^{n} + δ^{n})
= \frac{−wt}{w^{2} + 4t} (\frac{γ^{n} − δ^{n}}{\sqrt{w^{2} + 4t}}) + \frac{t}{w^{2} + 4t}nH_{n}
= \frac{t}{w^{2} + 4t} (nH_{n} − wG_{n}) .  (6)

3 An Application

Before we proceed any further we should like to recognize that the preceding results on tilings can also be interpreted in terms of compositions. Our results for the tilings of a 1 × n chessboard using w different kinds of 1 × 1 square tiles and t different kinds of 1 × 2 rectangular tiles can be reinterpreted in terms of compositions of a positive integer n that use w different kinds of 1’s and t different kinds of 2’s. This idea will be used in the following.

For a positive integer n, suppose we have a 3 × n chessboard that we wish to tile with 1 × 1 square tiles and 2 × 2 square tiles. We find that if x_{n} counts the number of ways in which this can be accomplished, then

x_{n} = x_{n−1} + 2x_{n−2}, n ≥ 3, x_{1} = 1, x_{2} = 3.

This recurrence relation comes about when we consider how we can tile the last (nth) column of a 3 × n chessboard. There are x_{n−1} possibilities if the last column is tiled with three 1 × 1 square tiles, and 2x_{n−2} possibilities if the last (nth) column, along with the next-to-last (n − 1)st), are covered (i) with a 2 × 2 square tile with two 1 × 1 tiles below it, or (ii) with a 2 × 2 square tile with two 1 × 1 tiles above it. Solving this recurrence relation one finds that for n ≥ 1, x_{n} = (\frac{1}{3}) (−1)^{n} + (\frac{2}{3}) (2^{n}) = J_{n}, the nth Jacobsthal number.

To determine the number of 1×1 square tiles that occur among the x_{n} tilings, we change the problem to compositions involving one kind of 1 and two kinds of 2’s. Then we can use the results for b_{n} in (5) and d_{n} in (6) for the case where w = 1, t = 2 (and γ = 2, δ = −1). Each 1 in such a composition accounts for three 1 × 1 square tiles and each 2 accounts for two 1 × 1 square tiles. Consequently, for n ≥ 1, the number of 1 × 1 square tiles that appear among the x_{n} tilings of a 3 × n chessboard is given by

3b_{n} + 2d_{n} = 3 (\frac{2wt}{w^{2} + 4t}G_{n} + \frac{w}{2}nG_{n} + \frac{w^{2}}{2 (w^{2} + 4t)}nH_{n}) + 2 (\frac{t}{w^{2} + 4t} (nH_{n} − wG_{n}))
= 3 (\frac{4}{9}G_{n} + \frac{1}{2}nG_{n} + \frac{1}{18}n H_{n}) + \frac{4}{9}(nH_{n} − G_{n})
= \frac{8}{9}G_{n} + \frac{3}{2}nG_{n} + \frac{11}{18}nH_{n}
= \frac{8}{9} (\frac{1}{3}) (2^{n} − (−1)^{n}) + \frac{3}{2} n (\frac{1}{3}) (2^{n} − (−1)^{n}) + \frac{11}{18}n (2^{n} + (−1)^{n})
= (\frac{8 + 30n}{27}) 2^{n} − (\frac{8 − 3n}{27}) (−1)^{n}.

The number of 2 × 2 square tiles that appear among the x_{n} tilings of a 3 × n chessboard is simply

d_{n} = \frac{t}{w^{2} + 4t} (nH_{n} − wG_{n})
= \frac{2}{9} (nH_{n} − G_{n}) = \frac{2}{9}n(2^{n} + (−1)^{n}) − \frac{2}{9} (\frac{1}{3}) (2^{n} − (−1)^{n})
= (\frac{6n − 2}{27}) 2^{n} + (\frac{6n + 2}{27}) (−1)^{n}.

For n ≥ 1, the total number of tiles used for the x_{n} tilings of the 3 × n chessboard is 3b_{n} + 3d_{n} = (\frac{12n+2}{9}) 2^{n} + (\frac{3n−2}{9}) (−1)^{n}.

4 Circular Tilings

Starting with a 1 × n chessboard, suppose now that we attach the right side of the nth square to the left side of the first square, thus forming a circular chessboard where the squares maintain their locations (or, labels) as first, second, …, nth. Providing the 1 × 1 square tiles and the 1 × 2 rectangular tiles with any needed curvature, we want to count the number of ways we can tile the 1 × n circular chessboard. We let ã_{n} count the number of such tilings. Then ã_{1} = w and ã_{2} = w^{2} + 2t, where w^{2} counts the tilings that use two 1 × 1 square tiles and the coefficient 2 (in 2t) takes into account placing a 1 × 2 rectangular tile according to whether or not it covers the dividing line where the second square is now followed by the first square (on the 1 × 2 circular chessboard). For n ≥ 3, it follows that

ã_{n} = a_{n} + ta_{n−2},

where (i) a_{n} accounts for the circular tilings that result from attaching the right side of the nth square of each of the a_{n} (linear) tilings to the left side of the first square; and (ii) t a_{n−2} accounts for those circular tilings where a 1 × 2 tile is placed on squares 1 and n, leaving one of the possible a_{n−2} (linear) tilings for the squares labeled 2, 3, …, n − 1. Since a_{n} = G_{n+1}, it follows that

ã_{n} = G_{n+1} + tG_{n−1}
= (wG_{n} + tG_{n−1}) + t(wG_{n−2} + tG_{n−3})
= w(G_{n} + tG_{n−2}) + t(G_{n−1} + tG_{n−3})
= wã_{n−1} + tã_{n−2}.

Solving this recurrence relation, for which the characteristic roots are likewise γ and δ, we find that

ã_{n} = c̃_{1}γ^{n} + c̃_{2}δ^{n}.

From w = ã_{1} = c̃_{1}γ + c̃_{2} δ and w^{2} + 2t = ã_{2} = c̃_{1}γ^{2} + c̃_{2}δ^{2}, it follows that c̃_{1} = c̃_{2} = 1, so

ã_{n} = γ^{n} + δ^{n}, n ≥ 1.

In (4) we defined H_{n} = γ^{n} + δ^{n} for n ≥ 0. Consequently, ã_{n} = H_{n} for n ≥ 1, and we can define ã_{0} = H_{0} = (1/t)H_{2} − (w/t)H_{1} = (1/t)(w^{2} + 2 t) − (w/t)w = 2. Further, we now see that

H_{n} = G_{n+1} + tG_{n−1}, n ≥ 1, and
H_{n} = wH_{n−1} + tH_{n−2}, n ≥ 2.

Now let b̃_{n} count the number of 1 × 1 square tiles that appear among the ã_{n} circular tilings. Then b̃_{1} = w and b̃_{2} = 2w^{2} and

b̃_{n} = b_{n} + tb_{n−2}, n ≥ 2.

Here the summand b_{n} accounts for the 1 × 1 square tiles obtained when we take a 1 × n linear tiling and attach the right edge of the nth square with the left edge of the first square. The summand tb_{n−2} accounts for the case where we place one of the t different 1 × 2 tiles on squares n and 1, and then consider the b_{n−2} 1 × 1 square tiles that result for the a_{n−2} 1 × (n − 2) linear tilings. Using the result for b_{n} in (5), for n ≥ 2, the result for b̃_{n} can be rewritten as

b̃_{n} = \frac{2wt}{w^{2} + 4t}G_{n} + \frac{wn}{2}G_{n} + \frac{w^{2}n}{2(w^{2} + 4t)}H_{n}

+ t (\frac{2wt}{w^{2} + 4t}G_{n−2} + \frac{w(n − 2)}{2}G_{n−2} + \frac{w^{2}(n − 2)}{2(w^{2} + 4t)}H_{n−2})

= \frac{2wt}{w^{2} + 4t}H_{n−1} + \frac{wn}{2}H_{n−1} − wtG_{n−2}

+\frac{w^{2}n}{2(w^{2} + 4t)}H_{n} + \frac{w^{2}t(n − 2)}{2(w^{2} + 4t)}H_{n−2}.

Finally, let d̃_{n} count the number of 1 × 2 rectangular tiles that appear among the ã_{n} circular tilings. Here we find that d̃_{1} = 0 and d̃_{2} = 2t. With d_{0} = 0 and a_{0} = 1, for n ≥ 2 we find that

d̃_{n} = d_{n} + (d_{n−2} + a_{n−2}) t,

where d_{n} accounts for the cases where a 1 × 2 rectangular tile does not cover tiles n and 1. The summand (d_{n−2} + a_{n−2}) t is for the case where a 1 × 2 rectangular tile does cover tiles n and 1. The term d_{n−2} takes into account that for each of the t colors for a 1 × 2 tile, the remaining n − 2 tiles have d_{n−2} 1 × 2 rectangular tiles. Also, for each of the tilings of a 1 × (n − 2) chessboard we have t different colored 1 × 2 rectangular tiles covering squares n and 1.

The result for d_{n} in (6) and the result for a_{n} in (1) now provide an alternate way to express d̃_{n} for n ≥ 2 — namely,

d̃_{n} = \frac{t}{w^{2} + 4t} (nH_{n} − wG_{n}) +

(\frac{t}{w^{2} + 4t} ((n − 2)H_{n−2} − wG_{n−2}) + G_{n−1}) t.

5 Levels, Rises, and Descents for the Linear Tilings

Given a linear tiling of a 1 × n chessboard, a level is said to occur in the tiling whenever there are two consecutive tiles of the same size. (This concept, along with those of rises and descents, are studied for compositions in [1]. In [9] the concepts of levels, rises, and descents are studied for finite set partitions.)

Letting lev_{n} count the number of levels that occur for a 1×n chessboard, we find initially that lev_{1} = 0 and lev_{2} = w^{2}. Then for n ≥ 3, it follows that, with a_{−1} = 0,

lev_{n} = (wlev_{n−1} + w^{2}a_{n−2}) + (tlev_{n−2} + t^{2}a_{n−4})
= wlev_{n−1} + tlev_{n−2}

+w^{2} \frac{γ^{n−1} − δ^{n−1}}{γ − δ} + t^{2} \frac{γ^{n−3} − δ^{n−3}}{γ − δ} .

For the term (wlev_{n−1} + w^{2}a_{n−2}): (i) the summand w lev_{n−1} accounts for when one of the w 1 × 1 square tiles is placed on the nth square of the 1 × n chessboard, where there are lev_{n−1} levels on the first n − 1 squares, and (ii) the summand w^{2}a_{n−2} accounts for the w^{2} levels that occur at the (n − 1)st and nth squares of the 1 × n chessboard, for each of the possible a_{n−2} tilings of the first n − 2 squares of the 1 × n chessboard. Similarly, for the term (tlev_{n−2} + t^{2}a_{n−4}) we find that (i) the summand t lev_{n−2} deals with the situation where one of the t 1 × 2 rectangular tiles is placed on the last two squares of the 1 × n chessboard, with lev_{n−2} levels on the first n − 2 squares, and (ii) the summand t^{2}a_{n−4} accounts for t^{2} levels that occur in the last four squares of the 1 × n chessboard, for each of the a_{n−4} tilings of the first n − 4 squares of the 1 × n chessboard. Since the characteristic roots for the homogeneous part of the solution are γ and δ, the solution here has the form

lev_{n} = c_{1}γ^{n} + c_{2}δ^{n} + Anγ^{n} + Bnδ^{n}.

Substituting Anγ^{n} for lev_{n} into the recurrence relation

lev_{n} = wlev_{n−1} + tlev_{n−2} + (\frac{w^{2}}{γ − δ} ) γ^{n−1} + (\frac{t^{2}}{γ − δ} ) γ^{n−3},

we find that

Anγ^{n} = wA(n − 1)γ^{n−1} + tA(n − 2)γ^{n−2}

+ (\frac{w^{2}}{γ − δ} ) γ^{n−1} + (\frac{t^{2}}{γ − δ} ) γ^{n−3},

from which it follows that

Anγ^{3} = wA(n − 1)γ^{2} + tA(n − 2)γ + (\frac{w^{2}}{γ − δ} ) γ^{2} + (\frac{t^{2}}{γ − δ} ) .

Consequently,

wAγ^{2} + 2Atγ = \frac{w^{2}γ^{2} + t^{2}}{γ − δ},

and

A = \frac{w^{2}γ^{2} + t^{2}}{(γ − δ)(wγ^{2} + 2tγ)} = \frac{1}{2} (\frac{3w^{2} + 2t − w\sqrt{w^{2} + 4t}}{w^{2} + 4t}) .

A similar substitution — namely, Bnδ^{n} for lev_{n} — in the recurrence relation

lev_{n} = wlev_{n−1} + tlev_{n−2} − (\frac{w^{2}}{γ − δ} ) δ^{n−1} − (\frac{t^{2}}{γ − δ} ) δ^{n−3}

leads to

B = \frac{−w^{2}δ^{2} − t^{2}}{(γ − δ)(wδ^{2} + 2tδ)} = \frac{1}{2} (\frac{3w^{2} + 2t + w\sqrt{w^{2} + 4t}}{w^{2} + 4t}) .

At this point we know that

lev_{n} = c_{1}γ^{n} + c_{2}δ^{n} + Anγ^{n} + Bnδ^{n},

with A and B as above. From the relations

0 = lev_{1} = c_{1}γ + c_{2}δ + Aγ + Bδ
w^{2} = lev_{2} = c_{1}γ^{2} + c_{2}δ^{2} + 2Aγ^{2} + 2Bδ^{2},

we learn that

c_{1} = −\frac{1}{2} (1 + \frac{(w^{3} − 6wt)}{(w^{2} + 4t)^{3/2}} ) and c_{2} = −\frac{1}{2} (1 + \frac{(6wt − w^{3})}{(w^{2} + 4t)^{3/2}} ) .

Therefore,

lev_{n} = c_{1}γ^{n} + c_{2}δ^{n} + Anγ^{n} + Bnδ^{n}, n ≥ 1,  (7)

with c_{1}, c_{2}, A, and B as determined above.

Having settled the issue of levels, we now turn our attention to counting the number of rises that occur among the a_{n} tilings of the 1 × n chessboard. By a rise we mean the situation where a square 1 × 1 tile is followed by a rectangular 1 × 2 tile. We shall let rise_{n} count the number of such rises for all the a_{n} tilings of the 1 × n chessboard. Initially we find that

rise_{1} = 0, rise_{2} = 0, rise_{3} = wt, rise_{4} = 2w^{2}t.

For n ≥ 3, we have

rise_{n} = rise_{n−1}w + rise_{n−2}t + a_{n−3}wt,

where (i) the summand rise_{n−1}w accounts for the rises that occur among the tilings that have a square 1 × 1 tile on the nth square of the chessboard; (ii) the summand rise_{n−2}t accounts for the rises that occur among the tilings that have a rectangular 1 × 2 tile covering the (n − 1)st and nth squares of the chessboard; and, (iii) the summand a_{n−3}wt accounts for the additional rises that result when we place a rectangular 1 × 2 tile at the end of one of the a_{n−3} tilings of length n − 2 that ends with a square 1 × 1 tile. From (2) we know that a_{n−3} = G_{n−2} = \frac{γ^{n−2}−δ^{n−2}}{γ−δ}, so now it follows that

rise_{n} = rise_{n−1}w + rise_{n−2}t + tw (\frac{γ^{n−2} − δ^{n−2}}{γ − δ} )
= rise_{n−1}w + rise_{n−2}t + \frac{tw}{\sqrt{w^{2} + 4t}}(γ^{n−2} − δ^{n−2}), n ≥ 3,
rise_{1} = rise_{2} = 0.

In this case the particular solution has the form

A_{1}nγ^{n} + B_{1}nδ^{n}.

Substituting rise_{n} = A_{1}nγ^{n} into the nonhomogeneous recurrence relation

rise_{n} = rise_{n−1}w + rise_{n−2}t + \frac{tw}{\sqrt{w^{2} + 4t}}γ^{n−2},

we find that

A_{1}nγ^{n} = wA_{1}(n − 1)γ^{n−1} + tA_{1}(n − 2)γ^{n−2} + \frac{tw}{\sqrt{w^{2} + 4t}}γ^{n−2},

from which it follows that

A_{1}nγ^{2} = wA_{1}(n − 1)γ + tA_{1}(n − 2) + \frac{tw}{\sqrt{w^{2} + 4t}}.

Since γ^{2} − wγ − t = 0, we find that

A_{1} = \frac{tw}{(wγ + 2t)\sqrt{w^{2} + 4t}} = \frac{2tw}{(w^{2} + 4t)^{3/2} + w(w^{2} + 4t)}
= \frac{2tw}{(w^{2} + 4t)(w + \sqrt{w^{2} + 4t})} · \frac{(w + \sqrt{w^{2} − 4t})}{(w + \sqrt{w^{2} − 4t})}
= \frac{−w^{2} + w\sqrt{w^{2} + 4t}}{2(w^{2} + 4t)},

and a similar calculation leads us to

B_{1} = \frac{−tw}{(wδ + 2t)\sqrt{w^{2} + 4t}} = \frac{−2tw}{(w^{2} + 4t)^{3/2} − w(w^{2} + 4t)}
= \frac{−w^{2} − w\sqrt{w^{2} + 4t}}{2(w^{2} + 4t)}.

So at this point we have

rise_{n} = k_{1}γ^{n} + k_{2}δ^{n} + A_{1}nγ^{n} + B_{1}nδ^{n},

with A_{1}, B_{1} as above. From

0 = rise_{1} = k_{1}γ + k_{2}δ + A_{1}γ + B_{1}δ
0 = rise_{2} = k_{1}γ^{2} + k_{2}δ^{2} + 2A_{1}γ^{2} + 2B_{1}δ^{2}

we learn that

k_{1} = \frac{−2tw}{(w^{2} + 4t)^{3/2}} and k_{2} = \frac{2tw}{(w^{2} + 4t)^{3/2}} .

Consequently, for n ≥ 1,

rise_{n} = (\frac{−2tw}{(w^{2} + 4t)^{3/2}} ) γ^{n} + (\frac{2tw}{(w^{2} + 4t)^{3/2}} ) δ^{n}

+ (\frac{−w^{2} + w\sqrt{w^{2} + 4t}}{2(w^{2} + 4t)}) nγ^{n} + (\frac{−w^{2} − w\sqrt{w^{2} + 4t}}{2(w^{2} + 4t)}) nδ^{n}.  (8)

Finally, a descent occurs in a tiling when a 1 × 2 rectangular tile is followed by a 1 × 1 square tile. If the tiling is examined from right to left, we get another tiling in which a descent becomes a rise. Consequently, from this symmetry, the number of descents for the a_{n} tilings is the same as the number of rises.

6 Levels, Rises, and Descents for the Circular Tilings

In dealing with circular tilings we considered the squares on the 1 × n chessboard numbered from 1 to n, with the square numbered 1 following the square numbered n.

As above a level occurs when two tiles of the same size are next to each other on the chessboard. If we let l̃ev_{n} count the levels on the 1 × n circular chessboard, we initially find that

l̃ev_{1} = 0, l̃ev_{2} = 2w^{2}, l̃ev_{3} = 3w^{3},
l̃ev_{4} = lev_{4} + w^{2}a_{2} + t^{2} + tlev_{2}
l̃ev_{5} = lev_{5} + w^{2}a_{3} + t^{2}a_{1} + tlev_{3} + 2wt^{2}.

For n ≥ 6, we have

l̃ev_{n} = lev_{n} + w^{2}a_{n−2} + t^{2}a_{n−4} + tlev_{n−2} + 2wt^{2}a_{n−5} + 2t^{3}a_{n−6}.

The summands in this recurrence relation arise as follows:

(i) If the circular chessboard can be split where the nth square and the first square meet, then we have lev_{n} levels as in the linear case. If there is a square 1 × 1 tile on each of the nth and first squares of the circular chessboard, then there are an additional w^{2} levels for each of the possible a_{n−2} tilings — for a total of w^{2}a_{n−2} levels. Finally, if there is a rectangular 1 × 2 tile on the (n − 1)st and nth squares, and on the first and second squares, then these account for an additional t^{2}a_{n−4} levels.

(ii) Otherwise, there is a 1 × 2 rectangular tile covering the nth and first squares. Since these tiles come in t colors, there are lev_{n−2} levels for each possible color, totaling tlev_{n−2} levels. Further, if there is a square 1 × 1 tile on square n − 1 and a rectangular 1 × 2 tile on the second and third squares, then we have an additional wt^{2}a_{n−5} levels. This is also the case if there is a square 1 × 1 tile on the second square and a rectangular 1 × 2 tile on the (n − 2)nd and (n − 1)st squares — providing wt^{2}a_{n−5} more levels. Lastly, if there are rectangular 1 × 2 tiles on the (n − 2)nd and (n − 1)st squares as well as on the second and third squares, then these account for an additional 2t^{3}a_{n−6} levels.

(Note that the given recurrence relation also accounts for the cases where 1 ≤ n ≤ 5, provided we have a_{−n} = 0 for 1 ≤ n ≤ 5.)

Using the fact that a_{n} = \frac{γ^{n+1}−δ^{n+1}}{γ−δ} (from (2)) and the solution for lev_{n} (from (7)), the

above result for l̃ev_{n} can be expressed in terms of w, t, γ,and δ.

Turning now to rises for the circular tilings we find that a rise occurs if

(i) there is a 1×1 square tile on square i of the chessboard, followed by a 1×2 rectangular tile on squares i + 1, i + 2 of the chessboard, for 1 ≤ i ≤ n − 2; or,

(ii) there is a 1×1 square tile on square n of the chessboard, followed by a 1×2 rectangular tile on squares 1, 2 of the chessboard; or,

(iii) there is a 1 × 1 square tile on square n − 1 of the chessboard, followed by a 1 × 2 rectangular tile on squares n, 1 of the chessboard.

In the first case we can split the circular 1 × n chessboard between the nth and first squares and obtain rise_{n} rises. For the second case we find wta_{n−3} additional rises, and the same is true for the third case. Consequently, if we let r̃ise_{n} count the number of rises for the circular 1 × n chessboard, then we have

r̃ise_{1} = 0, r̃ise_{2} = 0, and
r̃ise_{n} = rise_{n} + 2wta_{n−3}, n ≥ 3.

This can be expressed in terms of w, t, γ,and δ by using a_{n} = \frac{γ^{n+1}−δ^{n+1}}{γ−δ} (from (2)) and the solution for rise_{n} (from (8)).

Finally, a descent occurs for the circular 1 × n chessboard if

(i) there is a 1 × 2 rectangular tile on squares i and i + 1 of the chessboard, followed by a 1 × 1 square tile on square i + 2, for 1 ≤ i ≤ n − 2; or,

(ii) there is a 1 × 2 rectangular tile on squares n − 1 and n of the chessboard, followed by a 1 × 1 square tile on square 1; or,

(iii) there is a 1 × 2 rectangular tile on squares n and 1 of the chessboard, followed by a 1 × 1 square tile on square 2 of the chessboard.

The situation here is similar to that for the number of descents on the linear 1 × n chessboard, namely — the number of descents for the circular 1 × n chessboard equals r̃ise_{n}, for n ≥ 1.

7 Further Properties of G_{n} and H_{n}

In this section we shall investigate some of the properties exhibited by G_{n} and H_{n} — analogous to those we find for the Fibonacci and Lucas numbers, which are the special cases where w = t = 1, γ = α = \frac{1+\sqrt{5}}{2}(the golden ratio), and δ = β = −\frac{1}{α}.

First we recall that the Fibonacci numbers can be expressed as sums of binomial coefficients — that is, for n ≥ 0,

F_{n} = \{ \begin{matrix}\binom{n−1}{0} + \binom{n−2}{1} + \binom{n−3}{2} + ⋯ + \binom{(n−1)/2}{(n−1)/2}, n odd \\ \binom{n−1}{0} + \binom{n−2}{1} + \binom{n−3}{2} + ⋯ + \binom{n/2}{(n/2)−1}, n even, \end{matrix}

where F_{0} = \binom{−1}{0} = 0.

Now we find that

G_{n} = \{ \begin{matrix}\binom{n−1}{0}w^{n−1} + \binom{n−2}{1}w^{n−3}t + \binom{n−3}{2}w^{n−5}t^{2} + ⋯ + \binom{(n−1)/2}{(n−1)/2}w^{0}t^{(n−1)/2}, \\ n odd \\ \binom{n−1}{0}w^{n−1} + \binom{n−2}{1}w^{n−3}t + \binom{n−3}{2}w^{n−5}t^{2} + ⋯ + \binom{n/2}{(n/2)−1}wt^{(n−2)/2}, \\ n even, \end{matrix}

where G_{0} = \binom{−1}{0} = 0. This can be established using the alternative form of the principle of mathematical induction together with the combinatorial identity \binom{m+1}{r} = \binom{m}{r} + \binom{m}{r−1}, m ≥ r ≥ 1. However, we shall provide a combinatorial proof — one comparable to those given in [3, 5].

Proof. From (2) we know that G_{n} = a_{n−1}, the number of ways we can tile a 1 × (n − 1) chessboard with 1 × 1 square tiles (of w colors) and 1 × 2 rectangular tiles (of t colors). If we tile the board with only 1×1 square tiles, then there are w^{n−1}(= \binom{n−1}{0}w^{n−1}) possible tilings. If instead we use (n − 3) 1 × 1 square tiles and one 1 × 2 rectangular tile, these (n − 2) tiles can be arranged in \frac{(n−2)!}{(n−3)!1!} = \binom{n−2}{1} ways. Taking into account the colors that are available, this case provides us with \binom{n−2}{1}w^{n−3}t more tilings of the 1×(n−1) chessboard. Continuing, for the case of (n − 5) 1 × 1 square tiles and two 1 × 2 rectangular tiles, these (n − 3) tiles can be arranged in \frac{(n−3)!}{(n−5)!2!} = \binom{n−3}{2} ways and result in \binom{n−3}{2}w^{n−5}t^{2} additional tilings.

Lastly, if n is odd, then n − 1 is even and we can tile the 1 × (n − 1) chessboard with (n − 1)/2 1 × 2 rectangular tiles. This case provides the final t^{(n−1)/2} = \binom{(n−1)/2}{(n−1)/2}w^{0}t^{(n−1)/2} tilings and completes the formula for G_{n} in the case where n is odd. On the other hand, if n is even, then n − 1 is odd and we can tile the 1 × n chessboard with one 1 × 1 square tile and ((n − 1) − 1)/2 = (n − 2)/2 = (n/2) − 1 1 × 2 rectangular tiles. These (n/2) tiles can be arranged in \frac{(n/2)!}{((n/2)−1)!1!} = \binom{n/2}{(n/2)−1} ways and provide the final \binom{n/2}{(n/2)−1}wt^{(n−2)/2} possible tilings. This then establishes the formula for G_{n} in the case where n is even.

Table 7.1 will now provide some further properties for G_{n} and H_{n}. The first column provides the corresponding property for F_{n} and L_{n}.

\begin{matrix}(7.1) & F_{n+m+1} = F_{n+1}F_{m+1} + F_{n}F_{m} & G_{n+m+1} = G_{n+1}G_{m+1} + tG_{n}G_{m} \\ (7.2) & F_{2n+1} = F_{n+1}^{2} + F_{n}^{2} & G_{2n+1} = G_{n+1}^{2} + tG_{n}^{2} \\ (7.3) & 2 L_{m+n} = 5 F_{m}F_{n} + L_{m}L_{n} & 2H_{m+n} = (w^{2} + 4t)G_{m}G_{n} + H_{m}H_{n} \\ (7.4) & ∑_{k=0}^{n} \binom{n}{k}F_{k}L_{n−k} = 2^{n}F_{n} & ∑_{k=0}^{n} \binom{n}{k}G_{k}H_{n−k} = 2^{n}G_{n} \\ (7.5) & ∑_{k=0}^{n} \binom{n}{k}F_{k} = F_{2n} & ∑_{k=0}^{n} \binom{n}{k}w^{k}t^{n−k}G_{k} = G_{2n} \\ (7.6) & ∑_{k=0}^{n} \binom{n}{k}L_{k} = L_{2n} & ∑_{k=0}^{n} \binom{n}{k}w^{k}t^{n−k}H_{k} = H_{2n} \\ (7.7) & F_{2n} = F_{n}L_{n} & G_{2n} = G_{n}H_{n} \\ (7.8) & F_{n−1} + F_{n+1} = L_{n} & tG_{n−1} + G_{n+1} = H_{n} \\ (7.9) & 2F_{n+1} = F_{n} + L_{n} & 2G_{n+1} = wG_{n} + H_{n} \\ (7.10) & 2L_{n+1} = 5F_{n} + L_{n} & 2H_{n+1} = (w^{2} + 4t)G_{n} + wH_{n} \\ (7.11) & L_{n}^{2} − 5F_{n}^{2} = 4(−1)^{n} & H_{n}^{2} − (w^{2} + 4t)G_{n}^{2} = 4(−t)^{n} \\ (7.12) & F_{m}L_{n} + F_{n}L_{m} = 2F_{m+n} & G_{m}H_{n} + G_{n}H_{m} = 2G_{m+n} \\ (7.13) & L_{n}^{2} + L_{n+1}^{2} = L_{2n} + L_{2n+2} & (\sqrt{t}H_{n})^{2} + H_{n+1}^{2} = tH_{2n} + H_{2n+2} \\ (7.14) & F_{n+1}F_{n−1} − F_{n}^{2} = (−1)^{n} & G_{n+1}G_{n−1} − G_{n}^{2} = t^{n−1}(−1)^{n} \end{matrix}

Table 7.1

We shall provide proofs for ten of these results — the other four results can be obtained by similar methods, usually employing the Binet forms for G_{n} and H_{n}. Several of the identities given in the table have combinatorial proofs that generalize those given in [3] for the case where w = t = 1.

Proof. (7.1) This result can be obtained by a combinatorial argument. We know that G_{n+m+1} counts the number of tilings of a 1 × (n + m) chessboard. For these tilings consider the two possible cases: (i) We split the tiling between the nth and (n + 1)st squares — this is possible if these squares are not covered with a 1 × 2 rectangular tile. Here, the first n squares can be covered in G_{n+1} ways, while the last m squares can be covered in G_{m+1} ways. This then provides G_{n+1}G_{m+1} tilings. (ii) Otherwise there is a 1 × 2 rectangular tile covering the nth and (n + 1)st squares of the chessboard. Here the first n − 1 squares can be tiled in G_{n} ways, while the last m − 1 squares can be tiled in G_{m} ways. Since a 1 × 2 rectangular tile comes in t colors, this case provides the remaining tG_{n}G_{m} possible tilings. Consequently,

G_{n+m+1} = G_{n+1}G_{m+1} + tG_{n}G_{m}.

(7.2) This is just a special case of (7.1), for

G_{2n+1} = G_{n+n+1} = G_{n+1}G_{n+1} + tG_{n}G_{n} = G_{n+1}^{2} + tG_{n}^{2}.

(7.4) Using the Binet forms for G_{n} and H_{n}, we find that

∑_{k=0}^{n} \binom{n}{k}G_{k}H_{n−k}

= ∑_{k=0}^{n} \binom{n}{k}\frac{γ^{k} − δ^{k}}{γ − δ} (γ^{n−k} + δ^{n−k})
= ∑_{k=0}^{n} \binom{n}{k}\frac{γ^{n} − γ^{n−k}δ^{k} + γ^{k}δ^{n−k} − δ^{n}}{γ − δ}
= ∑_{k=0}^{n} \binom{n}{k}\frac{γ^{n} − δ^{n}}{γ − δ} − ∑_{k=0}^{n} \binom{n}{k}\frac{γ^{n−k}δ^{k}}{γ − δ} + ∑_{k=0}^{n} \binom{n}{k}\frac{γ^{k}δ^{n−k}}{γ − δ}
= G_{n} ∑_{k=0}^{n} \binom{n}{k} − \frac{(γ + δ)^{n}}{γ − δ} + \frac{(γ + δ)^{n}}{γ − δ} = 2^{n}G_{n}.

(7.7) This follows readily as

G_{2n} = \frac{γ^{2n} − δ^{2n}}{γ − δ} = \frac{γ^{n} − δ^{n}}{γ − δ} (γ^{n} + δ^{n}) = G_{n}H_{n}.

(7.9) Starting with the right-hand side of the result we see that

wG_{n} + H_{n}
= w\frac{γ^{n} − δ^{n}}{γ − δ} + (γ^{n} + δ^{n})
= \frac{w (γ^{n} − δ^{n}) + (γ^{n} + δ^{n}) (γ − δ)}{γ − δ}
= \frac{(γ^{n+1} − δ^{n+1}) + (w − δ)γ^{n} − (w − γ)δ^{n}}{γ − δ}
= \frac{(γ^{n+1} − δ^{n+1}) + (γ^{n+1} − δ^{n+1})}{γ − δ} = 2G_{n+1}, since γ + δ = w.

(7.10) Again we start on the right-hand side and find that

(w^{2} + 4t)G_{n} + wH_{n}
= (γ − δ)^{2} (\frac{γ^{n} − δ^{n}}{γ − δ} ) + w (γ^{n} + δ^{n})
= (γ − δ) (γ^{n} − δ^{n}) + w (γ^{n} + δ^{n})
= (γ^{n+1} + δ^{n+1}) + γ^{n}(w − δ) + δ^{n}(w − γ)
= (γ^{n+1} + δ^{n+1}) + γ^{n}(γ) + δ^{n}(δ)
= 2 (γ^{n+1} + δ^{n+1}) = 2H_{n+1}.

(7.11) This time we start on the left-hand side.

H_{n}^{2} − (w^{2} + 4t)G_{n}^{2}
= (γ^{n} + δ^{n})^{2} − (γ − δ)^{2} (\frac{γ^{n} − δ^{n}}{γ − δ} )^{2}
= γ^{2n} + 2γ^{n}δ^{n} + δ^{2n} − (γ^{2n} − 2γ^{n}δ^{n} + δ^{2n})
= 4γ^{n}δ^{n} = 4(−t)^{n}.

(7.12) This result for F_{n} and L_{n} can be found in [4].

G_{m}H_{n} + G_{n}H_{m}
= (\frac{γ^{m} − δ^{m}}{γ − δ} ) (γ^{n} + δ^{n}) + (\frac{γ^{n} − δ^{n}}{γ − δ} ) (γ^{m} + δ^{m})
= \frac{(γ^{m+n} − δ^{m+n}) − δ^{m}γ^{n} + γ^{m}δ^{n}}{γ − δ} + \frac{(γ^{m+n} − δ^{m+n}) − δ^{n}γ^{m} + δ^{m}γ^{n}}{γ − δ}
= 2 (\frac{γ^{m+n} − δ^{m+n}}{γ − δ} ) = 2G_{m+n}.

(7.13) This result for L_{n} is found in [8].

(\sqrt{t}H_{n})^{2} + H_{n+1}^{2}
= t (γ^{n} + δ^{n})^{2} + (γ^{n+1} + δ^{n+1})^{2}
= t (γ^{2n} + 2γ^{n}δ^{n} + δ^{2n}) + (γ^{2n+2} + 2γ^{n+1}δ^{n+1} + δ^{2n+2})
= t(γ^{2n} + δ^{2n}) + 2t(−t)^{n} + (γ^{2n+2} + δ^{2n+2}) + 2(−t)^{n+1}
= tH_{2n} + H_{2n+2}.

(7.14) This result for the Fibonacci numbers was originally discovered in 1680 by the Italianborn French astronomer and mathematician Giovanni Domenico (or, Jean Dominique) Cassini (1625–1712). It was also discovered independently in 1753 by the Scottish mathematician and landscape artist Robert Simson (1687–1768).

G_{n+1}G_{n−1} − G_{n}^{2}
= (\frac{γ^{n+1} − δ^{n+1}}{γ − δ} ) (\frac{γ^{n−1} − δ^{n−1}}{γ − δ} ) − (\frac{γ^{n} − δ^{n}}{γ − δ} )^{2}
= \frac{γ^{2n} − δ^{2}(γδ)^{n−1} − γ^{2}(γδ)^{n−1} + δ^{2n} − γ^{2n} + 2(γδ)^{n} − δ^{2n}}{(γ − δ)^{2}}
= \frac{(γ^{2} + δ^{2})(−1)(γδ)^{n−1} + 2(γδ)^{n}}{(γ − δ)^{2}} = \frac{(−1)(γδ)^{n−1}(γ^{2} + δ^{2} − 2γδ)}{(γ − δ)^{2}}
= \frac{(−1)(γδ)^{n−1}(γ − δ)^{2}}{(γ − δ)^{2}} = (−1)(−t)^{n−1} = t^{n−1}(−1)^{n}.

Results (7.9), (7.10), and (7.11) will prove to be especially useful in the next section.

8 First Order Recurrence Relations for G_{n} and H_{n}

Before we start, the reader must realize that the title of this section does not contain the adjective linear. Our results will be nonlinear first order recurrence relations.

The following first order nonlinear recurrence relations for the Fibonacci and Lucas numbers can be found in [2]. They were discovered in 1963 by S. L. Basin, while at the Sylvania Electronic Systems at Mountain View, California. Using the results for the Fibonacci and Lucas numbers in (7.9)–(7.11) of Table 7.1, it was shown (using (7.9) and (7.11)) that

F_{n+1} = \frac{F_{n} + \sqrt{5F_{n}^{2} + 4(−1)^{n}}}{2} ,

while the results in (7.10) and (7.11) were used to derive

L_{n+1} = \frac{L_{n} + \sqrt{5(L_{n}^{2} − 4(−1)^{n})}}{2}.

Turning now to the results in (7.9)–(7.11) for G_{n} and H_{n} we find that

2G_{n+1} = wG_{n} + H_{n}(from (7.9))
= wG_{n} + \sqrt{(w^{2} + 4t)G_{n}^{2} + 4(−t)^{n}}(from (7.11))
So G_{n+1} = \frac{wG_{n} + \sqrt{(w^{2} + 4t)G_{n}^{2} + 4(−t)^{n}}}{2} .

Likewise, we see that

2H_{n+1} = (w^{2} + 4t)G_{n} + wH_{n}(from (7.10))
= wH_{n} + (w^{2} + 4t)\sqrt{\frac{H_{n}^{2} − 4(−t)^{n}}{w^{2} + 4t}} (from (7.11))
= wH_{n} + \sqrt{(w^{2} + 4t) (H_{n}^{2} − 4(−t)^{n})}.
So H_{n+1} = \frac{wH_{n} + \sqrt{(w^{2} + 4t) (H_{n}^{2} − 4(−t)^{n})}}{2}.

9 One Further Result

Among the many fascinating properties exhibited by the Fibonacci numbers one finds that

∑_{s_{1}+s_{2}+···+s_{k}=n k>0} s_{1}s_{2} ⋯ s_{k} = F_{2n},

where the sum is taken over all compositions of n. For example, there are 8(= 2^{3} = 2^{4−1}) compositions of 4, as exhibited in Table 9.1, where the second column contains the products of the summands that occur in each composition.

Composition of 4 Product of Summands in the Composition
4  4
3 + 1  3 · 1 = 3
2 + 2  2 · 2 = 4
2 + 1 + 1  2 · 1 · 1 = 2
1 + 3  1 · 3 = 3
1 + 2 + 1  1 · 2 · 1 = 2
1 + 1 + 2  1 · 1 · 2 = 2
1 + 1 + 1 + 1  1 · 1 · 1 · 1 = 1

Table 9.1

Here the sum of the eight products is

4 + 3 + 4 + 2 + 3 + 2 + 2 + 1 = 21 (= F_{8}), or
∑_{\begin{matrix}s_{1}+ ··· + s_{k}=4 \\ s_{i}≥1, i=1, ..., k \end{matrix}} s_{1} ⋯ s_{k} = 21 (= F_{8}).

It is also the case that F_{8} counts the number of compositions of 7, where the only summands allowed are 1’s and 2’s. (In [1] it is shown that F_{n+1} counts the number of compositions of a positive integer n, where the only summands are 1’s and 2’s.)

In order to show that

∑_{\begin{matrix}s_{1}+s_{2}+···+s_{k}=n \\ k>0 \end{matrix}} s_{1}s_{2} ⋯ s_{k} = F_{2n},

for a given positive integer n, we shall describe a method given by Ira Gessel. Consider n dots arranged in a line, where you may place at most one (separating) bar between any two consecutive dots. Now suppose that you have drawn k −1 separating bars and that you have s_{1} dots before the first bar, s_{2} dots between the first and second bars, s_{3} dots between the second and third bars, …, and s_{k} dots after the (k − 1)st bar. At this point circle one of the first s_{1} dots, one of the s_{2} dots between the first and second bars, one of the s_{3} dots between the second and third bars, …, and one of the s_{k} dots after the (k − 1)st bar. Now replace (i) each circled dot with a 1; (ii) each bar with a 1; and, (iii) each uncircled dot with a 2. The result is a composition of

(k − 1) + k + 2(n − k) = 2n − 1

where the only summands are 1’s and 2’s. Since we had s_{1} choices for the first dot, s_{2} choices for the second dot, s_{3} choices for the third dot, …, and s_{k} choices for the kth dot, this case accounts for s_{1}s_{2} ⋯ s_{k} of the compositions of 2n − 1, where the only summands are 1’s and 2’s. Furthermore, the process is reversible — that is, given a composition of 2n − 1, where the only summands are 1’s and 2’s, we determine the corresponding string of dots, circled dots, and bars that generate it, as follows: (i) Replace each 2 with an uncircled dot; (ii) Scanning the composition from left to right, replace the kth 1 by a circled dot, when k is odd, and by a bar, when k is even.

Consequently, ∑\begin{matrix}s_{1}+s_{2}+···+s_{k}=n \\ k>0 \end{matrix} s_{1}s_{2} ⋯ s_{k} counts all of the compositions of 2n − 1, where the only summands are 1’s and 2’s, so

∑_{\begin{matrix}s_{1}+s_{2}+···+s_{k}=n \\ k>0 \end{matrix}} s_{1}s_{2} ⋯ s_{k} = F_{2n}.

We now claim that for any positive integers w and t,

∑_{\begin{matrix}s_{1}+s_{2}+···+s_{k}=n \\ k>0 \end{matrix}} s_{1}s_{2} ⋯ s_{k}w^{2k−1}t^{n−k} = G_{2n} = \frac{γ^{2n} − δ^{2n}}{γ − δ}

= \frac{(\frac{w+\sqrt{w^{2}+4t}}{2})^{2n} − (\frac{w−\sqrt{w^{2}+4t}}{2})^{2n}}{\sqrt{w^{2} + 4t}} .

Once again we consider a composition of n and represent it as a string of n dots where we have placed k − 1 separating bars so that there are s_{1} dots to the left of the first bar, s_{2} dots between the first and second bars, s_{3} dots between the second and third bars, …, and s_{k} dots to the right of the (k − 1)st bar. As above, at this point circle one of the first s_{1} dots, one of the s_{2} dots between the first and second bars, one of the s_{3} dots between the second and third bars, …, and one of the s_{k} dots after the (k − 1)st bar. This time we replace each of the n − k uncircled dots with a 1 × 2 rectangular tile (which comes in t colors) and each of the k − 1 bars and each of the k circled dots with a 1 × 1 square tile (which comes in w colors). This composition of n then provides us with s_{1}s_{2} ⋯ s_{k}w^{2k−1}t^{n−k} of the tilings of a 1 × [(2k − 1) + 2(n − k)] = 1 × (2n − 1) chessboard, and, consequently,

∑\begin{matrix}s_{1}+s_{2}+···+s_{k}=n \\ k>0 \end{matrix} s_{1}s_{2} ⋯ s_{k}w^{2k−1}t^{n−k} counts all of the tilings of a 1 × (2n − 1) chessboard

using 1 × 1 square tiles (which come in w colors) and 1 × 2 rectangular tiles (which come in t colors). This is G_{2n}.

10 Acknowledgement

The author is truly grateful to the referee for the corrections that were noted and the helpful suggestions that were made. They definitely served to improve the presentation.

References

[1] K. Alladi and V. E. Hoggatt, Jr. Compositions with ones and twos. Fibonacci Quart., 13 (1975), 233–239.

[2] S. L. Basin. Problem B-42. Fibonacci Quart., 2 (1964), 329.

[3] A. T. Benjamin and J. J. Quinn. Proofs that Really Count. The Mathematical Association of America, 2003.

[4] R. Blazej. Problem B-294. Fibonacci Quart., 13 (1975), 375.

[5] R. C. Brigham, R. M. Caron, P. Z. Chinn, and R. P. Grimaldi. A tiling scheme for the Fibonacci numbers. J. Recreational Math., 28 (1996–97), 10–17.

[6] R. A. Brualdi. Introductory Combinatorics, 5th edition. Pearson Prentice Hall, 2010.

[7] R. P. Grimaldi. Discrete and Combinatorial Mathematics, 5th edition. Pearson Addison Wesley, 2004.

[8] T. Koshy. The convergence of a Lucas series. Math. Gazette, 83 (1999), 272–274.

[9] T. Mansour and A. Munagi. Enumeration of partitions by long rises, levels and descents. J. Integer Sequences, 12 (2009), Article 09.1.8.

2010 Mathematics Subject Classification: Primary 11B37; Secondary 11B39. Keywords: tilings, Fibonacci numbers, Lucas numbers, Jacobsthal numbers, levels, rises, descents, circular tilings.

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

Received August 13 2009; revised version received June 15 2010. Published in Journal of Integer Sequences, June 16 2010.

Return to Journal of Integer Sequences home page.