<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}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}

\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

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

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}

\begin{document}

\begin{center}
\includegraphics[width=4in]{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf 
Tiling a $2 \times n$ Board with Dominos and \\
\vskip .1in
$L$-Shaped Trominos
}
\vskip 1cm
\large
Gregory Dresden\\ 
Department of Mathematics\\
Washington \&amp; Lee University \\
Lexington, VA 24450 \\
USA\\
\href{mailto:dresdeng@wlu.edu}{\tt dresdeng@wlu.edu} \\
\ \\
Michael Tulskikh\\
East Mountain High School\\
Sandia Park, NM 87047\\
USA\\
\href{mailto:tulskikhmichael@gmail.com}{\tt tulskikhmichael@gmail.com}\\ 
\end{center}

\vskip .2 in

\begin{abstract} 
We count the number of ways to tile  $2 \times n$ rectangles and bracelets
using dominos and $L$-shaped trominos. We show that these $2 \times n$
tilings can be related to $1 \times n$ tilings with squares, dominos,
and two colors of $k$-minos for $k \geq 3$, and we discover some new
identities for old sequences.
\end{abstract}

\section{Introduction}

How many ways are there to tile a $2 \times n$ board? Naturally, it all depends on the tiles we use. 
With just dominos, we obtain the familiar Fibonacci sequence. 
For dominos and squares, 
we look to McQuistan and Lichtman \cite{ML} and the
sequence \seqnum{A030186} from the {\em On-Line Encyclopedia of Integer Sequences} (OEIS) \cite{Sloan}, and  for colored dominos and squares we have papers by  Kahkeshani \cite{Kah}, 
Kahkeshani and Arab \cite{KA}, and Katz and Stenson \cite{KS}. 
Squares, dominos, and (straight) trominos were covered by Haymaker and Robertson \cite{HR} and are counted by  
\seqnum{A278815}.
For $L$-shaped trominos and squares, we can turn to to a recent paper by Chinn, Grimaldi, and Heubach \cite{CGH} as seen in
\seqnum{A077917}. 
An interesting variation on the $2 \times n$ board was given by Bodeen, Butler, Kim, Sun, and Wang \cite{BBKSW} who looked at tiling a 
$2 \times n$ lozenge with triangles, giving nice combinatorial interpretations to 
the sequences 
\seqnum{A000129},
\seqnum{A000133},
\seqnum{A097075},
and 
\seqnum{A097076}.

In this paper, we count the tilings of the $2 \times n$ board using a slightly different collection of tiles:
we use dominos and $L$-shaped trominos. We derive a number of results and identities for these kinds of tilings. In addition, we are able to relate this question to the problem of tiling a $1 \times n$ board with squares, dominos, and colored $k$-minos, and this allows us to establish 
new identities for the sequences 
\seqnum{A052980},
\seqnum{A080204},
and
\seqnum{A332647}.
Our work follows closely the tiling techniques studied by Benjamin and
Quinn in their book, {\it Proofs That Really Count} \cite{BQ}.


To begin with, let us define $a_n$
to be the number of different ways to tile a
$2 \times n$ board
with dominos and ``bent trominos" in the shape of the letter $L$ (henceforth, we will call these $L$-shaped trominos, or simply ``trominos" if it is clear from the context). It is convenient to define $a_0 = 1$. As an example, Figure \ref{f1Label} gives all five possible tilings for $n=3$, thus demonstrating that $a_3 = 5$. The trominos are shaded for ease of reading.
\begin{figure}[H]
\centering
    \includegraphics[scale=0.4]{f1.eps}
    \caption{Demonstrating that $a_3 = 5$.}
    \label{f1Label}
\end{figure}

A few minutes of work with pencil and paper will give us the
sequence $1, 1, 2, 5, 11, 24, 53, \dots $ (starting with $a_0 = 1$), and  
in the next section we will show that this sequence equals
 \seqnum{A052980}.
But first, inspired by a similar coloring trick in Chinn, Grimaldi, and Heubach's article \cite{CGH}, we show that 
we can reduce this $2 \times n$ tiling problem
to a $1 \times n$ problem: our numbers $a_n$ are exactly the number
of ways to tile a $1 \times n$ strip with 
(white) squares, (white) dominos, and  colored 
({\color{red}red} or
{\color{blue}blue})
$k$-minos
of arbitrary length $k \geq 3$.
To see this equivalence, first
note that any $2 \times n$ tiling can be broken along vertical lines into
{ indivisible segments}. Two examples are given here in Figure \ref{f1bLabel}, with the trominos shaded for easy visibility.
\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{f1b.eps}
\caption{Breaking  a $2 \times n$ tiling along vertical lines.}
\label{f1bLabel}
\end{figure}


By parity, each indivisible segment must contain an even number of trominos. Furthermore, each tromino induces a single vertical break in the tiling, as seen in Figure \ref{f1cLabel} (we will explain the red and blue coloring in Figure \ref{f1cLabel} in a moment).
\begin{figure}[h]
\centering
\includegraphics[scale=0.4]{f1c.eps}
\caption{Trominos that can appear at the ends of indivisible segments.}
\label{f1cLabel}
\end{figure}


Hence, we conclude that for each indivisible segment, it either has {\em no} trominos, or it has {\em exactly two} trominos with one at each end of
 the segment. As seen  in Figure \ref{f1cLabel}, a tromino at the {\em beginning} of an indivisible segment is either oriented
 like the letter ``r" (which we have colored 
 {\color{red}red})
  or 
 like the letter ``b" (which we have colored {\color{blue}blue}). Likewise, a tromino at the {\em end} of an indivisible segment must be one of the two 
 grey trominos at the right of Figure \ref{f1cLabel}.
 Also, an indivisible segment with {\em no} trominos must begin with (and hence must be  equal to)
  either a single vertical domino or two stacked horizontal dominos; any
   longer and the segment would break. 
   
These insights now allow us to establish the
    following relationship between our $2 \times n$ tilings and our 
$1 \times n$ tilings. After breaking up a $2 \times n$ tiling into
 indivisible segments, and after coloring each tromino at the beginning of each  segment either  {\color{red}red} or {\color{blue}blue} depending on its orientation as seen in Figure \ref{f1cLabel}, we
 map  
 {\color{red} each  segment of length $k$ beginning with a red tromino} to a {\color{red}red $k$-mino} and likewise 
 {\color{blue} each segment of length $k$ beginning with a blue tromino} to a {\color{blue}blue $k$-mino}, each single vertical domino to a white square, and each aligned 
 pair of horizontal doninos to a white domino. We give here in Figure \ref{f1dLabel} an example based on the tilings in Figure \ref{f1bLabel}. 
\begin{figure}[H]
\centering
\includegraphics[scale=0.4]{f1d.eps}
\caption{Mapping from our $2 \times n$ tilings to our to $1 \times n$ tilings.}
\label{f1dLabel}
\end{figure}


To reverse the mapping, we apply the following algorithm to a $1 \times n$ tiling: we replace each square with a vertical domino, we replace each domino with two stacked horizontal  dominos, and we replace each red $k$-mino with a segment that begins with the red tromino from Figure \ref{f1cLabel} followed by $k-3$ staggered horizontal dominos and then one of the two grey trominos on the right of Figure \ref{f1cLabel}. (A similar procedure is used for replacing each blue $k$-mino.) We then ``uncolor" each colored tromino, repainting the red and blue trominos with a neutral grey.  We give an example in Figure \ref{f1eLabel}
\begin{figure}[H]
\centering
\includegraphics[scale=0.4]{f1e.eps}
\caption{Mapping from our $1 \times n$ tilings to our to $2 \times n$ tilings.}
\label{f1eLabel}
\end{figure}


It is clear that we have a one-to-one and onto mapping between our 
$2 \times n$ tilings and our $1 \times n$ tilings. 


As an aside, we note that 
other types of tilings that use both single-color and multi-colored tiles have
interesting connections to seemingly-unrelated sequences. For example, Milan Janjic 
comments in \seqnum{A001333} in the OEIS that the numerators of the continued fraction expansion for $\sqrt{2}$ also count the number of tilings using single-color squares and two colors of $k$-minos for $k\geq 2$. As for tilings with single-color squares and {\em three} colors of $k$-minos for $k \geq 2$, this gives us
\seqnum{A026150} which is related to $\sqrt{3}$.
Thus, we should not be surprised to learn that  our tiling method
(using single-color squares, single-color dominos, and two colors of $k$-minos for $k\geq 3$) 
also turns up in the OEIS, and that is the subject of the next section.


\section{Establishing that our tiling sequence equals A052980}

The sequence 
\seqnum{A052980}, defined in the OEIS
as the sequence with generating function
$(1-x)/(1-2x - x^3)$, has initial values 1, 1, 2, 5, 11
and recurrence formula $x_n = 
2x_{n-1} + x_{n-3}$. We now show (in Corollary \ref{simplereccurence} to  Theorem \ref{tilingproof}) that our sequence $(a_n)_{n \geq 0}$ has the same recurrence, and since it also has the same initial values then it must equal
\seqnum{A052980}.

\begin{theorem}\label{tilingproof}
For $n \geq 3$, we have 
\begin{equation}\label{tilingproofeqn}
a_n = a_{n-1} + a_{n-2}
+ 2 \left(a_{n-3} + a_{n-4} + \cdots + a_1 + a_0 \right).
\end{equation}
\end{theorem}


\begin{proof}
In the spirit of Benjamin and Quinn, we ask: how many ways can we tile a 
 board of length $n$ using squares, dominos, 
 and red or blue $k$-minos with $k\geq 3$?
On the one hand, by our equivalence discussed in the 
introduction there are $a_n$ ways to tile it.
On the other hand, we can condition based on the first tile. If it is a square, there are $a_{n-1}$ ways to tile the remaining length of $n-1$.
Likewise, if the first tile is a domino, we have 
$a_{n-2}$ ways. 
Finally, if the tiling begins with a $k$-mino for $k \geq 3$, we recall that
each $k$-mino has two possible colorings, and can also be any length greater than or equal to three. Therefore, any tiling starting with a $k$-mino has $2 a_{n-k}$ ways to tile the rest of the strip. Summing up all the different ways, 
and comparing it to $a_n$, we have our desired equation (\ref{tilingproofeqn}).
\end{proof}

\begin{corollary}\label{simplereccurence}
For $n \geq 3$, we have
\begin{equation}\label{simplereccurenceeqn}
a_n = 2a_{n-1} + a_{n-3}.
\end{equation}
\end{corollary}


\begin{proof}
Since our first few values for $a_n$ starting with $a_0$ are $1, 1, 2, 5, \dots$, then the corollary clearly holds for $n=3$. As for $n \geq 4$, we use equation (\ref{tilingproofeqn}) from Theorem \ref{tilingproof} to state that
\begin{align}
a_n &amp;= a_{n-1} + a_{n-2} + 2\sum_{i=0}^{n-3}a_{i},\label{cor_eqn1}\\
\intertext{which also implies}
    a_{n-1} &amp;= a_{n-2} + a_{n-3} + 2\sum_{i=0}^{n-4}a_{i}.\label{cor_eqn2}\\
\intertext{Subtracting  equation (\ref{cor_eqn2}) from equation (\ref{cor_eqn1}),
and noticing that just about everything cancels, we get}
    a_n - a_{n-1} &amp;= a_{n-1} + a_{n-3}. \nonumber
\end{align}
Therefore, $a_n = 2a_{n-1} + a_{n-3}$, as desired.
\end{proof}

Thanks to Corollary 
\ref{simplereccurence} above, 
we can now conclude that our
sequence $(a_n)_{n \geq 0}$ is indeed the
sequence \seqnum{A052980}, as both have the same
initial values and the same recurrence formula. 

It is worth noting that Corollary \ref{simplereccurence}
can be proved directly using the following clever tiling argument: on the one hand, there are $a_n$ ways to tile a strip of length $n$ with squares, dominos, and red or blue $k$-minos. On the other hand, we can look at the first tile of our strip of length $n$. 
\begin{enumerate} 
\item  If a square, remove it to get a strip of length $n-1$.
\item  If a domino, replace it with a square to get an $n-1$ tiling that {\em begins with a square}.
\item  If a red 3-mino, remove it to get a strip of length $n-3$. 
\item  If a blue 3-mino, replace it with a domino to get an $n-1$ tiling that {\em begins with a domino}.
\item  If a (red or blue) $k$-mino for $k\geq 4$, reduce the length of this $k$-mino by one to get an $n-1$ tiling that {\em begins with a (red or blue) $k$-mino}.
\end{enumerate} 
To sum up, part 1 gives us $a_{n-1}$ tilings, part 3 gives us $a_{n-3}$ tilings, and parts 2, 4, and 5 add up to give us another $a_{n-1}$. In total, we have $a_{n-1} + a_{n-3} + a_{n-1}$, and
 since this must equal $a_n$ then we have our desired equation (\ref{simplereccurenceeqn}). 


\section{Additional identities}


Benjamin and Quinn's book \cite{BQ} is full of  ingenious tiling proofs for
various identities.
Since our sequence $(a_n)_{n \geq 0}$ is also a tiling sequence, we 
can use Benjamin and Quinn's methods (just as we did in the proof of Theorem 
\ref{tilingproof}) to come up with new identities for our sequence. 
For example, this next formula comes from looking at where the tiling breaks into two. 
\begin{theorem}\label{generalsplit}
For $n, m \geq 2$, we have
\begin{equation}\label{generalspliteqn}
a_{m+n} = a_{m}a_{n} - a_{m-1}a_{n-1} + \frac{1}{2}(a_{m+2} - a_{m+1} - a_m)(a_{n+2} - a_{n+1} - a_n).
\end{equation}
\end{theorem}
\begin{proof} Just like in our proof of Theorem \ref{tilingproof}, we ask: how many ways
can we tile a board of length $m+n$ with 
squares, dominos, and red or blue $k$-minos with
$k\geq 3$? On the one hand, this is simply
$a_{m+n}$. On the other hand, we can look at what happens between cell $m$ and cell $m+1$. There are three options.

\begin{enumerate}
\item   The tiling breaks between cell $m$ and $m+1$. 
See Figure \ref{f5Label}.
\begin{figure}[H]
\centering
    \includegraphics[scale=0.5]{f5.eps}
\caption{A break between cells $m$ and $m+1$.}
\label{f5Label}
\end{figure}


In this case, it is easy to see that there are 
$a_m$ tilings on the left of the break, and $a_n$ tilings on the right, giving $a_{m}a_{n}$ ways to tile this board.

\item   There is a domino covering the break between cells $m$ and $m+1$.
See Figure \ref{f5bLabel}.
\begin{figure}[H]
\centering
    \includegraphics[scale=0.5]{f5b.eps}
\caption{Covering the break with a domino.}
\label{f5bLabel}
\end{figure}

Using the same argument as above, we can see that the total number of ways to tile this board is $a_{m-1}a_{n-1}$.

\item There is  a red or blue $k$-mino covering the break between cells $m$ and $m+1$. 
\begin{figure}[H]
\centering
     \includegraphics[scale=0.5]{f5d.eps}
\caption{Covering the break with a red or blue $k$-mino.}
\label{f5dLabel}
\end{figure}
 
As seen in Figure \ref{f5dLabel}, there are $a_{m-i}$ tilings to the left of the central $k$-mino, then two possible colorings 
 (red or blue) for the $k$-mino, and then $a_{n-j}$ tilings to the right, giving $a_{m-i}\cdot 2 \cdot  a_{n-j}$ tilings. We now imagine central $k$-minos of different sizes, and we see that  $i$ can range from 1 to $m$ and likewise $j$ can range from 1 to $n$, but we note that we can not have both $i$ and $j$ equal to 1 at the same time, as this would imply that the central $k$-mino would be of length $2$ instead of the required $3$ or above. Hence, the total number of tilings in this configuration can be written as 
\begin{equation}\label{3sum}
\left(2\cdot \sum_{i=1}^{m}{a_{m-i}} \cdot  \sum_{j=1}^{n}{a_{n-j}}\right)
 \ - \ 2 a_{m-1}a_{n-1},
\end{equation}
where we have included, and then removed, the forbidden case where $i = j = 1$. 
 \end{enumerate}
 
We have now covered all possible cases. Since $a_{m+n}$ must equal the sum of the 
expressions from the above three options, we have
\begin{align}
    a_{m+n} &amp;= a_{m}a_{n} \ + \ a_{m-1}a_{n-1} \ + \ 
    	\left(2\cdot \sum_{i=1}^{m}{a_{m-i}} \cdot  \sum_{j=1}^{n}{a_{n-j}}\right)
 - 2 a_{m-1}a_{n-1},\nonumber \\
     &amp;= a_{m}a_{n} - a_{m-1}a_{n-1} +  2\sum_{i=1}^{m}{a_{m-i}}\sum_{j=1}^{n}{a_{n-j}}.\label{lastsum}
\end{align}
For the sum $\sum_{i=1}^{m}a_{m-i}$ in equation (\ref{lastsum}), we replace $i$ with $m-i$ to obtain $\sum_{i=0}^{m-1}a_{i}$. We note that Theorem
 \ref{tilingproof} tells us that $a_{m+2} = a_{m+1} + a_m + 2\sum_{i=0}^{m-1}a_{i}$ and so we see that  our sum $\sum_{i=0}^{m-1}a_{i}$ can be replaced with $\frac{1}{2} \left(a_{m+2} - a_{m+1} - a_m\right)$. This, along with a similar substitution for $\sum_{j=1}^{n}a_{n-j}$, allows us to simplify equation (\ref{lastsum}) to obtain our desired equation (\ref{generalspliteqn}). 
\end{proof} 




The following corollary is a nice variant on Theorem \ref{generalsplit}.
\begin{corollary}
For $n \geq 2$, we have 
$\displaystyle 
a_{2n}= a_{n}^2 - a_{n-1}^2 + \frac{1}{2} \Big( 
a_{n} + a_{n-1} + a_{n-2} \Big)^2.
$\end{corollary}

\begin{proof}
If we replace $m$ with $n$ in equation (\ref{generalspliteqn}) of Theorem 
\ref{generalsplit}, we have
\begin{equation}\label{a2n1}
a_{2n} = a_{n}^2 - a_{n-1}^2 + \frac{1}{2}(a_{n+2} - a_{n+1} - a_n)^2.
\end{equation}
We can now use Corollary \ref{simplereccurence} to replace the $a_{n+2}$ in 
equation (\ref{a2n1}) with $2a_{n+1} + a_{n-1}$, giving us 
\begin{equation}\label{a2n2}
a_{2n} = a_{n}^2 - a_{n-1}^2 + \frac{1}{2}(a_{n+1} - a_{n} + a_{n-1})^2,
\end{equation}
and we again use Corollary \ref{simplereccurence} but this time to replace the $a_{n+1}$ in 
equation (\ref{a2n2}) with $2a_{n} + a_{n-2}$, which gives us our desired formula. 
\end{proof}


We remind our reader  of the  Fibonacci numbers, which are  traditionally defined as $F_0=0, F_1=1$, and 
$F_n = F_{n-1} + F_{n-2}$. If we define $f_n = F_{n+1}$
then the sequence $(f_n)_{n \geq 0}$ is exactly the number of ways to tile a board of
length $n$ with squares and dominos \cite{BQ}. 
With this in mind, we present the following theorem on weighted sums.

\begin{theorem}\label{fibonacci_theorem}
For $n \geq 3$, we have
\begin{align}
a_n &amp;= F_{n+1} + 
2\sum_{i=0}^{n-3} a_i \left( F_{n-i} - 1 \right),\label{weighteqn1}\\
\intertext{and for $n \geq 0$, we have}
a_{n+2} &amp;=  F_{n+1} + a_{n+1} + 2 \sum_{i=0}^{n}a_i F_{n-i}.\label{weighteqn2}
\end{align}
\end{theorem}

\begin{proof}
As before, we count up the total number of tilings of a strip of length $n$ and set it equal to $a_n$ to obtain our formula. We recall that we have $n \geq 3$.
 
If a particular tiling has no $k$-minos, it must be entirely made up of squares and dominos. By our observation earlier, this corresponds to $f_n = F_{n+1}$ unique tilings.
 (Recall that when we talk about $k$-minos we always assume that $k\geq 3$).

Suppose, instead, that the tiling has at least one $k$-mino. If we
look at the last or right-most $k$-mino, we see that this splits the length-$n$ tiling into a tiling of length $i$ (to the left of the $k$-mino) with squares, dominos and $k$-minos, followed by the red or blue $k$-mino in the middle, and ending with a tiling of length $n-i-k$ (to the right of the $k$-mino) with just squares and dominos.  An illustration is shown in Figure \ref{f6Label}.
\begin{figure}[H]
\centering
    \includegraphics[scale=0.5]{f6.eps}
\caption{Tiling a board based on the location of the last (red or blue) $k$-mino.}
\label{f6Label}
\end{figure}


There are exactly $a_i$ ways to tile everything to the left of that last $k$-mino, there are two possible colors (red or blue) for that last $k$-mino, and there are $f_{n-i-k}$ ways to tile everything to the right of that last $k$-mino (because to the right we have only squares and dominos). Hence, the particular configuration in Figure \ref{f6Label} has $a_i \cdot 2 \cdot f_{n-i-k}$ tilings. 

We now imagine fixing $i$ at some permissible value, 
$0 \leq i \leq n-3$. Since $k\geq 3$, then $n-i-k$ ranges from 
$0$ to $n-i-3$, giving us 
\[
a_i\cdot 2 \cdot f_0 \ + \ a_i\cdot 2 \cdot f_1 \ + \  a_i\cdot 2 \cdot f_2 \ + \ \cdots \ + \  a_i \cdot 2 \cdot f_{n-i-3}
\]
tilings for the configurations in Figure \ref{f6Label} for this fixed  value of $i$. In other words,  we have
$a_i\cdot 2 \cdot(f_0 + f_1 + f_2 + \cdots + f_{n-i-3})$ ways to tile the board in Figure \ref{f6Label}. 

We now sum up these values over $i$ as $i$ ranges from $0$ to $n-3$, and we have
\begin{equation}\label{consecFib}
    \sum_{i=0}^{n-3}a_i\cdot 2 \cdot (f_0 + f_1 + f_2 + \cdots + f_{n-i-3}).
\end{equation}
Thanks to a well-known identity, that sum of consecutive Fibonacci numbers in equation (\ref{consecFib}) can be replaced with $f_{n-i-1} - 1$. If we make this substitution, and also add in $f_n$ (coming from the tilings with no $k$-minos) we obtain this total count for all tilings,
\begin{equation}\label{totalcount}
    a_n = f_n + 2\sum_{i=0}^{n-3}a_i(f_{n-i-1} - 1),
\end{equation}
and if we use the identity $f_n = F_{n+1}$ on equation (\ref{totalcount}) we have  
\begin{equation}\label{firstTheorempart}
    a_n = F_{n+1} + 2\sum_{i=0}^{n-3}a_i(F_{n-i} - 1),
\end{equation}
and this is a perfect match for equation (\ref{weighteqn1}) from the first part  of the theorem. 

It is now a simple matter to arrive at equation (\ref{weighteqn2}) from the  second part of 
the theorem. We substitute equation (\ref{tilingproof}) from 
 Theorem \ref{tilingproof} into 
equation (\ref{firstTheorempart}) to obtain
\begin{align}
    a_n &amp;= F_{n+1} + 2\sum_{i=0}^{n-3}a_iF_{n-i} 
    \ - \ (a_n - a_{n-1} - a_{n-2})\nonumber \\
        &amp;= F_{n+1} + 2\sum_{i=0}^{n}a_iF_{n-i} 
    \ - \ 2(a_{n-2}F_2 + a_{n-1}F_1 + a_n F_0)\ - \ (a_n - a_{n-1} - a_{n-2})\nonumber \\
     &amp;= F_{n+1} + 2\sum_{i=0}^{n}a_iF_{n-i} 
    \ - \ (a_n + a_{n-1} + a_{n-2}).\label{lastie}
\end{align}
From equation (\ref{lastie}) we have 
$2a_n + a_{n-1} + a_{n-2}= F_{n+1} + 2\sum_{i=0}^{n}a_iF_{n-i}$, and by applying Corollary \ref{simplereccurence} twice we can replace the $2a_n + a_{n-1} + a_{n-2}$ on the left with $a_{n+2} - a_{n+1}$, which gives us 
the formula
\begin{equation}\label{6bformula}
a_{n+2} = F_{n+1} + a_{n+1} + 2\sum_{i=0}^{n}a_iF_{n-i},
\end{equation}
and this matches equation (\ref{weighteqn2}). 
Finally, while  our proof of (\ref{6bformula}) was only valid for  $n \geq 3$, it is easy to check the cases $n=0, 1, 2$ by hand and so our equation (\ref{6bformula}) actually holds for all $n\geq 0$, as desired.
\end{proof}



While Theorem \ref{fibonacci_theorem} involved weighted sums with Fibonacci numbers, this next theorem presents a weighted sum with powers of 2. 


\begin{theorem}\label{powersof2}
For $n \geq 0$, we have 
\begin{equation}\label{powersof2eqn}
\displaystyle a_{n+3} = 2^{n+2} + \sum_{i=0}^{n} a_i 2^{n-i}.
\end{equation}
\end{theorem}


\begin{proof}
For now, let us assume that $n \geq 3$. Just as in the proof of 
Theorem \ref{fibonacci_theorem}, we consider a strip of length $n$, but this
time we condition on the location of the last 
blue $k$-mino.
If there are no blue $k$-minos, we take all the red $k$-minos and color them white to match the white squares and white dominos; this means that our
 tiling now consists of single-color (white) tiles of arbitrary length. In order to find the number of ways to tile such a board, consider the  length-$n$ board in Figure \ref{untiled}.
\begin{figure}[H]
\centering
    \includegraphics[scale=0.5]{f7.eps}
\caption{A board of length $n$.}
\label{untiled}
\end{figure}
Note that there are exactly $n-1$ interior vertical ``dividing lines". We can create unique tiling patterns by simply removing (some of the) dividing lines to produce tiles of arbitrary length. For each dividing line, there are only two options: keep it or remove it. Making this choice for every dividing line  in Figure \ref{untiled} gives $2^{n-1}$ possible tiling patterns.

Next, we suppose there is at least one blue $k$-mino, and we imagine that it starts at cell $i+1$ and extends a distance $k$ to the right, as seen in Figure \ref{f8Label}.
\begin{figure}[H]
\centering
\includegraphics[scale=0.5]{f8.eps}
\caption{Counting tilings based on location and length of last blue $k$-mino.}
\label{f8Label}
\end{figure}


There are exactly $a_i$ ways to tile everything to the left of that last blue $k$-mino. If $i+k=n$, then there is nothing to the right of that last blue $k$-mino and so we have $a_i$ tilings overall. Assuming now that $i+k&lt;n$, then to count the tilings to the right of that last blue $k$-mino
 we apply the same technique as at the beginning of the proof: we assign all tiles to the right of that last blue $k$-mino to be white so that we now are counting all tilings
consisting of single-color (white) tiles of arbitrary length within a total length of $n-i-k$, giving us  $2^{n-i-k-1}$ such tilings. In total, then,
for Figure \ref{f8Label} we have 
$a_i$ tilings for $i+k=n$ and $a_i\cdot 2^{n-i-k-1}$ tilings for $i+k&lt;n$.


It remains to carefully sum our number of tilings  over the permissible values of $i$ and $k$. While $i$ can run from 0 to $n-3$, and $k$ can run from 3 to $n-i$, we need to separate the  special case when $i+k=n$ from the general case when $i+k&lt;n$. The following list gives all possible options.
\begin{enumerate} 
\item  When $i+k=n$, we have
just $a_i$ tilings for each case, and when we sum over these permissible values of $i$
we get 
$\displaystyle \sum_{i=0}^{n-3} a_i$ tilings. 
\item  When $i + k &lt; n$, which occurs when $0\leq i \leq n-4$ and $3\leq k \leq n-i-1$,  we have $a_i\cdot 2^{n-i-k-1}$ tilings. Summing this over these values of $i$ and $k$ gives us 
\[
\displaystyle \sum_{i=0}^{n-4}\, \sum_{k=3}^{n-i-1} a_i \cdot 2^{n-i-k-1}
\]
tilings. We factor out the $a_i$ and we re-index the inner sum by letting $j=n-i-k-1$ to obtain
\[
\displaystyle \sum_{i=0}^{n-4} a_i \, \sum_{j=0}^{n-i-4}  2^{j},
\] 
and we sum up that inner sum to obtain
$\displaystyle 
     \sum_{i=0}^{n-4} a_i \left(2^{n-i-3} - 1\right).
     $
\end{enumerate} 
Summing up the terms from these two cases gives us 
$\displaystyle  \sum_{i=0}^{n-3} a_i \left(2^{n-i-3}\right)$. When we add in the 
$2^{n-1}$ from the case where there are no blue $k$-minos, and when we compare this total to $a_n$, we obtain
\begin{align*}
    a_n &amp;= 2^{n-1} + \sum_{i=0}^{n-3}a_i2^{n-i-3} \qquad \mbox{for $n \geq 3$.}\\
\intertext{Replacing $n$ with $n+3$ gives us}
    a_{n+3} &amp;= 2^{n+2} + \sum_{i=0}^{n}a_i2^{n-i} \qquad\ \ \  \mbox{for $n \geq 0$},
\end{align*}
which is our desired equation (\ref{powersof2eqn}) in the statement of Theorem \ref{powersof2}. 
\end{proof}



\section{Bracelet numbers}
Recall that the Fibonacci numbers $f_n$ count the number of ways to tile a $1 \times n$ strip with squares and dominos, and  likewise
the Lucas numbers 
count the number of ways to tile a $1 \times n$ {\em bracelet} with squares and dominos \cite{BQ}. 
Inspired by this relationship, we now ask: what are 
the corresponding ``bracelet numbers" for our
sequence $(a_n)_{n \geq 0}$?

Surprisingly, there are two answers to this question! It all depends on whether we view $a_n$ 
as counting the tilings of 
a $2 \times n$ strip 
with dominos and trominos (which was our definition of $a_n$), or 
as counting the tilings of 
a $1 \times n$ strip with squares, dominos, and red/blue $k$-minos (which, as we showed in the Introduction, is exactly the same number). 
This equivalence between the $2 \times n$ and the $1 \times n$ situations isn't quite perfect when we turn to  bracelets, because 
while every $2 \times n$ {\em strip} with dominos and trominos can be broken 
along vertical lines into indivisible segments 
(which we then map to squares, dominos, and red or blue $k$-minos), 
when $n$ is even there are exactly two tilings on 
a $2 \times n$ {\em bracelet} which can {\em not} be broken; these are the two tilings with unaligned horizontal dominos that go 
``all the way around the bracelet". (Imagine one such configuration; if we 
rotate the bracelet by one cell we will have the other configuration). When $n$ is odd this configuration is not possible thanks to parity.

With this in mind, we define  $b_n'$ to be the number of ways to tile a $2 \times n$ bracelet with dominos and trominos, 
and $b_n$ to be the number of ways to tile a $1 \times n$ bracelet
with squares, dominos, and red or blue $k$-minos. By our discussion above, $b_n' = b_n + 2$ for $n$ even and $b_n' = b_n$ for $n$ odd. In what follows, we will focus on $b_n$.


Once again, a few minutes with pencil and paper give the initial values $1, 3, 10, 23, \dots$ for $b_n$ (starting with $b_1 = 1$), 
and we will show in a moment that this
is the sequence 
\seqnum{A080204}
(which, interestingly enough, comes from
a Kolakoski sequence which has nothing to do with tilings).
To show this equality, we need to begin with the following theorem.




\begin{theorem}\label{eight}
For $a_n$ and $b_n$ defined as above, we have
\begin{equation}\label{eighteqn}
b_n = a_n + a_{n-2} + 2\sum_{k=3}^n (k-1)a_{n-k}
\end{equation}
\end{theorem} 

\begin{proof}
Inspired by the proofs of Theorems 
\ref{tilingproof} and \ref{generalsplit}, we
count the number of ways to tile a
$(1 \times n)$ bracelet using squares, dominos, and red or blue $k$-minos, and we set that equal to 
$b_n$.
We condition on the tile covering the ``break" at the top of the bracelet, as shown in the following images. There are three options.

\begin{enumerate} 
\item The tiling is breakable at the top, meaning that no single tile crosses over from the $n^{th}$ position (immediately to the left of the break) to the first position (immediately to the right). See Figure \ref{bracie}.
\begin{figure}[h]
\centering
    \includegraphics[scale=0.4]{f9.png}
\caption{A bracelet of length $n$.}
\label{bracie}
\end{figure}
As the bracelet is breakable here, there are simply $a_n$ ways to tile the $1 \times n$ strip we obtain when we unfold the bracelet.

\item   The tiling is not breakable at the top, due to a domino covering the break.
For this, we simply remove the domino and unfold the bracelet to give us a strip of length $n-2$, and hence there are  $a_{n-2}$ ways to tile it.

\item   The tiling is not breakable at the top, due to a red or blue $k$-mino covering the break. 
In this case, for each $k$-mino covering the break there are exactly $k-1$ ways to shift it such that the bracelet remains unbreakable at the top. There are two colors for the $k$-mino (red or blue), and the rest of the bracelet has length $n-k$. Hence, there are $2(k-1)a_{n-k}$ ways to tile this particular bracelet. 
 Since $k$ can range from 3 to $n$, we get that the total number of ways to tile in this situation is $2\sum_{k=3}^{n}(k-1)a_{n-k}$.
\end{enumerate} 

We have now covered all three possible cases. Adding the results will give equation (\ref{eighteqn}), as desired. 
\end{proof}


To conclude, we present the following 
results for our bracelet sequence 
$(b_n)_{n \geq 0}$. These can all be proved by induction, by Theorem \ref{eight}, or by tilings; we leave the details to the 
reader.
\begin{theorem}\label{last}
For $a_n$ and $b_n$ defined as above, we have
\begin{align} 
b_n &amp;= 3b_{n-1} - 2b_{n-2} + b_{n-3} -b_{n-4}, \label{last.1} \\[1.2ex]
b_n &amp;= 2b_{n-1} + b_{n-3} + 2,  \label{last.2}\\[1.2ex]
b_n &amp;= \frac{1}{2}\bigg(5a_n - a_{n-1} - a_{n-2}\bigg) - 1,  \label{last.3}\\[1.2ex]
b_n &amp;= \theta_1^n + \theta_2^n + \theta_3^n - 1, \ \  \mbox{ for $\theta_1, \theta_2, \theta_3$ the roots of $x^3 - 2x^2 - 1 =0$}. \label{last.4}
\end{align} 
\end{theorem}


 With this recurrence relation (\ref{last.1}) for $b_n$, and with  our initial values for $b_n$ of $1, 3, 10$, and $23$, we can conclude that we do indeed have the sequence
\seqnum{A080204}.
Furthermore, the recurrence relation in (\ref{last.1}) for $b_n$ is also satisfied by $a_n$, as seen here in Lemma \ref{neatrecurrence}. Only the initial values are different. 
\begin{lemma}\label{neatrecurrence}
For $n \geq 4$ we have 
\begin{equation}\label{neatrecurrenceeqn}
a_n = 3a_{n-1} -2a_{n-2}
+ a_{n-3} - a_{n-4}.
\end{equation}
\end{lemma}


\begin{proof}
From equation (\ref{simplereccurenceeqn}) in Corollary \ref{simplereccurence}, we have that 
$a_{n} = 2a_{n-1} + a_{n-3}$ and replacing $n$ with $n-1$ we have
$a_{n-1} = 2a_{n-2} + a_{n-4}$. We subtract these two equations, and simplify,  to obtain the desired result. 
\end{proof}




Finally, we can rewrite  equation  (\ref{last.2}) in Theorem \ref{last}
as $(b_n + 1) = 2(b_{n-1} +1) + (b_{n-3} + 1)$,
which tells us that the numbers $b_{n} + 1$ have a particularly nice recurrence formula
(in fact, the same recurrence formula as 
for $a_n$ in 
Theorem \ref{simplereccurence}).
These numbers $b_n + 1$ appears in the 
OEIS as \seqnum{A332647}.

\section{Acknowledgments}
We express our gratitude to Pioneer Academics for making this collaboration possible, and to Brittney Miller for her many helpful comments and suggestions for improving our paper. 


\begin{thebibliography}{9}

\bibitem{BQ}
Arthur~T. Benjamin and Jennifer~J. Quinn, {\em Proofs That Really Count},
  Vol.~27 of {\em The Dolciani Mathematical Expositions}, Mathematical
  Association of America, 2003.

\bibitem{BBKSW}
John Bodeen, Steve Butler, Taekyoung Kim, Xiyuan Sun, and Shenzhi Wang, Tiling
a strip with triangles, {\em Electron. J. Combin.} {\bf 21} (2014),
P1.7.

\bibitem{CGH}
Phyllis Chinn, Ralph Grimaldi, and Silvia Heubach, Tiling with {L}'s and
  squares, {\em J. Integer Sequences} {\bf 10} (2007), 
  \href{https://cs.uwaterloo.ca/journals/JIS/VOL10/Heubach/heubach40.html}{Article 07.2.8}.

\bibitem{HR}
Kathryn Haymaker and Sara Robertson, Counting colorful tilings of
rectangular arrays, {\em J. Integer Sequences} {\bf 20} (2017),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL20/Haymaker/haym2.html}{Article 17.5.8}.

\bibitem{Kah}
Reza Kahkeshani, The tilings of a {$(2\times n)$}-board and some
new combinatorial identities, {\em J. Integer Sequences} {\bf 20}
(2017), \href{https://cs.uwaterloo.ca/journals/JIS/VOL20/Kahkeshani/kahk3.html}{Article 17.5.4}.

\bibitem{KA}
Reza Kahkeshani and Meysam Arab, A generalized {B}inet formula that
counts the tilings of a {$(2\times N)$}-board, {\em Integers} {\bf 18}
(2018), Paper No.~A91.

\bibitem{KS}
Matt Katz and Catherine Stenson, Tiling a {$(2\times n)$}-board with
squares and dominoes, {\em J. Integer Sequences} {\bf 12} (2009),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL12/Stenson/stenson8.html}{Article 09.2.2}.

\bibitem{ML}
R.~B. McQuistan and S.~J. Lichtman, Exact recursion relation for {$2\times N$}
arrays of dumbbells, {\em J. Mathematical Phys.} {\bf 11} (1970),
3095--3099.

\bibitem{Sloan}
N. J. A. Sloane et al., {\it The On-Line Encyclopedia of Integer Sequences},
published electronically at \url{https://oeis.org}, 2021.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 05B45; Secondary 52C20.

\noindent \emph{Keywords: }  domino, tromino, tiling, Fibonacci, rectangle.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000129},
\seqnum{A000133},
\seqnum{A001333},
\seqnum{A026150},
\seqnum{A030186},
\seqnum{A052980},
\seqnum{A077917},
\seqnum{A080204},
\seqnum{A097075},
\seqnum{A097076},
\seqnum{A278815}, and
\seqnum{A332647}.)


\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 18 2021;
revised version received April 12 2021. 
Published in {\it Journal of Integer Sequences}, April 16 2021.

\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>