<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\def\lev{{\rm lev}}
\def\rise{{\rm rise}}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
\vskip 1cm{\LARGE\bf 
Tilings, Compositions, and Generalizations
}
\vskip 1cm
\large
Ralph P. Grimaldi\\
Department of Mathematics\\
Rose-Hulman Institute of Technology\\
Terre Haute, Indiana  47803\\
USA\\
\href{mailto:ralph.grimaldi@rose-hulman.edu}{\tt ralph.grimaldi@rose-hulman.edu}
\\
\end{center}

\vskip .2 in

\begin{abstract}
For $n\geq 1$, let $a_n$ count the number of ways one can
tile a $1\times n$ chessboard using $1\times 1$ square tiles, which
come in $w$ colors, and $1\times 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\times 1$
square tiles and $1\times 2$ rectangular tiles that occur among the $
a_n$ tilings of the $1\times 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\times 1$ square tile is followed by a $1\times 2$ rectangular tile;
and, (iii) the number of descents, where a $1\times 2$ rectangular tile
is followed by a $1\times 1$ square tile. Wrapping the $1\times n$ 
chessboard around so that the $n$th square is followed by the first
square, the numbers of $1\times 1$ square tiles and $1\times 2$ 
rectangular tiles, as well as the numbers of levels, rises, and descents,
are then counted for these circular tilings.
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{defin}[theorem]{Definition}
\newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}}
\newtheorem{examp}[theorem]{Example}
\newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}}
\newtheorem{rema}[theorem]{Remark}
\newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}}


\section{Determining $a_n$}

For $n\geq 1$, let $a_{n}$ count the number of ways one can
tile a $1\times n$ chessboard using $1\times 1$ square tiles, which
come in $w$ colors, and $1\times 2$ rectangular tiles, which come in
$t$ colors. Then for $n\geq 2$, we have
\begin{equation}
a_{n}=w a_{n-1}+t a_{n-2}, \ \ a_{0}=1,\ \ a_{1}=w.  \label{recrel}
\end{equation}

This follows by considering how the last square in the $1\times n$
chessboard is covered. If we have a $1\times 1$ square tile in the 
$n$th 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\times 1$  square in the  $n$th
square.  Should the last square be covered (along with the  $(n-1)$st
square) by a  $1\times 2$  rectangular tile, then the preceding $ n-2$ 
squares of the $1\times n$  chessboard can be covered in  $a_{n-2}$ 
ways.  Here the coefficient  $t$  accounts for the number of colors
available for the  $1\times 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 
\cite{Brualdi,Grimaldi}, we substitute  $a_{n}=$ $A r^{n}$  into this
recurrence relation and arrive at the characteristic equation 
\begin{equation*}
r^{2}-w r-t=0\text{,}
\end{equation*}%
for which the characteristic roots are%
\begin{equation*}
r=\frac{w\pm \sqrt{w^{2}-4(1)(-t)}}{2}=\frac{w\pm \sqrt{w^{2}+4t}}{2}.
\end{equation*}%
Throughout this work we shall assign the following symbols for these
characteristic roots:

\begin{equation*}
\gamma =\frac{w+\sqrt{w^{2}+4t}}{2}; \ \ \ \ \ \ \ \delta =\frac{w-\sqrt{%
w^{2}+4t}}{2}.
\end{equation*}

Consequently, we may write the solution for  $a_{n}$  as 
\begin{equation*}
a_{n}=c_{1}\ \gamma ^{n}+c_{2}\ \delta ^{n}\text{, \ }n\geq 0 .
\end{equation*}%
From  $1=a_{0}=c_{1}+c_{2}$  and  $w=a_{1}=c_{1} \gamma +c_{2} \delta $
 we learn that
\begin{eqnarray*}
c_{1} &amp;=&amp;\frac{1}{2}\left( 1+\frac{w}{\sqrt{w^{2}+4t}}\right) =\frac{1}{2}%
\left( 1+\frac{\gamma +\delta }{\gamma -\delta }\right) \text{, and} \\
c_{2} &amp;=&amp;\frac{1}{2}\left( 1-\frac{w}{\sqrt{w^{2}+4t}}\right) =\frac{1}{2}%
\left( 1-\frac{\gamma +\delta }{\gamma -\delta }\right) \text{, so} \\
a_{n} &amp;=&amp;\frac{1}{2}\left( 1+\frac{\gamma +\delta }{\gamma -\delta }\right)
 \gamma ^{n}+\frac{1}{2}\left( 1-\frac{\gamma +\delta }{\gamma -\delta }%
\right) \ \delta ^{n} \\
&amp;=&amp;\frac{1}{2}\left( \frac{2\gamma }{\gamma -\delta }\right) \ \gamma ^{n}+%
\frac{1}{2}\left( \frac{-2\delta }{\gamma -\delta }\right) \ \delta ^{n}=%
\frac{\gamma ^{n+1}-\delta ^{n+1}}{\gamma -\delta }\text{, \ }n\geq 0.
\end{eqnarray*}%
If we define $G_{n}$  as 
\begin{equation*}
G_{n}=\frac{\gamma ^{n}-\delta ^{n}}{\gamma -\delta }\text{, \ }n\geq 0\text{%
, then}
\end{equation*}%
\begin{equation}
a_{n}=G_{n+1}\text{, for}\ \ n\geq 0  \label{Gnp1}
\end{equation}%
We shall refer to $\ \frac{\gamma ^{n}-\delta ^{n}}{\gamma -\delta }$ \ as
the \textit{Binet} form for $G_{n}$. \ Before proceeding we observe the
following:%
\begin{equation*}
\begin{array}{cc}
(1) &amp; \ \ \ \gamma \delta =-t \\ 
(2) &amp; \ \ \gamma -\delta =\sqrt{w^{2}+4t} \\ 
(3) &amp; \ \gamma +\delta =\ w \\ 
(4) &amp; \ \ \ \ \delta &lt;0\ \ \text{and \ }\left\vert \delta \right\vert
&lt;\left\vert \gamma \right\vert \\ 
(5) &amp; \ \ \gamma ^{2}=w\gamma +t \\ 
(6) &amp; \ \delta ^{2}=w\delta +t \\ 
(7) &amp; \ \ \gamma ^{2}+\delta ^{2}=w^{2}+2t \\ 
(8) &amp; \ \gamma ^{2}-\delta ^{2}=w\ \sqrt{w^{2}+4t} \\ 
(9) &amp; \lim_{n\rightarrow \infty }\frac{G_{n+1}}{G_{n}}=\gamma%
\end{array}%
\end{equation*}%
Also, we mention the following special cases:

(1)  When  $w=1$  and  $t=1$, then  $\gamma =\frac{1+\sqrt{5}}{2}%
=\alpha $, the golden ratio, and  $\delta =\frac{1-\sqrt{5}}{2}=\beta $,
the negative reciprocal of  $\alpha $.  In this case, 
\begin{equation}
G_{n}=F_{n}=\frac{\alpha ^{n}-\beta ^{n}}{\alpha -\beta }\text{,}\ \text{the
\ }n\text{th Fibonacci number.}  \label{Fib}
\end{equation}%
(The Fibonacci numbers are defined recursively by  $F_{0}=0, F_{1}=1,\
F_{n}=F_{n-1}+F_{n-2},\ n\geq 2$.)

(2) When  $w=1$  and  $t=2$, then  $\gamma =\frac{1+\sqrt{9}}{2}=2$
 and $\delta =$ $\frac{1-\sqrt{9}}{2}=-1$. In this case, 
$G_{n+1}=J_{n}=\left( \frac{1}{3}\right) (-1)^{n}+\left( \frac{2}{3}\right)
2^{n}$, the $n$th 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\geq 2$;
they are sequence \seqnum{A001045} in Sloane's {\it Encyclopedia}.)

(3) When $w=2$ and $t=1$, then $\gamma =\frac{2+\sqrt{8}}{2}=1+
\sqrt{2}$  and $\delta =$ $\frac{2-\sqrt{8}}{2}=1-\sqrt{2}$.  In this
case, $G_{n}=P_{n}=\frac{\gamma ^{n}-\delta ^{n}}{\gamma -\delta }=\left( 
\frac{1}{2\sqrt{2}}\right) \left( 1+\sqrt{2}\right) ^{n}-\left( \frac{1}{2%
\sqrt{2}}\right) \left( 1-\sqrt{2}\right) ^{n}$, the $n$th 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\geq 2$;
they are sequence \seqnum{A000129} in Sloane's {\it Encyclopedia}.)


\section{The Numbers of ${1\times 1}$ and ${1\times 2}$ Tiles among the 
$a_n$ Tilings}


For $n\geq 1$, let $b_{n}$ count the number of $1\times 1$ tiles
that are used in the $a_{n}$ tilings of the $1\times n$ chessboard.
Then $b_{1}=w$ $\ $and$\ b_{2}=2 w^{2}$, for there are $w^{2}$ 
tilings of a $1\times 2$ chessboard using only $1\times 1$ tiles and
each such tiling has two $1\times 1$ tiles. For $n\geq 3$, we find
that 
\begin{equation*}
b_{n}=w b_{n-1}+t b_{n-2}+w a_{n-1}\text{,}
\end{equation*}%
where (i)  the summand $w b_{n-1}$  accounts for the $b_{n-1}
$  $1\times 1$  tiles we get for each of the  $w$  different  $1\times 1
$  tiles that we can place on the  $n$th square of the  $1\times n$ 
chessboard; (ii)  the summand  $t b_{n-2}$  accounts for the $
b_{n-2}$  $1\times 1$  tiles we get for each of the  $t$  different 
$1\times 2$  tiles that we can place on the  $(n-1)$st and $n$th squares
of the  $1\times n$  chessboard; and, (iii)  the summand  $w a_{n-1}$ 
accounts for the  $w$ $1\times 1$  tiles we get for each of the  $
a_{n-1}$  tilings of the  $1\times (n-1)$  chessboard. Consequently,
\begin{eqnarray*}
b_{n} &amp;=&amp;w b_{n-1}+t b_{n-2}+w \frac{\gamma ^{n}-\delta ^{n}}{\gamma
-\delta } \\
&amp;=&amp;w b_{n-1}+t b_{n-2}+\frac{w}{\sqrt{w^{2}+4t}} (\gamma ^{n}-\delta
^{n}),\ n\geq 3.
\end{eqnarray*}%
The solution to this recurrence relation has the form 
\begin{equation*}
b_{n}=c_{1} \gamma ^{n}+c_{2} \delta ^{n}+A n \gamma ^{n}+B n \delta
^{n}, n\geq 1.
\end{equation*}%
To determine the particular part of the solution, namely  $A n \gamma
^{n}+B n \delta ^{n}$, substitute $A n \gamma ^{n}$  for  $b_{n}$ \
into the recurrence relation%
\begin{equation*}
b_{n}=w b_{n-1}+t b_{n-2}+\frac{w}{\sqrt{w^{2}+4t}} \gamma ^{n}.
\end{equation*}%
This leads to 
\begin{equation*}
A n \gamma ^{n}=w A (n-1) \gamma ^{n-1}+t A (n-2) \gamma ^{n-2}+%
\frac{w}{\sqrt{w^{2}+4t}} \gamma ^{n}.
\end{equation*}%
Dividing through by  $\gamma ^{n-2}$  we find that 
\begin{equation*}
A n \gamma ^{2}=w A (n-1) \gamma +t A (n-2)+\frac{w}{\sqrt{w^{2}+4t}}%
 \gamma ^{2},
\end{equation*}%
from which it follows that 
\begin{equation*}
A=\frac{w(w \gamma +t)}{(w \gamma +2t)\sqrt{w^{2}+4t}}=\frac{w^{2}t+wt%
\sqrt{w^{2}+4t}}{2 w^{2}t+8 t^{2}}.
\end{equation*}%
In a similar way we find that 
\begin{equation*}
B=\frac{w^{2}t-wt\sqrt{w^{2}+4t}}{2 w^{2}t+8 t^{2}}.
\end{equation*}%
Consequently, 
\begin{equation*}
b_{n}=c_{1} \gamma ^{n}+c_{2} \delta ^{n}+\left( \frac{w^{2}t+wt\sqrt{%
w^{2}+4t}}{2 w^{2}t+8 t^{2}}\right) n \gamma ^{n}+\left( \frac{w^{2}t-wt%
\sqrt{w^{2}+4t}}{2 w^{2}t+8 t^{2}}\right) n \delta ^{n}.
\end{equation*}%
From  $w=b_{1}=c_{1} \gamma +c_{2} \delta +A \gamma +B \delta $  and  
$2 w^{2}=b_{2}=$ $c_{1} \gamma ^{2}+c_{2} \delta ^{2}+2 A \gamma
^{2}+2 B \delta ^{2}$, it follows that%
\begin{equation*}
c_{1}=\frac{2 wt}{(w^{2}+4t)^{3/2}},\ \  c_{2}=\frac{-2 wt}{(w^{2}+4t)^{3/2}%
},
\end{equation*}%
so%
\begin{eqnarray*}
b_{n} &amp;=&amp;\frac{2 wt}{(w^{2}+4t)^{3/2}}\left( \gamma ^{n}-\delta ^{n}\right)
+\left( \frac{2 w^{2}t+2 wt\sqrt{w^{2}+4t}}{4 w^{2}t+16 t^{2}}\right) n\
\gamma ^{n} \\
&amp;&amp;+\left( \frac{2 w^{2}t-2 wt\sqrt{w^{2}+4t}}{4 w^{2}t+16 t^{2}}\right)
n \delta ^{n}.
\end{eqnarray*}%
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
 $\alpha $  and  $\beta $, as mentioned earlier in  (\ref{Fib}), we have
 $L_{n}=\alpha ^{n}+\beta ^{n},$ for  $n\geq 0$.  Here we define  $H_{n}$
 by%
\begin{equation}
H_{n}=\gamma ^{n}+\delta ^{n},\ n\geq 0.  \label{Hn}
\end{equation}%
Using this definition of  $H_{n},$ we now have%
\begin{equation}
b_{n}=\frac{2 wt}{w^{2}+4t} G_{n}+\frac{w}{2 } n G_{n}+\frac{w^{2}}{2\
\left( w^{2}+4t\right) } n H_{n},\ n\geq 1.  \label{bn}
\end{equation}%
This solution can also be given for  $n\geq 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\times 1$  square
tiles used in making all of the $a_{n}$  square-and-domino tilings of the $%
1\times n$  chessboard.  Using the fact that  $L_{n}=F_{n-1}+F_{n+1}$,
for  $n\geq 1$, we find the following alternate way to express  $b_{n}$ \
in this case:%
\begin{eqnarray*}
&amp;&amp;\frac{1}{10}nL_{n}+\frac{2}{5}F_{n}+\frac{1}{2}nF_{n} \\
&amp;=&amp;\frac{1}{10}nL_{n}+ \frac{1}{10} \left( 4F_{n}+n\left(
5F_{n}\right) \right) \\
&amp;=&amp;\frac{1}{10}nL_{n}+ \frac{1}{10} \left( 4F_{n}+n\left(
F_{n-1}+2F_{n-1}+F_{n-2}+2F_{n-2}+2F_{n}\right) \right) \\
&amp;=&amp;\frac{1}{10}nL_{n}+ \frac{1}{10} \left( n\left(
F_{n-1}+F_{n+1}+2F_{n-2}+2F_{n}\right) +4F_{n}\right) \\
&amp;=&amp;\frac{1}{10}nL_{n}+ \frac{1}{10} \left( n\left(
F_{n-1}+F_{n+1}\right) +2n(F_{n-2}+F_{n})+4F_{n}\right) \\
&amp;=&amp;\frac{1}{10}nL_{n}+ \frac{1}{10} \left(
nL_{n}+2nL_{n-1}+2(F_{n}+F_{n-1})+2(F_{n}-F_{n-1})\right) \\
&amp;=&amp;\frac{1}{10}nL_{n}+ \frac{1}{10} \left(
nL_{n}+2nL_{n-1}+2F_{n+1}+2F_{n-2}\right) \\
&amp;=&amp; \frac{1}{10} \left( 2nL_{n}+2nL_{n-1}+2F_{n+1}+2F_{n-2}%
\right) \\
&amp;=&amp; \frac{1}{5} \left( nL_{n}+nL_{n-1}+F_{n+1}+F_{n-2}\right) \\
&amp;=&amp; \frac{1}{5} \left(
nL_{n}+nL_{n-1}+(L_{n}-F_{n-1})+(L_{n-1}-F_{n})\right) \\
&amp;=&amp; \frac{1}{5} \left( \left( n+1\right) \left(
L_{n}+L_{n-1}\right) -\left( F_{n}+F_{n-1}\right) \right) = \frac{1}{5}
 \left( \left( n+1\right) L_{n+1}-F_{n+1}\right)
\end{eqnarray*}


From  $1\times 1$  tiles, we now turn our attention to the number of  $%
1\times 2$  tiles that appear among the  $a_{n}$  tilings of the  $%
1\times n$  chessboard.  We denote this number by  $d_{n}$.  We see that
 $d_{1}=0$  and  $d_{2}=t$.  For  $n\geq 3$  it follows that 
\begin{equation*}
d_{n}=w d_{n-1}+t d_{n-2}+t a_{n-2}\text{,}
\end{equation*}%
where (i)  the summand  $w d_{n-1}$  accounts for the $
d_{n-1} $  $1\times 2$  tiles we get for each of the  $w$  different $
1\times 1 $  tiles that we can place on the  $n$th square of the $
1\times n$  chessboard; (ii)  the summand  $t d_{n-2}$  accounts for
the 
$d_{n-2}$ \ $1\times 2$  tiles we get for each of the  $t$
 different  $1\times 2$  tiles that we can place on the  $(n-1)$st and 
$n$th squares of the  $1\times n$  chessboard; and, (iii)  the summand  
$t a_{n-2}$  accounts for the  $t$  $1\times 2$  tiles we get for each
of the  $a_{n-2}$  tilings of the  $1\times (n-2)$  chessboard. 
Consequently,%
\begin{eqnarray*}
d_{n} &amp;=&amp;w d_{n-1}+t d_{n-2}+t\left( \frac{\gamma ^{n-1}-\delta ^{n-1}}{%
\gamma -\delta }\right) \\
&amp;=&amp;w d_{n-1}+t d_{n-2}+\frac{t}{\sqrt{w^{2}+4t}}\left( \gamma
^{n-1}-\delta ^{n-1}\right) .
\end{eqnarray*}%
So the solution for this recurrence relation has the form 
\begin{equation*}
d_{n}=c_{3} \gamma ^{n}+c_{4} \delta ^{n}+A_{1} n \gamma ^{n}+B_{1} n\
\delta ^{n}.
\end{equation*}%
Substituting  $A_{1} n \gamma ^{n}$  into the recurrence relation%
\begin{equation*}
d_{n}=w d_{n-1}+t d_{n-2}+\frac{t}{\sqrt{w^{2}+4t}}\gamma ^{n-1},
\end{equation*}%
we obtain 
\begin{equation*}
A_{1} n \gamma ^{n}=w A_{1} (n-1) \gamma ^{n-1}+t A_{1} (n-2) \gamma
^{n-2}+\frac{t}{\sqrt{w^{2}+4t}}\gamma ^{n-1}.
\end{equation*}%
From this it follows that%
\begin{equation*}
(w \gamma +2 t) A_{1}=\frac{t \gamma }{\sqrt{w^{2}+4t}}\text{, so  }%
A_{1}=\frac{t}{w^{2}+4t}.
\end{equation*}%
A comparable calculation leads to 
\begin{equation*}
(w \delta +2 t) B_{1}=\frac{-t \delta }{\sqrt{w^{2}+4t}}\text{  and  }%
B_{1}=\frac{t}{w^{2}+4t}.
\end{equation*}%
Consequently, 
\begin{equation*}
d_{n}=c_{3} \gamma ^{n}+c_{4} \delta ^{n}+\left( \frac{t }{w^{2}+4t}%
\right)  n (\gamma ^{n}+\delta ^{n}).
\end{equation*}%
From  $0=d_{1}=$ $c_{3} \gamma +c_{4} \delta +\left( \frac{t }{w^{2}+4t}%
\right)  (\gamma +\delta )$  and  $t=d_{2}=$ $c_{3} \gamma ^{2}+c_{4}\
\delta ^{2}+\left( \frac{t }{w^{2}+4t}\right)  2 (\gamma ^{2}+\delta
^{2}) $, it follows that%
\begin{equation*}
c_{3}=\frac{-w t}{(w^{2}+4t)^{3/2}}\text{ \ and\  }c_{4}=\frac{w t}{%
(w^{2}+4t)^{3/2}}.
\end{equation*}%
Therefore, for  $n\geq 1$, 
\begin{eqnarray}
d_{n} &amp;=&amp;\left( \frac{-w t}{(w^{2}+4t)^{3/2}}\right) \gamma ^{n}+\left( 
\frac{w t}{(w^{2}+4t)^{3/2}}\right) \delta ^{n}+\frac{t}{w^{2}+4t} n\
(\gamma ^{n}+\delta ^{n})  \notag \\
&amp;=&amp;\frac{-w t}{w^{2}+4t}\left( \frac{\gamma ^{n}-\delta ^{n}}{\sqrt{w^{2}+4t%
}}\right) +\frac{t}{w^{2}+4t} n H_{n}  \notag \\
&amp;=&amp;\frac{t}{w^{2}+4t}\left( n H_{n}-w G_{n}\right) .  \label{dn}
\end{eqnarray}

\section{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\times n$  chessboard using  $w$ \
different kinds of  $1\times 1$  square tiles and  $t$  different kinds
of  $1\times 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\times n$  chessboard
that we wish to tile with  $1\times 1$  square tiles and  $2\times 2$ 
square tiles.  We find that if  $x_{n}$  counts the number of ways in
which this can be accomplished, then%
\begin{equation*}
x_{n}=x_{n-1}+2 x_{n-2}, \ n\geq 3,\ \ x_{1}=1,\ \ x_{2}=3.
\end{equation*}%
This recurrence relation comes about when we consider how we can tile the
last ($n$th) column of a  $3\times n$  chessboard.  There are  $x_{n-1}$
 possibilities if the last column is tiled with three  $1\times 1$ \
square tiles, and  $2 x_{n-2}$  possibilities if the last ($n$th) column,
along with the next-to-last ($n-1$)st), are covered (i)  with a  $2\times
2$  square tile with two  $1\times 1$  tiles below it, or (ii)  with a  
$2\times 2$  square tile with two  $1\times 1$  tiles above it.  Solving
this recurrence relation one finds that for  $n\geq 1$, $x_{n}=\left( \frac{%
1}{3}\right) (-1)^{n}+\left( \frac{2}{3}\right) (2^{n})=J_{n}$, the  $n$th
Jacobsthal number.

To determine the number of  $1\times 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 (\ref{bn})  and  $d_{n}$  in (\ref{dn})  for the case
where  $w=1$, $t=2$  (and  $\gamma =2, \delta =-1$).  Each  $1$  in
such a composition accounts for three  $1\times 1$  square tiles and each
 $2$  accounts for two  $1\times 1$  square tiles.  Consequently, for  
$n\geq 1$, the number of  $1\times 1$  square tiles that appear among the
 $x_{n}$  tilings of a  $3\times n$  chessboard is given by
\begin{eqnarray*}
3 b_{n}+2 d_{n} 
&amp;=&amp;3\left( \frac{2 wt}{w^{2}+4t} G_{n}+\frac{w}{2 } n G_{n}+\frac{w^{2}
}{2 \left( w^{2}+4t\right) } n H_{n}\right) 
+2\left( \frac{t}{w^{2}+4t}\left( n H_{n}-w G_{n}\right) \right) \\
&amp;=&amp;3\left( \frac{4}{9} G_{n}+\frac{1}{2} n G_{n}+\frac{1}{18} n\
H_{n}\right) +\frac{4}{9}(n H_{n}-G_{n}) \\
&amp;=&amp;\frac{8}{9} G_{n}+\frac{3}{2} n G_{n}+\frac{11}{18} n H_{n} \\
&amp;=&amp;\frac{8}{9}\left( \frac{1}{3}\right) (2^{n}-(-1)^{n})+\frac{3}{2}\
n\left( \frac{1}{3}\right)  (2^{n}-(-1)^{n})+\frac{11}{18} n\
(2^{n}+(-1)^{n}) \\
&amp;=&amp;\left( \frac{8+30n}{27}\right)  2^{n}-\left( \frac{8-3n}{27}\right) 
(-1)^{n}.
\end{eqnarray*}%
The number of  $2\times 2$  square tiles that appear among the  $x_{n}$ 
tilings of a  $3\times n$  chessboard is simply%
\begin{eqnarray*}
d_{n} &amp;=&amp;\frac{t}{w^{2}+4t}\left( n H_{n}-w G_{n}\right) \\
&amp;=&amp;\frac{2}{9}\left( n H_{n}-G_{n}\right) =\frac{2}{9} n (2^{n}+(-1)^{n})-
\frac{2}{9}\left( \frac{1}{3}\right)  (2^{n}-(-1)^{n}) \\
&amp;=&amp;\left( \frac{6n-2}{27}\right)  2^{n}+\left( \frac{6n+2}{27}\right) \
(-1)^{n}. 
\end{eqnarray*}%
For  $n\geq 1$, the total number of tiles used for the  $x_{n}$  tilings
of the  $3\times n$  chessboard is $ 3 b_{n}+3 d_{n}=\left( \frac{12n+2%
}{9}\right)  2^{n}+\left( \frac{3n-2}{9}\right)  (-1)^{n}$. 

\section{Circular Tilings}

Starting with a  $1\times n$  chessboard, suppose now that we attach the
right side of the  $n$th 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, $\ldots$, $n$th.  Providing the  $1\times 1$ \
square tiles and the  $1\times 2$  rectangular tiles with any needed
curvature, we want to count the number of ways we can tile the  $1\times n$
 circular chessboard.  We let  $\widetilde{a_{n}}$  count the number of
such tilings.  Then  $\widetilde{a_{1}}=w$  and  $\widetilde{a_{2}}%
=w^{2}+2t,$ where  $w^{2}  $ counts the tilings that use two  $1\times 1$
 square tiles and the coefficient  $2$ (in $ 2t$)  takes into account
placing a  $1\times 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\times 2$ circular chessboard).  For  $n\geq 3$%
, it follows that%
\begin{equation*}
\widetilde{a_{n}}=a_{n}+t a_{n-2}\text{,}
\end{equation*}%
where (i)  $a_{n}$  accounts for the circular tilings that result from
attaching the right side of the  $n$th 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\times 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, \ldots,  n-1$. 
Since  $a_{n}=G_{n+1}$, it follows that 
\begin{eqnarray*}
\widetilde{a_{n}} &amp;=&amp;G_{n+1}+t G_{n-1} \\
&amp;=&amp;(w G_{n}+t G_{n-1})+t(w G_{n-2}+t G_{n-3}) \\
&amp;=&amp;w(G_{n}+t G_{n-2})+t(G_{n-1}+t G_{n-3}) \\
&amp;=&amp;w \widetilde{a_{n-1}}+t \widetilde{a_{n-2}}.
\end{eqnarray*}%
Solving this recurrence relation, for which the characteristic roots are
likewise  $\gamma   $ and  $\delta $, we find that 
\begin{equation*}
\widetilde{a_{n}}=\widetilde{c_{1}} \gamma ^{n}+\widetilde{c_{2}} \delta
^{n}.
\end{equation*}%
From  $w=$ $\widetilde{a_{1}}=\widetilde{c_{1}} \gamma +\widetilde{c_{2}}\
\delta $  and  $w^{2}+2t=\widetilde{a_{2}}=\widetilde{c_{1}} \gamma ^{2}+%
\widetilde{c_{2}} \delta ^{2}$, it follows that  $\widetilde{c_{1}}=%
\widetilde{c_{2}}=1$, so%
\begin{equation*}
\widetilde{a_{n}}= \gamma ^{n}+\delta ^{n} , n\geq 1.
\end{equation*}%
In (\ref{Hn}) we defined  $H_{n}= \gamma ^{n}+\delta ^{n}$  for  $n\geq
0 $.  Consequently, $\widetilde{a_{n}}=H_{n}$  for  $n\geq 1$, and we can
define  $\widetilde{a_{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  
\begin{eqnarray*}
H_{n} &amp;=&amp;G_{n+1}+t G_{n-1}\text{, }n\geq 1\text{, and} \\
H_{n} &amp;=&amp;w H_{n-1}+t H_{n-2}\text{, }n\geq 2.
\end{eqnarray*}

Now let  $\widetilde{b_{n}}$  count the number of  $1\times 1$  square
tiles that appear among the  $\widetilde{a_{n}}$  circular tilings.  Then
 $\widetilde{b_{1}}=w$  and  $\widetilde{b_{2}}=2 w^{2}$  and  
\begin{equation*}
\widetilde{b_{n}}=b_{n}+t b_{n-2}, n\geq 2.
\end{equation*}%
Here the summand  $b_{n}$  accounts for the  $1\times 1$  square tiles
obtained when we take a  $1\times n$  linear tiling and attach the right
edge of the  $n$th square with the left edge of the first square.  The
summand  $t b_{n-2}$  accounts for the case where we place one of the  $%
t $  different  $1\times 2  $ tiles on squares  $n$  and  $1$, and
then consider the  $b_{n-2}$  $1\times 1$  square tiles that result for
the  $a_{n-2}$  $1\times (n-2)$  linear tilings.  Using the result for  
$b_{n}$  in (\ref{bn}), for  $n\geq 2$, the result for  $\widetilde{b_{n}}
$  can be rewritten as%
\begin{eqnarray*}
\widetilde{b_{n}} &amp;=&amp;\frac{2 wt}{w^{2}+4t}G_{n}+\frac{wn}{2}G_{n}+\frac{%
w^{2}n}{2(w^{2}+4t)}H_{n} \\
&amp;&amp;+\ t\left( \frac{2 wt}{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}\right) \\
&amp;=&amp;\frac{2 wt}{w^{2}+4t}H_{n-1}+\frac{wn}{2}H_{n-1}-wtG_{n-2} \\
&amp;&amp;+\frac{w^{2}n}{2(w^{2}+4t)}H_{n}+\frac{w^{2}t(n-2)}{2(w^{2}+4t)}H_{n-2}%
.
\end{eqnarray*}%
 

Finally, let  $\widetilde{d_{n}}$  count the number of  $1\times 2$ \
rectangular tiles that appear among the  $\widetilde{a_{n}}$  circular
tilings.  Here we find that  $\widetilde{d_{1}}=0$  and  $\widetilde{%
d_{2}}=2t$.  With  $d_{0}=0$  and  $a_{0}=1$, for  $n\geq 2$  we find
that 
\begin{equation*}
\widetilde{d_{n}}=d_{n}+\left( d_{n-2}+a_{n-2}\right) t\text{,}
\end{equation*}%
where  $d_{n}$  accounts for the cases where a  $1\times 2$  rectangular
tile does \textit{not }cover tiles  $n$  and  $1$.  The summand  $%
\left( d_{n-2}+a_{n-2}\right) t$  is for the case where a  $1\times 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\times 2$
 tile, the remaining  $n-2$  tiles have  $d_{n-2}$  $1\times 2$ \
rectangular tiles.  Also, for each of the tilings of a  $1\times (n-2)$ \
chessboard we have  $t$  different colored  $1\times 2$  rectangular
tiles covering squares  $n$  and  $1$.  

The result for  $d_{n}$  in (\ref{dn})  and the result for  $a_{n}$  in
 (\ref{recrel})  now provide an alternate way to express  $\widetilde{%
d_{n}}$  for  $n\geq 2$ --- namely,  
\begin{eqnarray*}
\widetilde{d_{n}} &amp;=&amp;\frac{t}{w^{2}+4t}\left( nH_{n}-wG_{n}\right) + \\
&amp;&amp;\left( \frac{t}{w^{2}+4t}\left( (n-2)H_{n-2}-wG_{n-2}\right)
+G_{n-1}\right) t .
\end{eqnarray*}

\section{Levels, Rises, and Descents for the Linear Tilings}

Given a linear tiling of a  $1\times n$  chessboard, a \textit{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 \cite{Alladi}.  In \cite{Mansour} 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\times
n$  chessboard, we find initially that  $\lev_{1}=0$  and  $\lev_{2}=w^{2}$%
.  Then for  $n\geq 3$, it follows that, with  $a_{-1}=0$,  
\begin{eqnarray*}
\lev_{n} &amp;=&amp;(w \lev_{n-1}+w^{2}a_{n-2})+(t \lev_{n-2}+t^{2}a_{n-4}) \\
&amp;=&amp;w \lev_{n-1}+t \lev_{n-2} \\
&amp;&amp;+w^{2}\frac{\gamma ^{n-1}-\delta ^{n-1}}{\gamma -\delta }+t^{2}\frac{%
\gamma ^{n-3}-\delta ^{n-3}}{\gamma -\delta }.
\end{eqnarray*}%
For the term $ (w \lev_{n-1}+w^{2}a_{n-2})$:  (i) the summand  $w\
\lev_{n-1}$  accounts for when one of the  $w$  $1\times 1$  square tiles
is placed on the  $n$th square of the  $1\times 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  $n$th squares of the  $1\times n$ \
chessboard, for each of the possible  $a_{n-2}$  tilings of the first  $%
n-2$  squares of the  $1\times n$  chessboard.  Similarly, for the term
 $(t \lev_{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\times 2$ \
rectangular tiles is placed on the last two squares of the  $1\times 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\times n$  chessboard, for each
of the  $a_{n-4}$  tilings of the first  $n-4$  squares of the  $%
1\times n$  chessboard.  Since the characteristic roots for the
homogeneous part of the solution are  $\gamma   $ and  $\delta $, the
solution here has the form%
\begin{equation*}
\lev_{n}=c_{1}\gamma ^{n}+c_{2}\delta ^{n}+An\gamma ^{n}+Bn\delta ^{n}.
\end{equation*}%
Substituting   $An\gamma ^{n}$  for  $\lev_{n}$  into the recurrence
relation  
\begin{equation*}
\lev_{n}=w \lev_{n-1}+t \lev_{n-2}+\left( \frac{w^{2}}{\gamma -\delta }%
\right) \gamma ^{n-1}+\left( \frac{t^{2}}{\gamma -\delta }\right) \gamma
^{n-3}\text{,}
\end{equation*}%
we find that%
\begin{eqnarray*}
An\gamma ^{n} &amp;=&amp;wA(n-1)\gamma ^{n-1}+tA(n-2)\gamma ^{n-2} \\
&amp;&amp;+\left( \frac{w^{2}}{\gamma -\delta }\right) \gamma ^{n-1}+\left( \frac{%
t^{2}}{\gamma -\delta }\right) \gamma ^{n-3}\text{,}
\end{eqnarray*}%
from which it follows that%
\begin{equation*}
An\gamma ^{3}=wA(n-1)\gamma ^{2}+tA(n-2)\gamma +\left( \frac{w^{2}}{\gamma
-\delta }\right) \gamma ^{2}+\left( \frac{t^{2}}{\gamma -\delta }\right) 
.
\end{equation*}%
Consequently,%
\begin{equation*}
wA\gamma ^{2}+2At\gamma =\frac{w^{2}\gamma ^{2}+t^{2}}{\gamma -\delta }\text{%
,}
\end{equation*}%
and%
\begin{equation*}
A=\frac{w^{2}\gamma ^{2}+t^{2}}{(\gamma -\delta )(w\gamma ^{2}+2t\gamma )}=%
\frac{1}{2}\left( \frac{3w^{2}+2t-w\sqrt{w^{2}+4t}}{w^{2}+4t}\right) .
\end{equation*}%
A similar substitution --- namely,  $Bn\delta ^{n}$  for  $\lev_{n}$ ---
in the recurrence relation%
\begin{equation*}
\lev_{n}=w \lev_{n-1}+t \lev_{n-2}-\left( \frac{w^{2}}{\gamma -\delta }%
\right) \delta ^{n-1}-\left( \frac{t^{2}}{\gamma -\delta }\right) \delta
^{n-3}
\end{equation*}%
leads to 
\begin{equation*}
B=\frac{-w^{2}\delta ^{2}-t^{2}}{(\gamma -\delta )(w\delta ^{2}+2t\delta )}=%
\frac{1}{2}\left( \frac{3w^{2}+2t+w\sqrt{w^{2}+4t}}{w^{2}+4t}\right) .
\end{equation*}

At this point we know that%
\begin{equation*}
\lev_{n}=c_{1}\gamma ^{n}+c_{2}\delta ^{n}+An\gamma ^{n}+Bn\delta ^{n}\text{,}
\end{equation*}%
with  $A$  and  $B$  as above.  From  the relations
\begin{eqnarray*}
0 &amp;=&amp;\lev_{1}=c_{1}\gamma +c_{2}\delta +A\gamma +B\delta  \\
w^{2} &amp;=&amp;\lev_{2}=c_{1}\gamma ^{2}+c_{2}\delta ^{2}+2A\gamma ^{2}+2B\delta
^{2}\text{,}
\end{eqnarray*}%
we learn that
\begin{equation*}
c_{1}=-\frac{1}{2}\left( 1+\frac{(w^{3}-6wt)}{(w^{2}+4t)^{3/2}}\right) \text{
 and  }c_{2}=-\frac{1}{2}\left( 1+\frac{(6wt-w^{3})}{(w^{2}+4t)^{3/2}}%
\right) .
\end{equation*}%
Therefore, 
\begin{equation}
\lev_{n}=c_{1}\gamma ^{n}+c_{2}\delta ^{n}+An\gamma ^{n}+Bn\delta ^{n}\text{%
,  }n\geq 1\text{,}  \label{levn}
\end{equation}%
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\times n$  chessboard.  By a \textit{rise} we mean the situation where a
square  $1\times 1$  tile is followed by a rectangular  $1\times 2$ \
tile.  We shall let  $\rise_{n}$  count the number of such rises for all
the  $a_{n}$  tilings of the  $1\times n$  chessboard.  Initially we
find that%
\begin{equation*}
\rise_{1}=0, \ \ \ \rise_{2}=0,\ \ \rise_{3}=wt,\ \ \rise_{4}=2w^{2}t.
\end{equation*}

For  $n\geq 3$, we have%
\begin{equation*}
\rise_{n}=\rise_{n-1}w+\rise_{n-2} t+a_{n-3} w t\text{,}
\end{equation*}%
where (i) the summand  $\rise_{n-1}w$  accounts for the rises that occur
among the tilings that have a square  $1\times 1$  tile on the  $n$th
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\times 2$
 tile covering the  $(n-1)$st and $ n$th squares of the chessboard; and,
(iii) the summand  $a_{n-3} w t$  accounts for the additional rises that
result when we place a rectangular  $1\times 2$  tile at the end of one of
the  $a_{n-3}$  tilings of length  $n-2$  that ends with a square  $%
1\times 1$  tile.  From  (\ref{Gnp1})  we know that  $a_{n-3}=$ $%
G_{n-2}=\frac{\gamma ^{n-2}-\delta ^{n-2}}{\gamma -\delta }$, so now it
follows that 
\begin{eqnarray*}
\rise_{n} &amp;=&amp;\rise_{n-1}w+\rise_{n-2} t+tw\left( \frac{\gamma ^{n-2}-\delta
^{n-2}}{\gamma -\delta }\right)  \\
  &amp;=&amp;\rise_{n-1}w+\rise_{n-2} t+\frac{tw}{\sqrt{w^{2}+4t}}(\gamma
^{n-2}-\delta ^{n-2}),\ \ n\geq 3,\  \\
\ \ \ \rise_{1} &amp;=&amp;\rise_{2}=0.
\end{eqnarray*}%
In this case the particular solution has the form%
\begin{equation*}
A_{1}n\gamma ^{n}+B_{1}n\delta ^{n}.
\end{equation*}%
Substituting  $\rise_{n}=A_{1}n\gamma ^{n}$  into the nonhomogeneous
recurrence relation%
\begin{equation*}
\rise_{n}=\rise_{n-1}w+\rise_{n-2} t+\frac{tw}{\sqrt{w^{2}+4t}}\gamma ^{n-2}%
\text{,}
\end{equation*}%
we find that%
\begin{equation*}
A_{1}n\gamma ^{n}=wA_{1}(n-1)\gamma ^{n-1}+tA_{1}(n-2)\gamma ^{n-2}+\frac{tw%
}{\sqrt{w^{2}+4t}}\gamma ^{n-2}\text{,}
\end{equation*}%
from which it follows that%
\begin{equation*}
A_{1}n\gamma ^{2}=wA_{1}(n-1)\gamma +tA_{1}(n-2)+\frac{tw}{\sqrt{w^{2}+4t}}%
.
\end{equation*}%
Since  $\gamma ^{2}-w\gamma -t=0$, we find that%
\begin{eqnarray*}
A_{1} &amp;=&amp;\frac{tw}{(w\gamma +2t)\sqrt{w^{2}+4t}}=\frac{2tw}{%
(w^{2}+4t)^{3/2}+w(w^{2}+4t)} \\
&amp;=&amp;\frac{2tw}{(w^{2}+4t)(w+\sqrt{w^{2}+4t})}\cdot \frac{(w+\sqrt{w^{2}-4t})}{%
(w+\sqrt{w^{2}-4t})} \\
&amp;=&amp;\frac{-w^{2}+w\sqrt{w^{2}+4t}}{2(w^{2}+4t)}\text{, }
\end{eqnarray*}%
and a similar calculation leads us to%
\begin{eqnarray*}
B_{1} &amp;=&amp;\frac{-tw}{(w\delta +2t)\sqrt{w^{2}+4t}}=\frac{-2tw}{%
(w^{2}+4t)^{3/2}-w(w^{2}+4t)} \\
&amp;=&amp;\frac{-w^{2}-w\sqrt{w^{2}+4t}}{2(w^{2}+4t)}.
\end{eqnarray*}%
So at this point we have%
\begin{equation*}
\rise_{n}=k_{1}\gamma ^{n}+k_{2}\delta ^{n}+A_{1}n\gamma ^{n}+B_{1}n\delta
^{n}\text{, }
\end{equation*}%
with  $A_{1}, B_{1}$ as above.  From%
\begin{eqnarray*}
0 &amp;=&amp;\rise_{1}=k_{1}\gamma +k_{2}\delta +A_{1}\gamma +B_{1}\delta  \\
0 &amp;=&amp;\rise_{2}=k_{1}\gamma ^{2}+k_{2}\delta ^{2}+2A_{1}\gamma
^{2}+2B_{1}\delta ^{2}
\end{eqnarray*}%
we learn that%
\begin{equation*}
k_{1}=\frac{-2tw}{(w^{2}+4t)^{3/2}}\text{ \ and \ }k_{2}=\frac{2tw}{%
(w^{2}+4t)^{3/2}}.
\end{equation*}%
Consequently, for  $n\geq 1$,%
\begin{eqnarray}
\rise_{n} &amp;=&amp;\left( \frac{-2tw}{(w^{2}+4t)^{3/2}}\right) \gamma ^{n}+\left( 
\frac{2tw}{(w^{2}+4t)^{3/2}}\right) \delta ^{n}  \notag \\
&amp;&amp;+\left( \frac{-w^{2}+w\sqrt{w^{2}+4t}}{2(w^{2}+4t)}\right) n\gamma ^{n}+%
\left( \frac{-w^{2}-w\sqrt{w^{2}+4t}}{2(w^{2}+4t)}\right) n\delta ^{n} .
  \label{risen}
\end{eqnarray}

Finally, a \textit{descent} occurs in a tiling when a  $1\times 2$ \
rectangular tile is followed by a  $1\times 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.

\section{Levels, Rises, and Descents for the Circular Tilings}

In dealing with circular tilings we considered the squares on the  $1\times
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  $\widetilde{\lev_{n}}$  count the
levels on the  $1\times n$  circular chessboard, we initially find that%
\begin{eqnarray*}
\widetilde{\lev_{1}} &amp;=&amp;0, \ \widetilde{\lev_{2}}=2w^{2},\ \ \ \widetilde{%
\lev_{3}}=3w^{3}, \\
\widetilde{\lev_{4}} &amp;=&amp;\lev_{4}+w^{2}a_{2}+t^{2}+t \lev_{2} \\
\widetilde{\lev_{5}} &amp;=&amp;\lev_{5}+w^{2}a_{3}+t^{2}a_{1}+t \lev_{3}+2wt^{2}\text{%
.}
\end{eqnarray*}%
For $n\geq 6$, we have 
\begin{equation*}
\widetilde{\lev_{n}} =\lev_{n}+w^{2}a_{n-2}+t^{2}a_{n-4}+ 
t \lev_{n-2}+2wt^{2}a_{n-5}+2t^{3}a_{n-6}.
\end{equation*}
The summands in this recurrence relation arise as follows:

(i)  If the circular chessboard can be split where the  $n$th square and
the first square meet, then we have  $\lev_{n}$  levels as in the linear
case.  If there is a square $ 1\times 1$  tile on each of the  $n$th 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\times 2$  tile on the  $(n-1)$st and  $n$th 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\times 2$ rectangular tile covering the  $%
n $th and first squares.  Since these tiles come in  $t$  colors, there
are  $\lev_{n-2}$  levels for each possible color, totaling  $t \lev_{n-2}$
 levels.  Further, if there is a square  $1\times 1$  tile on square  $%
n-1 $  and a rectangular  $1\times 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\times 1$  tile on the second square
 and a rectangular  $1\times 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\times 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\leq n\leq 5$, provided we have  $a_{-n}=0$  for  $1\leq n\leq 5$.) 

Using the fact that  $a_{n}=\frac{\gamma ^{n+1}-\delta ^{n+1}}{\gamma
-\delta }$  (from  (\ref{Gnp1})) and the solution for  $\lev_{n}$  (from
 (\ref{levn})), the above result for  $\widetilde{\lev_{n}}$  can be
expressed in terms of  $w, t, \gamma , $and  $\delta $. 

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

(i) there is a  $1\times 1$  square tile on square  $i$  of the
chessboard, followed by a $ 1\times 2$  rectangular tile on squares  $%
i+1, i+2$  of the chessboard, for  $1\leq i\leq n-2$; or,

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

(iii) there is a $ 1\times 1$  square tile on square  $n-1$  of the
chessboard, followed by a $ 1\times 2$  rectangular tile on squares  $n,\
1$  of the chessboard.

In the first case we can split the circular  $1\times n$  chessboard
between the  $n$th and first squares and obtain  $\rise_{n}$  rises.  For
the second case we find  $wt a_{n-3}$  additional rises, and the same is
true for the third case.  Consequently, if we let  $\widetilde{\rise_{n}}$
 count the number of rises for the circular $1\times n$  chessboard, then
we have%
\begin{eqnarray*}
\widetilde{\rise_{1}} &amp;=&amp;0, \widetilde{\rise_{2}}=0,\ \text{and} \\
\widetilde{\rise_{n}} &amp;=&amp;\rise_{n}+2wt a_{n-3}, n\geq 3.
\end{eqnarray*}%
This can be expressed in terms of  $w, t, \gamma , $and  $\delta $  by
using  $a_{n}=\frac{\gamma ^{n+1}-\delta ^{n+1}}{\gamma -\delta }$  (from
 (\ref{Gnp1})) and the solution for  $\rise_{n}$  (from  (\ref{risen})).

Finally, a descent occurs for the circular  $1\times n$  chessboard if

(i) there is a  $1\times 2$  rectangular tile on squares  $i$  and  $%
i+1 $  of the chessboard, followed by a  $1\times 1$  square tile on
square  $i+2$, for  $1\leq i\leq n-2$; or,

(ii) there is a $ 1\times 2$  rectangular tile on squares  $n-1$  and  $%
n$  of the chessboard, followed by a  $1\times 1$  square tile on square
 $1$; or,

(iii) there is a $ 1\times 2$  rectangular tile on squares  $n$  and  $%
1 $  of the chessboard, followed by a $ 1\times 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\times n$  chessboard, namely --- the number of descents for the
circular  $1\times n$  chessboard equals  $\widetilde{\rise_{n}}$, for  $%
n\geq 1$.

\section{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$, $\gamma =\alpha $
$=\frac{1+\sqrt{5}}{2} $(the golden ratio), and  $\delta =\beta =-\frac{1}{%
\alpha }$.

First we recall that the Fibonacci numbers can be expressed as sums of
binomial coefficients --- that is, for  $n\geq 0$, 
\begin{equation*}
F_{n}=\left\{ 
\begin{array}{c}
\binom{n-1}{0}+\binom{n-2}{1}+\binom{n-3}{2}+\cdots + \binom{(n-1)/2}{(n-1)/2}%
,\ n\ \ \text{odd} \\ 
\binom{n-1}{0}+\binom{n-2}{1}+\binom{n-3}{2}+ \cdots + \binom{n/2}{(n/2)-1},\ n\
\ \text{even,}%
\end{array}%
\right.
\end{equation*}%
where  $F_{0}=\binom{-1}{0}=0$.  

Now we find that  
\begin{equation*}
G_{n}=\left\{ 
\begin{array}{c}
\binom{n-1}{0}w^{n-1}+\binom{n-2}{1}w^{n-3}t+\binom{n-3}{2}%
w^{n-5}t^{2}+\cdots + \binom{(n-1)/2}{(n-1)/2}w^{0}t^{(n-1)/2}, \\ 
\ n\ \ \text{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}+\cdots +\ \binom{n/2}{(n/2)-1}wt^{(n-2)/2}, \\ 
\ n\ \ \text{even,}%
\end{array}%
\right.
\end{equation*}%
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\geq r\geq 1$.  However, we shall provide a combinatorial proof --- one
comparable to those given in \cite{Benjamin,Brigham}.

\begin{proof}
From (\ref{Gnp1}) we know that  $G_{n}=a_{n-1},$ the number of
ways we can tile a  $1\times (n-1)$  chessboard with  $1\times 1$ 
square tiles (of  $w$  colors) and  $1\times 2$  rectangular tiles (of  
$t$  colors).  If we tile the board with only  $1\times 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\times 1$  square tiles and one
 $1\times 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\times (n-1)$  chessboard. \
Continuing, for the case of  $(n-5)$  $1\times 1$  square tiles and two  
$1\times 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\times (n-1)$  chessboard with  $(n-1)/2$  $1\times 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\times n$  chessboard with
one  $1\times 1$  square tile and  $((n-1)-1)/2=(n-2)/2=(n/2)-1$  $%
1\times 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.
\end{proof}

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{equation*}
\begin{tabular}{lll}
(7.1) &amp; $F_{n+m+1}=F_{n+1}F_{m+1}+F_{n}F_{m}$ &amp; $%
G_{n+m+1}=G_{n+1}G_{m+1}+tG_{n}G_{m}$ \\
(7.2) &amp; $F_{2n+1}=F_{n+1}^{2}+F_{n}^{2}$ &amp; $G_{2n+1}=G_{n+1}^{2}+tG_{n}^{2}$
\\ 
(7.3) &amp; $2\ L_{m+n}=5\ F_{m}F_{n}+L_{m}L_{n}$ &amp; $%
2H_{m+n}=(w^{2}+4t)G_{m}G_{n}+H_{m}H_{n}$ \\ 
(7.4) &amp; $\sum\nolimits_{k=0}^{n}\binom{n}{k}F_{k}L_{n-k}=2^{n}F_{n}$ &amp; $%
\sum\nolimits_{k=0}^{n}\binom{n}{k}G_{k}H_{n-k}=2^{n}G_{n}$ \\ 
(7.5) &amp; $\sum\nolimits_{k=0}^{n}\binom{n}{k}F_{k}=F_{2n}$ &amp; $%
\sum\nolimits_{k=0}^{n}\binom{n}{k}w^{k}t^{n-k}G_{k}=G_{2n}$ \\ 
(7.6) &amp; $\sum\nolimits_{k=0}^{n}\binom{n}{k}L_{k}=L_{2n}$ &amp; $%
\sum\nolimits_{k=0}^{n}\binom{n}{k}w^{k}t^{n-k}H_{k}=H_{2n}$ \\ 
(7.7) &amp; $F_{2n}=F_{n}L_{n}$ &amp; $G_{2n}=G_{n}H_{n}$ \\ 
(7.8) &amp; $F_{n-1}+F_{n+1}=L_{n}$ &amp; $tG_{n-1}+G_{n+1}=H_{n}$ \\ 
(7.9) &amp; $2F_{n+1}=F_{n}+L_{n}$ &amp; $2G_{n+1}=wG_{n}+H_{n}$ \\ 
(7.10) &amp; $2L_{n+1}=5F_{n}+L_{n}$ &amp; $2H_{n+1}=(w^{2}+4t)G_{n}+wH_{n}$ \\ 
(7.11) &amp; $L_{n}^{2}-5F_{n}^{2}=4(-1)^{n}$ &amp; $%
H_{n}^{2}-(w^{2}+4t)G_{n}^{2}=4(-t)^{n}$ \\ 
(7.12) &amp; $F_{m}L_{n}+F_{n}L_{m}=2F_{m+n}$ &amp; $G_{m}H_{n}+G_{n}H_{m}=2G_{m+n}$
\\ 
(7.13) &amp; $L_{n}^{2}+L_{n+1}^{2}=L_{2n}+L_{2n+2}$ &amp; $(\sqrt{t}%
H_{n})^{2}+H_{n+1}^{2}=tH_{2n}+H_{2n+2}$ \\ 
(7.14) &amp; $F_{n+1}F_{n-1}-F_{n}^{2}=(-1)^{n}$ &amp; $%
G_{n+1}G_{n-1}-G_{n}^{2}=t^{n-1}(-1)^{n}$%
\end{tabular}%
\end{equation*}

\begin{center}
Table 7.1
\end{center}

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 \cite{Benjamin}
for the case where  $w=t=1$.

\begin{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\times
(n+m)$  chessboard.  For these tilings consider the two possible cases: \
(i)  We split the tiling between the  $n$th and $(n+1)$st squares --- this
is possible if these squares are not covered with a  $1\times 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\times 2$  rectangular tile covering the   $n$th
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\times 2$  rectangular tile
comes in  $t$  colors, this case provides the remaining  $tG_{n}G_{m}$ \
possible tilings.  Consequently,%
\begin{equation*}
G_{n+m+1}=G_{n+1}G_{m+1}+tG_{n}G_{m}.
\end{equation*}

\noindent (7.2)  This is just a special case of (7.1), for  
\begin{equation*}
G_{2n+1}=G_{n+n+1}=G_{n+1}G_{n+1}+tG_{n}G_{n}=G_{n+1}^{2}+tG_{n}^{2}.
\end{equation*}

\noindent (7.4)  Using the Binet forms for  $G_{n}$  and  $H_{n}$, we
find that%
\begin{eqnarray*}
&amp;&amp;\sum\nolimits_{k=0}^{n}\binom{n}{k}G_{k}H_{n-k} \\
&amp;=&amp;\sum\nolimits_{k=0}^{n}\binom{n}{k}\frac{\gamma ^{k}-\delta ^{k}}{\gamma
-\delta }\left( \gamma ^{n-k}+\delta ^{n-k}\right) \\
&amp;=&amp;\sum\nolimits_{k=0}^{n}\binom{n}{k}\frac{\gamma ^{n}-\gamma ^{n-k}\delta
^{k}+\gamma ^{k}\delta ^{n-k}-\delta ^{n}}{\gamma -\delta } \\
&amp;=&amp;\sum\nolimits_{k=0}^{n}\binom{n}{k}\frac{\gamma ^{n}-\delta ^{n}}{\gamma
-\delta }-\sum\nolimits_{k=0}^{n}\binom{n}{k}\frac{\gamma ^{n-k}\delta ^{k}}{%
\gamma -\delta }+\sum\nolimits_{k=0}^{n}\binom{n}{k}\frac{\gamma ^{k}\delta
^{n-k}}{\gamma -\delta } \\
&amp;=&amp;G_{n}\sum\nolimits_{k=0}^{n}\binom{n}{k}-\frac{(\gamma +\delta )^{n}}{%
\gamma -\delta }+\frac{(\gamma +\delta )^{n}}{\gamma -\delta }=2^{n}G_{n}.
\end{eqnarray*}

\noindent (7.7)  This follows readily as%
\begin{equation*}
G_{2n}=\frac{\gamma ^{2n}-\delta ^{2n}}{\gamma -\delta }=\frac{\gamma
^{n}-\delta ^{n}}{\gamma -\delta }\left( \gamma ^{n}+\delta ^{n}\right)
=G_{n}H_{n}.
\end{equation*}

\noindent (7.9)  Starting with the right-hand side of the result we see that%
\begin{eqnarray*}
&amp;&amp;wG_{n}+H_{n} \\
&amp;=&amp;w\frac{\gamma ^{n}-\delta ^{n}}{\gamma -\delta }+\left( \gamma
^{n}+\delta ^{n}\right) \\
&amp;=&amp;\frac{w\left( \gamma ^{n}-\delta ^{n}\right) +\left( \gamma ^{n}+\delta
^{n}\right) \left( \gamma -\delta \right) }{\gamma -\delta } \\
&amp;=&amp;\frac{\left( \gamma ^{n+1}-\delta ^{n+1}\right) +(w-\delta )\gamma
^{n}-(w-\gamma )\delta ^{n}}{\gamma -\delta } \\
&amp;=&amp;\frac{\left( \gamma ^{n+1}-\delta ^{n+1}\right) +\left( \gamma
^{n+1}-\delta ^{n+1}\right) }{\gamma -\delta }=2G_{n+1}\text{, since  }%
\gamma +\delta =w.
\end{eqnarray*}

\noindent (7.10)  Again we start on the right-hand side and find that%
\begin{eqnarray*}
&amp;&amp;(w^{2}+4t)G_{n}+wH_{n} \\
&amp;=&amp;\left( \gamma -\delta \right) ^{2}\left( \frac{\gamma ^{n}-\delta ^{n}}{%
\gamma -\delta }\right) +w\left( \gamma ^{n}+\delta ^{n}\right) \\
&amp;=&amp;\left( \gamma -\delta \right) (\gamma ^{n}-\delta ^{n})+w\left( \gamma
^{n}+\delta ^{n}\right) \\
&amp;=&amp;\left( \gamma ^{n+1}+\delta ^{n+1}\right) +\gamma ^{n}(w-\delta )+\delta
^{n}(w-\gamma ) \\
&amp;=&amp;\left( \gamma ^{n+1}+\delta ^{n+1}\right) +\gamma ^{n}(\gamma )+\delta
^{n}(\delta ) \\
&amp;=&amp;2\left( \gamma ^{n+1}+\delta ^{n+1}\right) =2H_{n+1}.
\end{eqnarray*}

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

\begin{eqnarray*}
&amp;&amp;H_{n}^{2}-(w^{2}+4t)G_{n}^{2} \\
&amp;=&amp;\left( \gamma ^{n}+\delta ^{n}\right) ^{2}-\left( \gamma -\delta \right)
^{2}\left( \frac{\gamma ^{n}-\delta ^{n}}{\gamma -\delta }\right) ^{2} \\
&amp;=&amp;\gamma ^{2n}+2\gamma ^{n}\delta ^{n}+\delta ^{2n}-\left( \gamma
^{2n}-2\gamma ^{n}\delta ^{n}+\delta ^{2n}\right) \\
&amp;=&amp;4\gamma ^{n}\delta ^{n}=4(-t)^{n}.
\end{eqnarray*}

\noindent (7.12)  This result for  $F_{n}$  and  $L_{n}$  can be found
in \cite{Blazej}.%
\begin{eqnarray*}
&amp;&amp;G_{m}H_{n}+G_{n}H_{m} \\
&amp;=&amp;\left( \frac{\gamma ^{m}-\delta ^{m}}{\gamma -\delta }\right) \left(
\gamma ^{n}+\delta ^{n}\right) +\left( \frac{\gamma ^{n}-\delta ^{n}}{\gamma
-\delta }\right) \left( \gamma ^{m}+\delta ^{m}\right) \\
&amp;=&amp;\frac{\left( \gamma ^{m+n}-\delta ^{m+n}\right) -\delta ^{m}\gamma
^{n}+\gamma ^{m}\delta ^{n}}{\gamma -\delta }+\frac{\left( \gamma
^{m+n}-\delta ^{m+n}\right) -\delta ^{n}\gamma ^{m}+\delta ^{m}\gamma ^{n}}{%
\gamma -\delta } \\
&amp;=&amp;2\left( \frac{\gamma ^{m+n}-\delta ^{m+n}}{\gamma -\delta }\right)
=2G_{m+n}.
\end{eqnarray*}

\noindent (7.13)  This result for  $L_{n}$  is found in \cite{Koshy}.  
\begin{eqnarray*}
&amp;&amp;(\sqrt{t}H_{n})^{2}+H_{n+1}^{2} \\
&amp;=&amp;t\left( \gamma ^{n}+\delta ^{n}\right) ^{2}+\left( \gamma ^{n+1}+\delta
^{n+1}\right) ^{2} \\
&amp;=&amp;t\left( \gamma ^{2n}+2\gamma ^{n}\delta ^{n}+\delta ^{2n}\right) +\left(
\gamma ^{2n+2}+2\gamma ^{n+1}\delta ^{n+1}+\delta ^{2n+2}\right) \\
&amp;=&amp;t(\gamma ^{2n}+\delta ^{2n})+2t(-t)^{n}+\left( \gamma ^{2n+2}+\delta
^{2n+2}\right) +2(-t)^{n+1} \\
&amp;=&amp;tH_{2n}+H_{2n+2}.
\end{eqnarray*}

\noindent (7.14)  This result for the Fibonacci numbers was originally
discovered in 1680 by the Italian-born 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). 
\begin{eqnarray*}
&amp;&amp;G_{n+1}G_{n-1}-G_{n}^{2} \\
&amp;=&amp;\left( \frac{\gamma ^{n+1}-\delta ^{n+1}}{\gamma -\delta }\right) \left( 
\frac{\gamma ^{n-1}-\delta ^{n-1}}{\gamma -\delta }\right) -\left( \frac{%
\gamma ^{n}-\delta ^{n}}{\gamma -\delta }\right) ^{2} \\
&amp;=&amp;\frac{\gamma ^{2n}-\delta ^{2}(\gamma \delta )^{n-1}-\gamma ^{2}(\gamma
\delta )^{n-1}+\delta ^{2n}-\gamma ^{2n}+2(\gamma \delta )^{n}-\delta ^{2n}}{%
(\gamma -\delta )^{2}} \\
&amp;=&amp;\frac{(\gamma ^{2}+\delta ^{2})(-1)(\gamma \delta )^{n-1}+2(\gamma \delta
)^{n}}{(\gamma -\delta )^{2}}=\frac{(-1)(\gamma \delta )^{n-1}(\gamma
^{2}+\delta ^{2}-2\gamma \delta )}{(\gamma -\delta )^{2}} \\
&amp;=&amp;\frac{(-1)(\gamma \delta )^{n-1}(\gamma -\delta )^{2}}{(\gamma -\delta
)^{2}}=(-1)(-t)^{n-1}=t^{n-1}(-1)^{n}.
\end{eqnarray*}

\end{proof}

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

\section{First Order Recurrence Relations for $G_n$ and $H_n$}

Before we start, the reader must realize that the title of this section does 
\textit{not }contain the adjective \textit{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 \cite{Basin}.  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%
\begin{equation*}
F_{n+1}=\frac{F_{n}+\sqrt{5F_{n}^{2}+4(-1)^{n}}}{2}\text{,}
\end{equation*}%
while the results in (7.10) and (7.11) were used to derive%
\begin{equation*}
L_{n+1}=\frac{L_{n}+\sqrt{5(L_{n}^{2}-4(-1)^{n})}}{2}.
\end{equation*}

Turning now to the results in (7.9)--(7.11) for  $G_{n}$  and  $H_{n}$ \
we find that 
\begin{eqnarray*}
2G_{n+1} &amp;=&amp;wG_{n}+H_{n}  \text{(from (7.9))} \\
&amp;=&amp;wG_{n}+\sqrt{(w^{2}+4t)G_{n}^{2}+4(-t)^{n}}  \text{(from (7.11))} \\
\text{So  }G_{n+1} &amp;=&amp;\frac{wG_{n}+\sqrt{(w^{2}+4t)G_{n}^{2}+4(-t)^{n}}}{2}%
.
\end{eqnarray*}

Likewise, we see that%
\begin{eqnarray*}
2H_{n+1} &amp;=&amp;(w^{2}+4t)G_{n}+wH_{n}  \text{(from (7.10))} \\
&amp;=&amp;wH_{n}+(w^{2}+4t)\sqrt{\frac{H_{n}^{2}-4(-t)^{n}}{w^{2}+4t} }\text{ \
(from (7.11))} \\
&amp;=&amp;wH_{n}+\sqrt{(w^{2}+4t)\left( H_{n}^{2}-4(-t)^{n}\right) }. \\
\text{So  }H_{n+1} &amp;=&amp;\frac{wH_{n}+\sqrt{(w^{2}+4t)\left(
H_{n}^{2}-4(-t)^{n}\right) }}{2}.
\end{eqnarray*}

\section{One Further Result}

Among the many fascinating properties exhibited by the Fibonacci numbers one
finds that%
\begin{equation*}
\sum_{\substack{ s_{1}+s_{2}+\cdots +s_{k}=n  \ k&gt;0}}s_{1}s_{2} \cdots \
s_{k}=F_{2n}\text{,}
\end{equation*}%
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. 
\begin{equation*}
\begin{array}{cc}
\text{Composition of  }4 &amp; \text{Product of Summands in the Composition} \\
4 &amp; 4 \\ 
3+1 &amp; 3\cdot 1=3 \\ 
2+2 &amp; 2\cdot 2=4 \\ 
2+1+1 &amp; 2\cdot 1\cdot 1=2 \\ 
1+3 &amp; 1\cdot 3=3 \\ 
1+2+1 &amp; 1\cdot 2\cdot 1=2 \\ 
1+1+2 &amp; 1\cdot 1\cdot 2=2 \\ 
1+1+1+1 &amp; 1\cdot 1\cdot 1\cdot 1=1%
\end{array}%
\end{equation*}

\begin{center}
Table 9.1
\end{center}

Here the sum of the eight products is%
\begin{eqnarray*}
4+3+4+2+3+2+2+1 &amp;=&amp;21\ (=F_{8})\text{, or} \\
\sum\limits_{\substack{ s_{1}+\ \cdots \ +\ s_{k}=4  \\ s_{i}\geq 1,\ i=1,\
\ldots,\ k}}s_{1}\ \cdots\ s_{k} &amp;=&amp;21\ (=F_{8}).
\end{eqnarray*}%
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 \cite{Alladi} 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{equation*}
\sum_{\substack{ s_{1}+s_{2}+\cdots +s_{k}=n  \\ k&gt;0}}s_{1}s_{2}\ \cdots\
s_{k}=F_{2n}\text{,}
\end{equation*}%
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, $\ldots$, 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, $\ldots$, 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 
\begin{equation*}
(k-1)+k+2(n-k)=2n-1
\end{equation*}%
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, $\ldots$, and  $s_{k\text{ }}$choices for the  $k$th
dot, this case accounts for  $s_{1}s_{2} \cdots  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 $k$th  $1$  by a circled
dot, when  $k$  is odd, and by a bar, when  $k$  is even.

Consequently, $\sum_{\substack{ s_{1}+s_{2}+\cdots +s_{k}=n  \\ k&gt;0}}s_{1}s_{2}\
\cdots  s_{k}$  counts all of the compositions of  $2n-1$, where the only
summands are  $1$'s and  $2$'s, so  
\begin{equation*}
\sum_{\substack{ s_{1}+s_{2}+\cdots +s_{k}=n  \\ k&gt;0}}s_{1}s_{2}\ \cdots\
s_{k}=F_{2n}.
\end{equation*}

We now claim that for any positive integers  $w$  and  $t$, 
\begin{eqnarray*}
\sum_{\substack{ s_{1}+s_{2}+\cdots+s_{k}=n  \\ k&gt;0}}s_{1}s_{2}\ \cdots\
s_{k}w^{2k-1}t^{n-k} 
&amp;=&amp;G_{2n}=\frac{\gamma ^{2n}-\delta ^{2n}}{\gamma -\delta } \\
&amp;=&amp;\frac{\left( \frac{w+\sqrt{w^{2}+4t}}{2}\right) ^{2n}-\left( \frac{w-%
\sqrt{w^{2}+4t}}{2}\right) ^{2n}}{\sqrt{w^{2}+4t}}.
\end{eqnarray*}%
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,
$\ldots$, 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, $\ldots$, 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\times 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\times 1$  square tile (which comes in  $w$  colors). \
This composition of  $n$  then provides us with  $s_{1}s_{2}\ \cdots \
s_{k}w^{2k-1}t^{n-k}$  of the tilings of a  $1\times \lbrack
(2k-1)+2(n-k)]=1\times (2n-1)$  chessboard, and, consequently, $\sum 
_{\substack{ s_{1}+s_{2}+\cdots +s_{k}=n  \\ k&gt;0}}s_{1}s_{2}\ \cdots\
s_{k}w^{2k-1}t^{n-k}$  counts all of the tilings of a  $1\times (2n-1)$ \
chessboard using  $1\times 1$  square tiles (which come in  $w$  colors)
and  $1\times 2$  rectangular tiles (which come in  $t$  colors).  This
is  $G_{2n}$. 

\section{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.


\begin{thebibliography}{9}
\bibitem{Alladi} K. Alladi and V. E. Hoggatt, Jr.  Compositions with ones
and twos. \ \textit{Fibonacci Quart.}, \textbf{13} (1975), 233--239.\ 

\bibitem{Basin} S. L. Basin. Problem B-42. \ \textit{Fibonacci
Quart.},\textit{\ }\textbf{2} (1964), 329.

\bibitem{Benjamin} A. T. Benjamin and J. J. Quinn. \ \textit{Proofs that
Really Count}. \ The Mathematical Association of America, 2003.

\bibitem{Blazej} R. Blazej. \ Problem B-294. \ \textit{Fibonacci
Quart.},\textit{\ }\textbf{13} (1975), 375.

\bibitem{Brigham} R. C. Brigham, R. M. Caron, P. Z. Chinn, and R. P.
Grimaldi. \ A tiling scheme for the Fibonacci numbers. \ \textit{J. 
Recreational Math.}, \textbf{28} (1996--97), 10--17.

\bibitem{Brualdi} R. A. Brualdi. \ \textit{Introductory Combinatorics},
5th edition.\ Pearson Prentice Hall, 2010.

\bibitem{Grimaldi} R. P. Grimaldi. \ \textit{Discrete and Combinatorial
Mathematics}, 5th edition. \ Pearson Addison Wesley, 2004.

\bibitem{Koshy} T. Koshy. \ The convergence of a Lucas series. \textit{
Math. Gazette},\ \textbf{83} (1999), 272--274.

\bibitem{Mansour} T. Mansour and A. Munagi. \ Enumeration of partitions by
long rises, levels and descents. \ \textit{J. Integer Sequences}, 
\textbf{12} (2009), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Munagi/munagi15.html}{Article 09.1.8}.
\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B37; Secondary 11B39.

\noindent \emph{Keywords: } 
tilings, Fibonacci numbers, Lucas numbers,
Jacobsthal numbers, levels, rises, descents, circular tilings.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received August 13 2009;
revised version received June 15 2010.  
Published in {\it Journal of Integer Sequences}, June 16 2010.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

</pre></body></html>