\documentclass[12pt]{article}
\usepackage[dvips]{graphicx}
%\usepackage[pdftex]{graphicx}
\usepackage{epsfig}

%\usepackage{fancyheadings}
%\usepackage{setspace}
%\usepackage{fancyvrb}
%\usepackage[pdftex]{color}
%\usepackage[hyper]{listings}
%\usepackage{geometry}
%\usepackage{wrapfig}
%\usepackage{subfigure}
%\newcommand{\goodgap}{
%  \hspace{\subfigtopskip}
%  \hspace{\subfigbottomskip}}
%\usepackage{hyperref}
%\usepackage{algorithm}
%\usepackage{algorithmic}
%\usepackage[pdftex]{graphicx}
\usepackage{amsmath, rotating}
\usepackage{amsfonts}
\usepackage{amssymb}
%\usepackage{mathrsfs}
%\usepackage{epic}
%\usepackage{curves}
\usepackage{amsthm}
\newcommand{\sqbinom}[2]{\begin{bmatrix}#1\\#2\end{bmatrix}}
\numberwithin{equation}{section}

\setlength{\textwidth}{6.3in} \setlength{\textheight}{8.7in}
\setlength{\topmargin}{0pt} \setlength{\headsep}{0pt}
\setlength{\headheight}{0pt} \setlength{\oddsidemargin}{0pt}
\setlength{\evensidemargin}{0pt}

\makeatletter
\newfont{\footsc}{cmcsc10 at 8truept}
\newfont{\footbf}{cmbx10 at 8truept}
\newfont{\footrm}{cmr10 at 10truept}
%\renewcommand{\ps@plain}{%
%\renewcommand{\@oddfoot}{\footsc the electronic journal of combinatorics
%  {\footbf 13} (2006), \#R00\hfil\footrm\thepage}}
\makeatother \pagestyle{plain}

%%%%%%%%%%%%
\def\theoremname{Theorem}
\newtheorem{theorem}{\theoremname}[section]
\def\thetheorem{\thesection.\arabic{theorem}}
\def\theoremfont{\upshape}
\def\theoremheadfont{\bfseries}
%
\def\corollaryname{Corollary}
\newtheorem{corollary}{\corollaryname}[section]
\def\thecorollary{\thesection.\arabic{corollary}}
\def\corollaryfont{\itshape}
\def\corollaryheadfont{\bfseries}
%
\def\examplename{Example}
\newtheorem{example}{\examplename}[section]
\def\theexample{\thesection.\arabic{example}}
\def\examplefont{\itshape}
\def\exampleheadfont{\bfseries}
%
%\providecommand{\qedsymbol}{\openbox}%
%\renewenvironment{proof}[1][\proofname]{\par
%  \pushQED{\qed}%
%%  \normalfont \topsep6\p@\@plus6\p@\relax
%  \trivlist
%  \item[\hskip\labelsep
%        \itshape
%    #1.]\ignorespaces
%}
%{%
%%  \popQED\endtrivlist\@endpefalse
%}
%\providecommand{\proofname}{Proof}
%
%
%%%%%%%%%%%%


\newcommand{\nfact}[1]{^{\textstyle !}_{#1}}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\newtheorem{theo}{Theorem}[section]
\newtheorem{cor}[theo]{Corollary}
\numberwithin{theo}{section}
\newtheorem{lem}[theo]{Lemma}
\newcommand{\RN}{\mathcal{R}}


%[Float at the top formula]
\makeatletter
\setlength\@fptop{0\p@}
\makeatother

\raggedbottom
\sloppy


\makeatletter  % Renumerotare Figs si Tables functie de sectiune.
\@addtoreset{figure}{section}
\renewcommand{\thefigure}{\thesection.\@arabic\c@figure}
\makeatother




\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 Compression Theorems for Periodic Tilings and Consequences
}
\vskip 1cm

\large
Arthur T. Benjamin\\
Department of Mathematics\\
Harvey Mudd College\\
Claremont, CA 91711 \ USA\\
\href{mailto:benjamin@hmc.edu}{\tt benjamin@hmc.edu} \\
\ \\
Alex K. Eustis\\
Department of Mathematics\\
UC San Diego\\
La Jolla, CA 92037 \ USA\\
\href{mailto:akeustis@gmail.com}{\tt akeustis@gmail.com} \\
\ \\
Mark A. Shattuck\\
Department of Mathematics\\
University of Tennessee\\
Knoxville, TN 37996 \ USA \\
\href{mailto:shattuck@math.utk.edu}{\tt shattuck@math.utk.edu}\\
\end{center}

\vskip .2 in

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


%\begin{document}
%\maketitle



\section{Introduction}

In what follows, $\mathbb{Z}$, $\mathbb{N}$, and $\mathbb{P}$ denote, respectively, the integers, the
nonnegative integers, and the positive integers. Empty sums take the value 0 and empty products the value $1$, with
$0^0:=1$. Let
$F_n$ and
$L_n$ denote the Fibonacci and Lucas numbers, defined, respectively, by $F_0=0$, $F_1=1$ with $F_n=F_{n-1} + F_{n-2}$ if
$n \geqslant 2$ and by
$L_0=2$, $L_1=1$ with $L_n=L_{n-1}+L_{n-2}$ if $n \geqslant 2$.

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

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

\section{Weighted Tilings}
In this section, we recall (and slightly generalize) the weighted
tiling model described in Graham, Knuth, and Patashnik
%[5, Section 6.7]
\cite[Section~6.7]{ref5}
and review some of its properties.  First consider a board of
length $n$ with cells labelled 1 to $n$ from left to right. A
tiling of this board (termed an $n$\textit{-tiling}) is an
arrangement of indistinguishable squares and indistinguishable
dominos which cover it completely, where pieces do not overlap, a
domino is a rectangular piece covering two cells, and a square is
a piece covering a single cell. Let ${\cal F}_n$ denote the set of
all $n$-tilings; recall that
\begin{equation}
%|\bar{{\cal F}}_n| = F_{n+1},\quad n\in \mathbb{P}.
|{{\cal F}}_n| = F_{n+1},\quad n\in \mathbb{P}.
\end{equation}
(If we set ${{\cal F}}_0=\{\phi\}$, the ``empty tiling," then (2.1) holds for $n=0$ as well.)

Let $(a_i)_{i \geqslant 1}$ and $(b_i)_{i \geqslant 1}$ be
sequences of real numbers and suppose $n \in \mathbb{P}$. Given
$T\in {{{\cal F}}}_n$, assign a weight to each tile of $T$
according to its location as follows: (i) a square covering cell
$k$ receives weight $a_k$, and (ii) a domino covering the $k^{\it
th}$ boundary receives weight $b_k$ (by the $k^{\it th}$ boundary,
we mean the boundary between cells $k$ and $k+1$, $1\leq k\leq
n-1$).
\begin{eqnarray*}
&&\fbox{$\phantom{a_1}$}\fbox{$\phantom{a_1}$}\fbox{$\phantom{a_1}$}\fbox{$\phantom{a_1}$}\fbox{$\phantom{a_1}$}\fbox{$\phantom{a_1}$}\fbox{$\phantom{a_1}$}\\
&& \ a_1 \  \ a_2 \ \ a_3   \  \  \  \ \cdots\ \  \  \  \  \  \ \   a_n\\
&& \ \ \ \ b_1 \  \ b_2\ \   b_3  \  \  \  \ \cdots\   \ \    b_{n-1}\\
\end{eqnarray*}

Define the weight $w(T)$ to be the product of the weights of tiles and define the weighted sum $|1:n|$ by
\begin{equation}
|1:n| :=\sum_{T\in{{{\cal F}}_n}}w(T).
\end{equation}
For example, when $n=4$, there are the five 4-tilings pictured below,
\[
\begin{array}{c@{\quad}c@{\quad}l}
\fbox{\vphantom{$b_3$}$a_1$}\fbox{\vphantom{$b_3$}$a_2$}\fbox{\vphantom{$b_3$}$a_3$}\fbox{\vphantom{$b_3$}$a_4$} &
\fbox{\vphantom{$b_3$}$a_1$}\fbox{\vphantom{$b_3$}$a_2$}\fbox{\vphantom{$b_3$} \hskip .09 in $b_3$ \hskip .09 in } &
\fbox{\vphantom{$b_3$}$a_1$}\fbox{\vphantom{$b_2$} \hskip .09 in $b_2$ \hskip .09 in}\fbox{\vphantom{$b_3$}$a_4$}\\ [18pt]
& \fbox{\vphantom{$b_1$}\hskip .09 in $b_1$\hskip .09 in }\fbox{\vphantom{$b_3$}$a_3$}\fbox{\vphantom{$b_3$}$a_4$}  \quad\quad\quad
 \fbox{\vphantom{$b_1$}\hskip .09 in $b_1$\hskip .09 in }\fbox{\vphantom{$b_3$}\hskip .09 in $b_3$\hskip .09 in }  &
\end{array}
\]
which implies
\[
|1:4| = a_1 a_2 a_3 a_4 + a_1 a_2 b_3+ a_1 b_2 a_4 + b_1 a_3 a_4+ b_1 b_3.
\]
\noindent
If $a_i=b_i=1$ for all $i$, then each tiling receives
unit weight and $|1:n|=F_{n+1}$.\\

\noindent \textbf{Remarks.} ~If $a_i=1$ and $b_i=q^it$ or if
$a_i=q^i$ and $b_i=t$ for all $i$, then one gets, respectively,
the $q$-Fibonacci polynomials studied by Carlitz
%[3]
\cite{ref3}
and Cigler
%[4]
\cite{ref4}
and by Shattuck and Wagner
%[9]
\cite{ref9}. If $b_i=1$ for all $i$, then
(2.2) reduces to the continuant polynomial described in Graham, Knuth and Patashnik
%[5, p.~301--309]
\cite[p.~301--309]{ref5}.\\

For integers $1\leq i\leq j\leq n$, we write $|i:j|$ to mean the
sum of weights of tilings of the sub-board starting at cell $i$
and ending at cell $j$. For example, $|i:i|=a_i$ and
$|i:i+1|=a_ia_{i+1}+b_i$. We'll take $|i:i-1|=1$ and $|i:i-2|=0$
as conventions.

Considering whether or not the $k^{\it th}$ boundary of a tiling is covered by a domino yields the identity
\begin{equation}
|i:j|=|i:k||k+1:j| + b_k|i:k-1||k+2:j|,\quad i\leq k\leq j,
\end{equation}
the $k=i$ and $k=j-1$ cases of which give the recurrences
\begin{equation}
|i:j|=a_i|i+1:j| + b_i|i+2:j|
\end{equation}
and
\begin{equation}
|i:j|=a_j|i:j-1| + b_{j-1}|i:j-2|.\vspace{.15cm}
\end{equation}

Let ${{\cal L}}_n$ denote the set of $n$-tilings in which a domino
can wrap around from cell $n$ back to cell 1 (termed {\it Lucas}
$n$-{\it tilings} or $n$-{\it bracelets}). When a bracelet has a
wraparound domino, it is called {\it out-of-phase}; otherwise, it
is called {\it in-phase}. Recall that
\begin{equation}
|{\cal L}_n|=L_n,\quad n\in \mathbb{P},
\end{equation}
the $n^{\it th}$ Lucas number (see, e.g.,
%[2, p.~18], [10, p.~246])
\cite[p.~18]{ref2}, \cite[p.~246]{ref10}.
If we interpret $L_0=2$ to mean that there are two empty
0-bracelets, one of which is in-phase, the other out-of-phase,
then (2.6) holds for $n=0$ as well.

We extend slightly the prior model for $n$-tilings to
$n$-bracelets by keeping all weights the same as before and
assigning a wraparound domino weight $b_n$. One gets the weighted
sum
\begin{equation}
|1::n|:=\sum\limits_{T\in{\cal L}_n}w(T),
\end{equation}
which reduces to $L_n$ when $a_i=b_i=1$ for all $i$.\\

\noindent \textbf{Remark.} ~If $a_i=1$ and $b_i=q^it$ or if
$a_i=q^i$ and $b_i=t$ for all $i$, then one gets, respectively,
the $q$-Lucas polynomials studied by Carlitz
%[3]
\cite{ref3}
and by Shattuck
and Wagner
%[9]
\cite{ref9}.\\

Considering whether or not a member of ${\cal L}_n$ contains a
wraparound domino gives
\begin{equation}
|1::n|=|1:n| + b_n|2:n-1|,\quad n \geqslant 1.
\end{equation}
The $|1::n|$ do not appear to satisfy simple two-term recurrences like (2.4) or (2.5).

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

\section{Periodic Boards}
Throughout this section, we consider the important special case of $|1:n|$ in which the $a_i$ and $b_i$ are both periodic sequences.
For $m \geqslant 1$, we say that a board has {\it period} $m$ if $a_{i+m}=a_i$ and $b_{i+m}=b_i$ for all $i$.
% for some $m\in \mathbb{P}$.
It will be convenient to think of such tilings within a
rectangular grid of width $m$, where a domino's left half may end
one row whenever its right half starts the next.
\[
\begin{array}{l@{\qquad}l@{\qquad}l}
\begin{array}{l}
\fbox{$\phantom{a_1}$}\fbox{$\phantom{a_1}$}\fbox{$\phantom{a_1 a_1 a_1}$}\fbox{$\phantom{a_1}$}\\
 ~a_1 \ \ a_2 \ \ \cdots  \ \  \ \  \ a_{nm} \\
~~~~b_1 \ \ b_2 \ \ \cdots \  b_{nm-1}
\end{array} & \Longrightarrow  & \begin{array}{l@{\ }l@{\ }l}
\fbox{$\phantom{a_1}$}\fbox{$\phantom{a_1}$}\fbox{$\phantom{a_1 a_1 a_1}$}\fbox{$\phantom{a_1}$} & & \\
\vdots\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \  \vdots&  \ \  \} &  {\rm
\hbox{\hspace*{-26pt} \textit{n}}}  \\
\fbox{$\phantom{a_1}$}  \fbox{$\phantom{a_1}$} \fbox{$\phantom{a_1 a_1 a_1}$}\fbox{$\phantom{a_1}$} &
\hbox{\hspace*{20pt} rows}\\
\fbox{$\phantom{a_1}$}  \fbox{$\phantom{a_1}$}\fbox{$\phantom{a_1 a_1 a_1}$}\fbox{$\phantom{a_1}$}\\
~a_1 \  \ a_2 \  \ \cdots  \  \  \  \  \  \ a_{m} \\
~~~~b_1 \  \ b_2 \  \cdots    b_{m-1} \  b_m
\end{array}
\end{array}
\]

%%%%


Generalizing the tail-swapping technique extends the identity
%[2, p.~28]
\cite[p.~28]{ref2}
\begin{equation}
F_{2m+1} = L_mF_{m+1} + (-1)^{m+1},\quad m \geqslant 0,
\end{equation}

\noindent
to

\def\theoremname{Proposition}
\begin{theorem}%[Proposition 3.1]
{\it If a board has period} $m$, {\it then}
\begin{equation}
|1:2m|=L|1:m|+\beta,\quad m \geqslant 0,
\end{equation}
{\it where}
\begin{equation}
L:= |1::m|\quad\hbox{and}\quad\beta:=(-1)^{m+1}
%\prod_{k=1}^{m}b_k .
\textstyle{\prod_{k=1}^{m}b_k} .
\end{equation}
\end{theorem}


%\begin{proof}

\noindent
\textit{Proof}.
% If $\lambda\in \bar{{\cal F}}_{2m}$, then arrange $\lambda$ in two parallel rows of length $m$, breaking a domino covering
 If $\lambda\in {{\cal F}}_{2m}$, then arrange $\lambda$ in two parallel rows of length $m$, breaking a domino covering
cells $m$ and $m+1$ if necessary. Suppose that $j$ is the largest
$i$, $0\leq i\leq m$, such that neither boundary $i$ nor boundary
$i+m$ is covered by a domino (in which case,  we say that a {\it
fault} occurs at $i$; we'll assume for now that $\lambda$ has at
least one fault). Exchange the portion of the first row to the
right of boundary $j$ with the portion of the second row to the
right of boundary $j+m$ (i.e., perform a tailswap). This yields a
pair of tilings: row 1 is an ordinary $m$-tiling, but row 2 is a
Lucas $m$-tiling because it can begin and end with a half-domino.
Specifically, this happens if row 1 of the original tiling ends in
a half-domino, because the tailswap in this case moves the
half-domino to row 2 where the other half is located, as
illustrated below.
%
%\begin{center}\includegraphics[keepaspectratio,
%height=1.2in]{tailswap1.pdf}\\\footnotesize{Figure 3.1: Tiling
%before tailswap, $m=7$.}\end{center}
%
%
%\begin{figure}[h]
%\leavevmode
%\def\epsfsize#1#2{1.0#1}
%\centerline{\epsfbox{tailswap1}}
%\caption{Tiling before tailswap, $m=7$.}
%\end{figure}
%
%
\begin{figure}[!ht]
\centering
\includegraphics[width=0.55\textwidth]{tailswap1}
\caption{Tiling before tailswap, $m=7$.}
\label{fig1}
\end{figure}
%
%
%\begin{center}\includegraphics[keepaspectratio,
%height=1.2in]{tailswap2.pdf}\\\footnotesize{Figure 3.2: Tiling
%after tailswap.}\end{center}
%
%
%\begin{figure}[h]
%\leavevmode
%\def\epsfsize#1#2{1.0#1}
%\centerline{\epsfbox{tailswap2}}
%\caption{Tiling after tailswap.}
%\end{figure}
%
%
\begin{figure}[!ht]
\centering
\includegraphics[width=0.55\textwidth]{tailswap2}
\caption{Tiling after tailswap.}
\label{fig2}
\end{figure}
%

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

\begin{figure}[!ht]
\centering
\includegraphics[width=0.55\textwidth]{NoTailSwapOdd}
\caption{The fault-free configuration, $m=7$.}
\label{fig3}
\end{figure}
%
%\begin{center}\includegraphics[keepaspectratio,
%height=0.9in]{NoTailSwapEven.pdf}\\\footnotesize{Figure 3.4: The
%fault-free configuration, $m=6$.}\end{center}

\begin{figure}[!ht]
\centering
\includegraphics[width=0.55\textwidth]{NoTailSwapEven}
\caption{The fault-free configuration, $m=6$.}
\label{fig4}
\end{figure}

\vskip 0.01in
\hfill\hfill\qed

~\par

\noindent
Arranging a $(j+2m)$-tiling in two parallel rows of length $j+m$ and $m$ (flush right) and applying the preceding argument extends identity (3.2) to
\begin{equation}
|1:j+2m|=L|1:j+m| + \beta|1:j|,\quad j \geqslant 0,
\end{equation}
and starting tilings at cell $i$ gives the further generalization


\begin{equation}
|i:j+2m|=L|i:j+m| + \beta|i:j|,\quad 1\leq i\leq j.\vspace{.1 cm}
\end{equation}
(Note that $L=|1::m|=|i::i+m-1|$ for all $i \geqslant 1$, by
$m$-periodicity.)

Consider the sequence $G_n:=|1:nm|$, $n \geqslant 0$, where the associated $a_i$ and $b_i$ both have period $m$. Taking $j=nm$ in (3.4) gives a second order recurrence for $G_n$ with constant coefficients:
\def\theoremname{Proposition}
\begin{theorem}%[Proposition 3.2]
{\it If a board has period} $m$, {\it then}
\begin{equation}
G_{n+2}=LG_{n+1} + \beta G_n,\quad n \geqslant 0,
\end{equation}
{\it where} $G_0=1$ {\it and} $G_1=|1:m|$.
\end{theorem}

When all weights are unity, recurrence (3.6) reduces to
\begin{equation}
F_{(n+2)m+1}=L_mF_{(n+1)m+1} + (-1)^{m+1}F_{nm+1},
\end{equation}
which generalizes (3.1). Induction combining (2.5) when $i=1$ and
$j=n$ with recurrence (3.6) yields our first period-compression
theorem.
\def\theoremname{Theorem}
\begin{theorem}
{\it If a board has period} $m$, {\it then}
\begin{equation}
|1:nm|=\| 1:n\|,\quad n \geqslant 0,
\end{equation}
{\it where} $\| 1:n\|$ {\it is the sum of weights of} $n$-{\it
tilings using the meta-weights}
\[
\begin{array}{l@{\qquad}l}
& A_1 = |1:m|,\\
& A_2=\cdots=A_n=L=|1::m|,\\
\end{array}
\]
\noindent and
\[
\begin{array}{l@{\qquad}l}
& B_1=\cdots=B_{n-1}=\beta=(-1)^{m+1}\prod_{k=1}^{m}b_k.
\end{array}
\]
\end{theorem}
\begin{proof}
It is instructive to provide a combinatorial proof of (3.8). Note
first that $\| 1:n\|$ is a weighted sum of meta-tilings on $n$
cells, where meta-squares are themselves (weighted) $m$-bracelets
(except for cell 1, which cannot contain an out-of-phase bracelet)
and where meta-dominos each have weight $\beta$. First suppose $m$
is odd, and let $\lambda$ be such a meta-tiling of length $n$.
We'll construct, in an inductive manner, an $nm$-tiling (in
rectangular form) with period $m$ of the same weight. We'll call
meta-squares in-phase or out-of-phase depending on whether or not
they correspond to in-phase or out-of-phase bracelets.
%It combinatorial interpretation of the numerator and denominator of a finite continued
%fraction. For other combinatorial interpretations of continued fractions, see [1] as well as Chapter~4 of [2].


Let $c_i,\ i \geqslant 1$, denote the $i^{\it th}$ piece of
$\lambda$ (going from left to right). We'll consider the three
cases:
\begin{enumerate}
\item[(i)] $c_1$ is an in-phase meta-square and $c_2$ isn't an
out-of-phase meta-square; \item[(ii)] $c_1$ is an in-phase
meta-square and $c_2$ is an out-of-phase meta-square; \item[(iii)]
$c_1$ is a meta-domino.
\end{enumerate}
For (i), fill out the first row of an $n\times m$ rectangle with
the (in-phase) $m$-tiling corresponding to $c_1$. For (ii), let
$c_\ell,\ \ell \geqslant 2$, be the last out-of-phase square in a
run of out-of-phase squares directly following $c_1$. Swap (right)
tails of $c_1$ and $c_\ell$ to obtain $c^{\prime}_1$ and
$c^\prime_\ell$ (which can always be done since $m$ is odd). Note
that $c^\prime_1$ ends with a half-domino but doesn't start with
one and that $c_\ell^{\prime}$ starts with a half-domino but
doesn't end with one.
Fill out the first $\ell$ rows of an $n\times m$ rectangle %with $c_1^\prime, c_2^\prime,\ldots, c_\ell^\prime$.
with $c_1^\prime, c_2,\ldots, c_{\ell-1}, c_\ell^\prime$.

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

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

%\newline

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


\def\theoremname{Theorem}
\begin{theorem}
{\it For a board with period} $m$,
\begin{equation}
|2:nm|=|2:m|\cdot\|2:n\|,\quad n \geqslant 0,
\end{equation}
{\it with meta-weights defined as before}.
\end{theorem}
\begin{proof}
Applying (3.5) once with $i=2$, $j=nm$ and again with $i=2$,
$j=n$, $m=1$ yields (3.9), by induction on $n \geqslant 0$.
\end{proof}
Period compression takes an even simpler form for Lucas bracelets.
\def\theoremname{Theorem}
\begin{theorem}
{\it For a board with period} $m$,
\begin{equation}
|1::nm|=\|2::n+1\|,\quad n \geqslant 0,
\end{equation}
{\it with meta-weights defined as before}.
\end{theorem}
\begin{proof}
Note that both sides of (3.10) are equal when $n=0$ and $n=1$ and
can be expressed, using (2.8), as linear combinations of terms
which satisfy the same recurrence in $n$, by (3.5).
\end{proof}

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

\def\theoremname{Corollary}
\begin{theorem}%[Corollary 3.6]
{\it For all} $n,m\in \mathbb{N}$,
\begin{equation}
F_{nm} = F_m\| 2:n\|
\end{equation}
{\it and}
\begin{equation}
L_{nm} = \|2::n+1\|,
\end{equation}
{\it where the weighted sums refer to the board with constant
weights} $A_i={\it L}_m$ {\it and} $B_i=(-1)^{m+1}$ for all $i
\geqslant 2$.
\end{theorem}

\noindent \textbf{Remark.} ~Writing out (3.11) and (3.12)
explicitly, one gets the following pair of identities, the first
of which occurs in
%[6]
\cite{ref6}
and
%[7]
\cite{ref7}, the second as (V82) in Benjamin
and Quinn
%[2, p. 145]
\cite[p.~145]{ref2}:
\begin{equation}
    F_{nm}=F_m\sum_{i=0}^{\lfloor{\frac{n-1}{2}}\rfloor}(-1)^{(m+1)i}\binom{n-1-i}{i}L_m^{n-1-2i}
\end{equation}
and
\begin{equation}
    L_{nm}=\sum_{i=0}^{\lfloor{\frac{n}{2}}\rfloor}(-1)^{(m+1)i}\frac{n}{n-i}\binom{n-i}{i}L_m^{n-2i}.
\end{equation}

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

\def\theoremname{Proposition}
\begin{theorem}%[Proposition 4.1]
{\it Let} $a_1, b_1, a_2, b_2,\ldots, b_{n-1}, a_n$ {\it be any real numbers. Then}
\begin{equation}
a_1+\frac{b_1}{a_2+\frac{b_2}{\ddots+\frac{b_{n-1}}{a_n}}}=\frac{|1:n|}{|2:n|},
\end{equation}
{\it excluding division by zero. Furthermore, if} $a_i\in \mathbb{Z}$ and $b_i\in \{-1,1\}$, {\it then} $\frac{|1:n|}{|2:n|}$ {\it is a fraction in lowest terms.}
\end{theorem}
\begin{proof}
We'll prove, more generally, that
\begin{equation}
[i:j]=\frac{|i:j|}{|i+1:j|},\qquad 1\leq i \leq j\leq n,
\end{equation}
where $[i:j]$ denotes the continued fraction
\[
a_i + \frac{b_i}{a_{i+1}+\frac{b_{i+1}}{\ddots+\frac{b_{j-1}}{a_j}}}.
\]
Induct on the length, $j-i+1$, of the continued fraction, the case
in which $j=i$ clear. If $j>i$, then
\begin{eqnarray*}
[i:j] &=& a_i + \frac{b_i}{[i+1:j]}=a_i+\frac{b_i}{|i+1:j|/|i+2:j|}\\
&=&\frac{a_i|i+1:j|+b_i|i+2:j|}{|i+1:j|}=\frac{|i:j|}{|i+1:j|},
\end{eqnarray*}
by recurrence (2.4).

For the second part of the theorem, we'll show, more generally,
that $|i:n|$ and $|i+1:n|$ are relatively prime for all $i$,
$1\leq i\leq n$, by induction on $i$ starting with $i=n$, where
$n\in \mathbb{P}$ is fixed. If $i<n$, then by (2.4),
\begin{eqnarray*}
\hbox{gcd}(|i:n|,\ |i+1:n|) &=& \hbox{gcd}(a_i|i+1:n|\pm|i+2:n|,\ |i+1:n|)\\
&=& \hbox{gcd}(|i+2:n|,\ |i+1:n|)=1,
\end{eqnarray*}
completing the proof.
\end{proof}

%\newline

If $b_i=1$ for all $i$, then (4.1) reduces to (6.135) in
%[5]
\cite{ref5}.
Combining (4.1) with the period-compression theorems provides a
way of simplifying infinite periodic continued fractions.

\def\theoremname{Theorem}
\begin{theorem}
{\it Let} $a_1, a_2,\ldots$ and $ b_1, b_2,\ldots$ {\it be} $m$-{\it periodic sequences of real numbers. Then}
\begin{equation}
a_1+\frac{b_1}{a_2+\frac{b_2}{\ddots}}=\frac{1}{|2:m|}\bigg(|1:m|+\frac{\beta}{L+\frac{\beta}{L+\frac{\beta}{\ddots}}}\bigg),
\end{equation}
{\it provided that the fraction on the left converges, where} $L$
{\it and} $\beta$ {\it are as in (3.3).}
\end{theorem}
\begin{proof}
Let $n \geqslant 1$. By Theorems 3.3 and 3.4,
\[
\frac{|1:nm|}{|2:nm|}=\frac{1}{|2:m|}\bigg(\frac{\|1:n\|}{\|2:n\|}\bigg).
\]
Using (4.1) and taking the limit as $n\rightarrow \infty$ then gives (4.3).
\end{proof}



%\begin{example}
%[Example:]
\noindent \textbf{Example.} {\rm Consider a regular periodic
continued fraction: $b_i=1$ for all $i$ and let $a_1, a_2,
a_3,\ldots$ be the period-3 sequence 3, 4, 5, 3, 4, 5,$\ldots$.
Since bounded, monotonic sequences converge, all regular continued
fractions (i.e., those with $b_i=1$ and $a_i>0$ for all $i$)
converge, so we can use Theorem 4.2 with $m=3$. The relevant
calculations are $|1:3|=68$, $|2:3|=21$,} $L=|1:3|+|2:2|=72,\
\beta=1$. \rm {Therefore,}
\[
3+\frac{1}{4+\frac{1}{5+\frac{1}{\ddots}}}=\frac{1}{21}\bigg(68+\frac{1}{72+\frac{1}{72+\frac{1}{\ddots}}}\bigg).
\]
%\end{example}

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

%\newline

\vskip .2in

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

\def\theoremname{Theorem}
\begin{theorem}
{\it For all} $m,n\in \mathbb{P}$,
\begin{equation}
\frac{F_{(n+1)m}}{F_{nm}} = L_m - \frac{(-1)^m}{L_m-\frac{(-1)^m}{\ddots-\frac{(-1)^m}{L_m}}},
\end{equation}
{\it where} $L_m$ {\it appears} $n$ {\it times in the continued
fraction.}
\end{theorem}
\begin{proof}
By (3.11),
\[
\frac{F_{(n+1)m}}{F_{nm}} = \frac{F_m\| 2:n+1\|}{F_m\|2:n\|}=\frac{\|2:n+1\|}{\|3:n+1\|},
\]
where we have shifted the indices of the denominator in the last
step, which can be done since the weights are constant. Identity
(4.4) now follows from (4.2) when $a_i=L_m$ and $b_i=(-1)^{m+1}$
for all $i \geqslant 2$.
\end{proof}

%\newline

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

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


\def\theoremname{Identity}

\begin{theorem}%[Identity 5.1]
{\it For a board with constant weights} $a_i=A$ and $b_i=B$,
\begin{equation}
|1:2n+1|=A\sum\limits_{k=0}^{n}B^k|1:2n-2k|.
\end{equation}
\end{theorem}


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

%\newline

\noindent
We can generalize this to period-$m$ tilings by ``uncompressing" (5.1) :
\def\theoremname{Theorem}
\begin{theorem}
{\it For a board with period} $m$,
\begin{equation}
|2:(2n+2)m|=L\sum _{k=0}^n\beta^k|2:(2n+1-2k)m|,
\end{equation}
{\it where} $L$ {\it and} $\beta$ {\it are defined by (3.3) above.
In particular,}
\begin{equation}
F_{(2n+2)m}=L_m\sum_{k=0}^{n}(-1)^{(m+1)k}F_{(2n+1-2k)m}.
\end{equation}
\end{theorem}

\begin{proof}
%In (5.1), take $A=L$ and $B=\beta$ (starting with cell 2):
Starting tilings at cell 2 in (5.1) gives, equivalently,

\begin{equation}
|2:2n+2|=A\sum_{k=0}^{n}B^k |2:2n+1-2k|
\end{equation}
%
for a board with constant weights $a_i = A$ and $b_i = B$, $i\geq
2$. Taking $A=L$ and $B=\beta$ in (5.4) gives

%\[
\begin{equation}
\| 2:2n+2\|=L\sum^{n}_{k=0}\beta^k\| 2:2n+1-2k\|.
\end{equation}
%\]
Multiply both sides of (5.5) by $|2:m|$,
\[
|2:m|\cdot\| 2:2n+2\|=L\sum^{n}_{k=0}\beta^k|2:m|\cdot\|
2:2n+1-2k\|,
\]
and Theorem~3.4 gives (5.2). To obtain (5.3), set $a_i = b_i = 1$
for all $i$ in (5.2).
\end{proof}

%\newline

Our next identity
%involves relating weighted
relates
tilings of odd length with shorter bracelets.

\def\theoremname{Identity}
\begin{theorem}%[Identity 5.3]
{\it For a board with constant weights} $A$ {\it and} $B$,
\begin{equation}
|1:2n+1|=\sum_{k=0}^{n}(-1)^kB^k|1::2n+1-2k|.
\end{equation}
\end{theorem}

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

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


\def\theoremname{Theorem}
\begin{theorem}
{\it For a board with period} $m$,
\begin{equation}
|2:(2n+2)m|=|2:m|\sum_{k=0}^{n}(-1)^k\beta^k|1::(2n+1-2k)m|.
\end{equation}
{\it In particular,}
\begin{equation}
F_{(2n+2)m}=F_m\sum_{k=0}^{n}(-1)^{mk}L_{(2n+1-2k)m}.
\end{equation}
\end{theorem}
\begin{proof}
As in the proof of Theorem 5.2, we start our tilings at cell 2.
Taking ${A}=\hbox{\it L}$ and ${B}=\beta$ in (5.6), multiplying
both sides by $|2:m|$, and applying Theorems 3.4 and 3.5 yields
(5.7). To obtain (5.8), set $a_i = b_i = 1$ in (5.7).
\end{proof}

%\newline

\vskip .1in

The next identity is like (5.6) except that we will start with an
even-length rather than an odd-length tiling.
\def\theoremname{Identity}
\begin{theorem}%[Identity 5.5]
{\it For  a board with constant weights A and B,}

\begin{equation}
|1: 2n+2 |=(-1)^{n+1} {B}^{n+1} + \sum_{k=0}^n (-1)^k {B}^k|1::2n+2-2k|.
\end{equation}
\end{theorem}


\begin{proof}
Let $\mathcal{U}$ denote the set of all ordered pairs $(C,D)$ in
which $C$ is a bracelet (starting at cell 1) and $D$ is a line of
dominos such that the combined length of the pair is $2n+2$.
Define the sign and weight of such a pair as in the proof of
(5.6). Note that in this case, the sign-reversing involution in
the proof of (5.6) has two types of fixed points: elements of
$\mathcal{U}$ in which $C$ is an in-phase $(2n+2)$-bracelet and
$D$ is empty and the element in which $C$ is an out-of-phase
0-bracelet and $D$ contains $n+1$ dominos. Therefore,
%\[
\begin{equation}
|1:2n+2|+(-1)^{n+1}B^{n+1}=\sum_{k=0}^{n+1}(-1)^kB^k|1::2n+2-2k|,
\end{equation}
%\]
which is equivalent to (5.9).
\end{proof}

%\newline

\noindent
The same proof as before then gives


\def\theoremname{Theorem}
\begin{theorem}
{\it For a board with period} $m$,
\begin{equation}
|2:(2n+3)m|=|2:m|\bigg((-1)^{n+1}\beta^{n+1}+\sum_{k=0}^{n}(-1)^k\beta^k|1::(2n+2-2k)m|\bigg).
\end{equation}
{\it In particular,}
\begin{equation}
F_{(2n+3)m}=(-1)^{(n+1)m}F_m + F_m\sum_{k=0}^{n}(-1)^{mk}L_{(2n+2-2k)m}.
\end{equation}
\end{theorem}

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

\def\theoremname{Identity}
\begin{theorem}%[Identity 5.7]
{\it For a board with constant weights} $A$ {\it and} $B$,

\begin{equation}
|1::2n+3|=AB^{n+1}+A\sum^{n}_{k=0}B^k|1::2n+2-2k|.
\end{equation}
\end{theorem}


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

%\newline

\noindent Letting $A=L$ and $B=\beta$, and applying Theorem~3.5 to
both sides of (5.13), then gives



\def\theoremname{Theorem}
\begin{theorem}
{\it For a board with period} $m$,
\begin{equation}
|1::(2n+3)m|=L\beta^{n+1}+L\sum^{n}_{k=0}\beta^k|1::(2n+2-2k)m|.
\end{equation}
{\it In particular,}
\begin{equation}
L_{(2n+3)m}=(-1)^{(n+1)(m+1)}L_m+L_m\sum^{n}_{k=0}(-1)^{(m+1)k}L_{(2n+2-2k)m}.\vspace{.1cm}
\end{equation}
\end{theorem}

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

Finally, note that the $m=1$ case of (5.3), (5.8), (5.12), and
(5.15) is the case $A=B=1$ of (5.1), (5.6), (5.9), and (5.13),
respectively. The methods of this section then illustrate a way to
generalize certain Fibonacci/Lucas identities. For instance, the
well-known identity
\begin{equation}
F_{2n+1}=1+\sum_{k=1}^nF_{2k}
\end{equation}
is easily generalized to the constant-weight identity
\begin{equation}
|1:2n|=B^n+A\sum_{k=1}^nB^{n-k}|1:2k-1|.
\end{equation}
Taking $A=L$, $B=\beta$ in (5.17), multiplying by $|2:m|$, and applying Theorem 3.4 then gives
\begin{equation}
|2:(2n+1)m|=\beta^n|2:m|+L\sum^{n}_{k=1}\beta^{n-k}|2:2km|,
\end{equation}
for $m$-periodic tilings, and, in particular,
\begin{equation}
F_{(2n+1)m}=(-1)^{(m+1)n}F_m+L_m\sum^{n}_{k=1}(-1)^{(m+1)(n-k)}F_{2km},
\end{equation}
which generalizes (5.16).

\begin{thebibliography}{[99]}

\bibitem{ref1}
A. Benjamin, J. Quinn, and F. Su, Counting on continued fractions, {\it Math. Mag.} {\bf 73} (2000), 98--104.

\bibitem{ref2}
A. Benjamin and J. Quinn, {\it Proofs that Really Count: The Art of Combinatorial Proof}, The Dolciani Mathematical Expositions, 27, Mathematical Association of America, 2003.

\bibitem{ref3}
L. Carlitz, Fibonacci notes 3: $q$-Fibonacci numbers, {\it Fibonacci
Quart}. {\bf 12} (1974), 317--322.

\bibitem{ref4}
J. Cigler, $q$-Fibonacci polynomials, {\it Fibonacci Quart.} {\bf 41}
(2003), 31--40.

\bibitem{ref5}
R. Graham, D. Knuth, and O. Patashnik, {\it Concrete Mathematics:
A Foundation for Computer Science}, 2nd Edition,
Addison-Wesley, 1989.

\bibitem{ref6}
R. Johnson, {\it Matrix methods for Fibonacci and related
sequences}, preprint available at
\href{http://maths.dur.ac.uk/dma0rcj/PED/fib.pdf}{\tt http://maths.dur.ac.uk/dma0rcj/PED/fib.pdf}, 2003.

\bibitem{ref7}
J. McLaughlin, Combinatorial identities deriving from the $n^{th}$
power of a $2 \times 2$ matrix, {\it Integers} {\bf 4} (2004),
\#A19.  Available from
\href{http://www.integers-ejcnt.org/vol4.html}{\tt http://www.integers-ejcnt.org/vol4.html}.

\bibitem{ref8}
M. Shattuck, 
Tiling proofs of some Fibonacci-Lucas identities,
{\it Integers} {\bf 8} (1) (2008), \#A18.    Available from
\href{http://www.integers-ejcnt.org/vol8.html}{\tt http://www.integers-ejcnt.org/vol8.html}.

\bibitem{ref9}
M. Shattuck and C. Wagner, A new statistic on linear and circular
$r$-mino arrangements, {\it Electron. J. Combin.} {\bf 13} (2006),
\#R42.  Available from
\href{http://www.combinatorics.org/Volume_13/Abstracts/v13i1r42.html}{\tt http://www.combinatorics.org/Volume\_13/Abstracts/v13i1r42.html}.

\bibitem{ref10}
R. Stanley, {\it Enumerative Combinatorics, Vol.~I,} Wadsworth and Brooks/Cole, 1986.

\bibitem{ref11}
S. Vajda, {\it Fibonacci and Lucas Numbers}, {\it and the Golden Section}: {\it Theory and Applications}, John Wiley \& Sons, Inc., 1989.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\em Mathematics Subject Classification:} Primary
11B39; Secondary 05A19.

\noindent {\em Keywords:} continued fraction, polynomial
generalization, Fibonacci number, Lucas number, tiling.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 27 2009;
revised version received August 2 2009. 
Published in {\it Journal of Integer Sequences}, August 30 2009.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

.