\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 \& 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 &= a_{n-1} + a_{n-2} + 2\sum_{i=0}^{n-3}a_{i},\label{cor_eqn1}\\
\intertext{which also implies}
a_{n-1} &= 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} &= 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} &= 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 \\
&= 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 &= 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} &= 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 &= F_{n+1} + 2\sum_{i=0}^{n-3}a_iF_{n-i}
\ - \ (a_n - a_{n-1} - a_{n-2})\nonumber \\
&= 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 \\
&= 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