<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{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}{-.1in}
\setlength{\textheight}{8.4in}

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

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{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 Combinatorial Proofs of Some Formulas for \\
\vskip .13in
Triangular Tilings} \vskip 1cm
\large
Mark 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}
Bodeen et al.\ recently considered a new combinatorial tiling problem
wherein a ``strip'' is tiled using triangles of four types and derived
various identities for the resulting numbers.  Some of the identities
were proven combinatorially and others only algebraically, and the
question of finding combinatorial interpretations of all of their
results was posed.  In this note, we provide the requested bijective
proofs.  To do so, we rephrase the question in an equivalent form in
terms of tiling a strip with squares, trominos, and three types of
dominos and form bijections or near bijections where the cardinality of
various size families of sets gives the correct result.
\end{abstract}

\section{Introduction}

It is well known that the Fibonacci numbers given by $F(n)=F(n-1)+F(n-2)$ if $n \geq 2$ with $F(0)=0$ and $F(1)=1$ enumerate the tilings of a $2 \times (n-1)$ rectangular strip using vertical and horizontal dominos.  This interpretation has been used to establish many interesting properties of the Fibonacci numbers (see \cite{BQ}).  The Pell numbers $P(n)$ given by $P(n)=2P(n-1)+P(n-2)$ if $n \geq 2$ with $P(0)=1$ and $P(1)=2$  enumerate the tilings of a $2 \times n$ strip in which the vertically oriented dominos are allowed to come in two colors.  This interpretation has led to combinatorial proofs of several Pell number identities (see, e.g., \cite{BPS}).

A new problem of tiling a $2 \times n$ triangular strip using triangles was considered by Bodeen et al.~\cite{BBK} and various connections were made with the Fibonacci and Pell sequences.  In particular, let $Q(n)$ denote the number of tilings of a parallelogram having bases of length $n$ and legs of length $2$, where a leg makes an acute angle of $60^\circ$ with a base, using four types of tiles:  equilateral triangles having side length either $1$ or $2$ and oriented either upwards or downwards.  Upon considering that tilings end in one of five possible different patterns, it was shown that the numbers $Q(n)$ satisfy a third-order linear recurrence and are given by sequence \seqnum{A097076} in the
{\it On-line Encylopedia of Integer Sequences} \cite{Sl}.  A number of relations for the $Q(n)$ were obtained, among them the fact that $Q(n-1)+Q(n)$ is the $n$-th Pell number.

The following formulas were shown in Bodeen et al.~\cite{BBK} by
algebraic methods using Binet formulas and the question of finding
combinatorial proofs was raised.

\begin{proposition}
\cite{BBK} 
\emph{The sequence $Q(n)$ can be defined as $Q(0)=Q(1)=1$ and for $n \geq 2$,}
\begin{align*}
Q(n)=2Q(n-1)+Q(n-2)+(-1)^n.
\end{align*}
\label{prop1}
\end{proposition}

\begin{theorem}
\cite{BBK} \emph{Let $Q(n)$ count the number of tilings of a $2 \times n$ triangular strip. Then for $m \geq 1$,}
\begin{align*}
Q(4m)&amp;=(2Q(2m-1)+1)(2Q(2m)-1),\\
Q(4m+1)&amp;=(2Q(2m)-1)^2,\\
Q(4m+2)&amp;=2(Q(2m-1)+Q(2m))(Q(2m)+Q(2m+1)),\\
Q(4m+3)&amp;=2(Q(2m)+Q(2m+1))^2.\\
\end{align*}
\label{thm2}
\end{theorem}
\vskip -.5in
It is the purpose of the current note to provide the requested
combinatorial proofs of Proposition~\ref{prop1} and Theorem~\ref{thm2}.

\section{Combinatorial proofs}


In this section, we provide bijective proofs of Proposition~\ref{prop1} and
Theorem~\ref{thm2}.  By \cite[Theorem 1]{BBK}, we have that the numbers $Q(n)$ satisfy the recurrence
\begin{equation}\label{rec}
Q(n)=Q(n-1)+3Q(n-2)+Q(n-3), \qquad n \geq 3,
\end{equation}
with $Q(0)=Q(1)=1$ and $Q(2)=4$.  By the discussion in \cite[Section 3.1]{BQ}, the tilings enumerated by $Q(n)$ are in
one-to-one correspondence with tilings of a $1 \times n$ rectangular strip using squares, dominos, and trominos, where dominos come in one of three types.  (By a \emph{square}, \emph{domino}, or \emph{tromino}, we mean a $1\times1$, $1\times 2$, or $1\times 3$ rectangular piece, respectively.)

We may then view tilings enumerated by $Q(n)$ as words in the alphabet $\{s,d^1,d^2,d^3,t\}$, where $s$ and $t$ denote square and tromino, respectively, and  $d^i$ denotes one of three types of dominos.  Equivalently, such words may be viewed as compositions in $\{1,2,3\}$ of a positive integer $n$, where the $2$'s are marked in one of three ways.  Note that the five types of letters in these words correspond to the five types of sections that the tilings enumerated by $Q(n)$ are divided into by lines parallel to the legs of the parallelogram and not dissecting any of the pieces used.

We now adapt to the current problem a concept discussed in Benjamin and Quinn \cite[Section 1.2]{BQ} for rectangular tilings enumerated by the Fibonacci numbers.  Let $\mathcal{A}_n$ denote the set of tilings of a $1 \times n$ strip with squares, dominos, and trominos, where dominos come in one of three types.  If $1 \leq m \leq n-1$, then we will say that $\lambda \in \mathcal{A}_n$ is \emph{breakable at $m$} if it may be expressed as $\lambda=\lambda'+\lambda''$, where $\lambda'$ and $\lambda''$ have respective lengths of $m$ and $n-m$, that is, if there is no piece covering the boundary between the $m$-th and $(m+1)$-st cells.  Otherwise, we will say that $\lambda$ is \emph{unbreakable at $m$}.  Note that if $\lambda$ is unbreakable at $m$, then either cells $m-1$, $m$, and $m+1$ or $m$, $m+1$, and $m+2$ are covered by a tromino or cells $m$ and $m+1$ are covered by one of three kinds of dominos.

\subsection{Proof of Proposition~\ref{prop1}}

We will define a near bijection $f$ between the sets $\mathcal{A}_n$ and $\mathcal{R}=\mathcal{A}_{n-1}^{(1)}\cup\mathcal{A}_{n-1}^{(2)}\cup\mathcal{A}_{n-2}$, where $A_{n-1}^{(i)}$, $i=1,2$, denotes two copies of the set $\mathcal{A}_{n-1}$.  Note that $|\mathcal{R}|=2Q(n-1)+Q(n-2)$.  Let $\lambda \in \mathcal{A}_n$.  We consider cases on the right-most piece of $\lambda$ that is not a $d^3$.  If $\lambda=\lambda'+s+(d^3)^j$ for some $j \geq 0$, then let
\begin{equation}
f(\lambda)=\begin{cases} \lambda'\in \mathcal{A}_{n-1}^{(1)}, &amp; \text{if} \text{~}\text{~} j=0; \\ \lambda'+d^1+(d^3)^{j-1}\in \mathcal{A}_{n-1}^{(2)}, &amp; \text{if} \text{~}\text{~} j&gt;0,   \end{cases} \end{equation}
where ``+'' denotes concatenation.  If $\lambda=\lambda'+d^1+(d^3)^j$, then let
\begin{equation}
f(\lambda)=\begin{cases} \lambda'\in \mathcal{A}_{n-2}, &amp; \text{if} \text{~}\text{~} j=0; \\ \lambda'+t+(d^3)^{j-1}\in \mathcal{A}_{n-1}^{(2)}, &amp; \text{if} \text{~}\text{~} j&gt;0.   \end{cases} \end{equation}
For the remaining cases, we let
\begin{equation}
f(\lambda)=\begin{cases} \lambda'+s+(d^3)^j\in \mathcal{A}_{n-1}^{(2)}, &amp; \text{if} \text{~}\text{~} \lambda=\lambda'+d^2+(d^3)^j; \\ \lambda'+d^2+(d^3)^{j}\in \mathcal{A}_{n-1}^{(2)}, &amp; \text{if} \text{~}\text{~} \lambda=\lambda'+t+(d^3)^j,   \end{cases} \end{equation}
where $j \geq 0$.  Note that $f$ is one-to-one and its inverse may be obtained by considering the component of $\mathcal{R}$ to which a member of this set belongs, and if it belongs to $\mathcal{A}_{n-1}^{(2)}$, the right-most piece that is not a $d^3$.

If $n$ is even, then the mapping $f$ is not defined for $\lambda=(d^3)^{\frac{n}{2}}$, but its inverse is defined for all members of $\mathcal{R}$.  Thus, $|\mathcal{A}_n|=|\mathcal{R}|+1$, which implies the desired formula when $n$ is even.  Similarly, when $n$ is odd, then $f$ is defined on all of $\mathcal{A}_n$ but misses $\lambda'=(d^3)^{\frac{n-1}{2}}\in \mathcal{A}_{n-1}^{(2)}$, whence $|\mathcal{A}_n|=|\mathcal{R}|-1$, which completes the proof of Proposition~\ref{prop1}.



\subsection{The $n=4m$ case of Theorem~\ref{thm2}}

By the previous proposition, the $n=4m$ case of Theorem~\ref{thm2} above is equivalent to showing
$$Q(4m)=(Q(2m)-Q(2m-2))(Q(2m+1)-Q(2m-1)).$$
Note that by recurrence \eqref{rec}, we have $Q(2m)-Q(2m-2)=|\mathcal{U}|$, where
$$\mathcal{U}=\mathcal{A}_{2m-1}\cup\mathcal{A}_{2m-2}^{(1)}\cup\mathcal{A}_{2m-2}^{(2)}\cup\mathcal{A}_{2m-3},$$
with $\mathcal{A}_{2m-2}^{(i)}$ denoting two identical copies of the set $\mathcal{A}_
{2m-2}$.  Similarly, we have $Q(2m+1)-Q(2m-1)=|\mathcal{V}|$, where
$$\mathcal{V}=\mathcal{A}_{2m}\cup\mathcal{A}_{2m-1}^{(1)}\cup\mathcal{A}_{2m-1}^{(2)}\cup\mathcal{A}_{2m-2},$$
with similar notation for $\mathcal{A}_{2m-1}^{(i)}$, $i=1,2$.

To prove Theorem~\ref{thm2} when $n=4m$, we first define a partial mapping $g$ between $\mathcal{U}\times \mathcal{V}$ and $\mathcal{A}_{4m}$.  Let $\gamma=(\alpha,\beta) \in \mathcal{U}\times \mathcal{V}$.  In defining $g$, we will consider cases on $\alpha$.
First, if $\alpha \in \mathcal{A}_{2m-1}$, then let
\begin{equation}\label{p2e1}
g(\gamma)=\begin{cases} \alpha+s+\beta, &amp; \text{if} \text{~}\text{~} \beta \in \mathcal{A}_{2m}; \\ \alpha+d^1+\beta, &amp; \text{if} \text{~}\text{~} \beta \in \mathcal{A}_{2m-1}^{(1)};\\ \alpha+d^2+\beta, &amp; \text{if} \text{~}\text{~} \beta \in \mathcal{A}_{2m-1}^{(2)};\\ \alpha+t+\beta, &amp; \text{if} \text{~}\text{~} \beta \in \mathcal{A}_{2m-2}, \end{cases} \end{equation}
where ``$+$'' denotes concatenation.  Next, if $\alpha\in\mathcal{A}_{2m-2}^{(1)}$, then let
\begin{equation}\label{p2e2}
g(\gamma)=\begin{cases} \alpha+d^1+\beta, &amp; \text{if} \text{~}\text{~} \beta \in \mathcal{A}_{2m}; \\ \alpha+d^3+s+\beta, &amp; \text{if} \text{~}\text{~} \beta \in \mathcal{A}_{2m-1}^{(1)};\\ \alpha+t+\beta, &amp; \text{if} \text{~}\text{~} \beta \in \mathcal{A}_{2m-1}^{(2)};\\ \alpha+d^3+d^1+\beta, &amp; \text{if} \text{~}\text{~} \beta \in \mathcal{A}_{2m-2}. \end{cases} \end{equation}
If $\alpha \in \mathcal{A}_{2m-3}$, then let
\begin{equation}\label{p2e3}
g(\gamma)=\begin{cases} \alpha+t+\beta, &amp; \text{if} \text{~}\text{~} \beta \in \mathcal{A}_{2m}; \\ \alpha+d^1+d^3+\beta, &amp; \text{if} \text{~}\text{~} \beta \in \mathcal{A}_{2m-1}^{(1)};\\ \alpha+d^2+d^3+\beta, &amp; \text{if} \text{~}\text{~} \beta \in \mathcal{A}_{2m-1}^{(2)};\\ \beta+d^3+t+\alpha, &amp; \text{if} \text{~}\text{~} \beta \in \mathcal{A}_{2m-2}. \end{cases} \end{equation}
If $\alpha \in \mathcal{A}_{2m-2}^{(2)}$, then let
\begin{equation}\label{p2e4}
g(\gamma)=\begin{cases} \alpha+d^2+\beta, &amp; \text{if} \text{~}\text{~} \beta \in \mathcal{A}_{2m}; \\ \alpha+s+d^3+\beta, &amp; \text{if} \text{~}\text{~} \beta \in \mathcal{A}_{2m-1}^{(1)};\\ \alpha+d^3+d^2+\beta, &amp; \text{if} \text{~}\text{~} \beta \in \mathcal{A}_{2m-2}. \end{cases} \end{equation}
Finally, if $\gamma=(\alpha,\beta)$, where $\alpha \in \mathcal{A}_{2m-2}^{(2)}$ and $\beta \in \mathcal{A}_{2m-1}^{(2)}$ starts with a square, then let
$$g(\gamma)=\alpha+d^3+d^3+\beta',$$
where $\beta'$ is obtained from $\beta$ by removing the initial square.

The function $g$ is not defined for those ordered pairs $(\alpha,\beta)$ such that $\alpha \in \mathcal{A}_{2m-2}^{(2)}$ and $\beta \in \mathcal{A}_{2m-1}^{(2)}$, not starting with a square.  Note that \eqref{p2e1} covers all cases in which a member of $\mathcal{A}_{4m}$ is breakable at the boundary $2m-1$ except for those tilings in which the piece directly to the right of this boundary is a $d^3$.  Two of the cases for breakable members of $\mathcal{A}_{4m}$ at $2m-1$ of this last type are covered in \eqref{p2e3} and an additional case is covered in \eqref{p2e4}.  Using \eqref{p2e1}-\eqref{p2e4}, one may verify that $g$ is one-to-one where it is defined and that $g$ misses exactly those $\rho \in \mathcal{A}_{4m}$ of the following form:  $\rho$ is breakable at $2m-1$, with the piece directly to the right of this boundary being $d^3$ and the piece to the left of this boundary being either $d^3$ or $t$.

Thus, to complete the proof, it suffices to define a bijection between the sets
$\mathcal{C}_m=\mathcal{A}_{2m-1}\times(\mathcal{A}_{2m-3}\cup\mathcal{A}_{2m-4})$ and $\mathcal{D}_m=\mathcal{A}_{2m-2}\times \mathcal{A}_{2m-1}^*$, where $\mathcal{A}_{2m-1}^*$ denotes the subset of $\mathcal{A}_{2m-1}$ not starting with a square.  Let $(\lambda, \sigma) \in \mathcal{C}_m$.  We will construct an ordered pair $(\lambda', \sigma')$ belonging to $\mathcal{D}_m$.  To do so, let us express $\lambda$ as the word $\lambda_1\lambda_2\cdots$ in the alphabet $\{s,t,d^{1},d^{2},d^{3}\}$ such that the $i$-th letter of the word represents the $i$-th piece of $\lambda$ from the left, and, likewise, we express $\sigma$ as $\sigma_1\sigma_2\cdots$.  Let $i_0$ denote the smallest index $i \geq 1$ such that one (possibly both) of the following conditions fails to hold: (a) $\lambda_{2i-1}=\lambda_{2i}=s$, or (b) $\sigma_i=d^3$ or $t$, with $\sigma_j=d^3$ for all $1 \leq j &lt;i$.  In condition (b), we also require that $\sigma \in \mathcal{A}_{2m-3}$ or else this condition fai!
 ls with index one.  Since $2m-3$ is odd, note that the index $i_0$ always exists.

Let us first assume $i_0=1$ and define a mapping in this instance.  To do so, we consider several cases on $\lambda$.  First, if $\lambda$ does not start with $s$, then let $\sigma'=\lambda$ and $\lambda'$ be obtained from $\sigma$ by adding either an $s$ or $d^1$ piece to the beginning of $\sigma$, depending on whether $\sigma$ belongs to $\mathcal{A}_{2m-3}$ or $\mathcal{A}_{2m-4}$, respectively.  If $\lambda$ starts with $s$, but not with $ss$ or $sd^1$, then we delete the first square of $\lambda$ to obtain $\lambda'$ and add either $d^1$ or $t$ to the beginning of $\sigma$ to obtain $\sigma'$.  If $\lambda$ starts with $ss$ and $\sigma \in \mathcal{A}_{2m-4}$, then let $\lambda'=\sigma+d^2$ and $\sigma'=\lambda-ss+d^2$, where the addition and subtraction of the indicated letters happens now at the beginning of words.  If $\lambda$ starts with $sd^1$ and $\sigma \in \mathcal{A}_{2m-3}$, then let $\lambda'=\lambda-sd^1+d^3$ and $\sigma'=\sigma+d^2$.  If $\lambda$ starts w!
 ith $sd^1$ and $\sigma \in \mathcal{A}_{2m-4}$, then let $\lambda'=\lambda-sd^1+d^3$ and $\sigma'=\sigma+d^3s$.  Finally, if $\lambda$ starts with $ss$ and $\sigma \in \mathcal{A}_{2m-3}$, then we consider the following three further subcases: $\sigma$ starts with (i) $s$, (ii) $d^1$, or (iii) $d^2$.  For (i), we let $\lambda'=\sigma-s+d^2$ and $\sigma'=\lambda-ss+d^3$; for (ii), we let $\lambda'=\sigma-d^1+t$ and $\sigma'=\lambda-ss+d^2$; and for (iii), we let $\lambda'=\sigma-d^2+t$ and $\sigma'=\lambda-ss+d^3$.

The mapping $(\lambda,\sigma)\mapsto (\lambda',\sigma')$ is seen to be one-to-one and is defined for all ordered pairs $(\lambda,\sigma)$ for which $i_0=1$.  We now wish to extend it to all ordered pairs $(\lambda,\sigma)$ for which $i_0&gt;1$.  Note that if $i_0&gt;1$, then $\lambda$ starts with at least $2(i_0-1)$ $s$ pieces and $\sigma \in \mathcal{A}_{2m-3}$ starts with at least $i_0-2$ $d^3$ pieces, with the $(i_0-1)$-st piece either a $d^3$ or a $t$.  In this case, we let $(\lambda',\sigma')$ be given by
$$\lambda'=\left(\lambda-(s)^{2i_0-2}\right)'+(d^3)^{i_0-1}$$
and either
$$\sigma'=\left(\sigma-(d^3)^{i_0-1}\right)'+(d^3)^{i_0-1}\qquad \text{or} \qquad \sigma'=\left(\sigma-(d^3)^{i_0-2}-t\right)'+(d^3)^{i_0-1},$$
where the prime operation appearing on the right-hand side of the last two equations is as defined in the case $i_0=1$ above (now applied to members of $\mathcal{C}_{m-i_0+1}$ for which the violating index is one).  This defines the $'$ mapping for all ordered pairs for which $i_0&gt;1$ and hence for all of $\mathcal{C}_m$.  One may verify that it is a bijection.  Note that in constructing the inverse mapping on $\mathcal{D}_m$, one would write $\lambda'=\lambda_1'\lambda_2'\cdots$ and $\sigma'=\sigma_1'\sigma_2'\cdots$ and consider the smallest index $j\geq1$ such that one of the following conditions fails to hold: (i) $\lambda_j'=d^3$, or (ii) $\sigma_j'=d^3$, with $\sigma_{j+1}'\neq s$.

\subsection{Proof of remaining cases of Theorem~\ref{thm2}}

The other cases of Theorem~\ref{thm2} can be proved in a similar manner, which we now discuss.  By Proposition~\ref{prop1}, the $n=4m+1$ case of Theorem~\ref{thm2} is equivalent to showing
$$Q(4m+1)=(Q(2m)+2Q(2m-1)+Q(2m-2))^2.$$
For this, we can define an explicit bijection between the set of ordered pairs from $\mathcal{A}_{2m}\cup\mathcal{A}_{2m-1}^{(1)}\cup\mathcal{A}_{2m-1}^{(2)}\cup\mathcal{A}_{2m-2}$
and the set of tilings $\mathcal{A}_{4m+1}$.  The construction of the bijection follows along roughly similar lines to the $n=4m$ case above, with one needing to define in the end a bijection between the sets $\mathcal{C}_m$ and $\mathcal{D}_m$.  The main difference with the $n=4m$ case is that it is more convenient to consider cases using the criterion of breakability at $2m$ rather than at $2m-1$ with regard to members of $\mathcal{A}_{4m+1}$.

To show the $n=4m+2$ case, we define a bijection $h$ between the sets $\mathcal{U}\times \mathcal{V}=(\mathcal{A}_{2m-1}^{(1)}\cup\mathcal{A}_{2m-1}^{(2)}\cup\mathcal{A}_{2m}^{(1)}\cup\mathcal{A}_{2m}^{(2)})
\times(\mathcal{A}_{2m}\cup\mathcal{A}_{2m+1})$ and $\mathcal{A}_{4m+2}$, where $\mathcal{A}_j^{(i)}$, $i=1,2$, denotes two identical copies of the set $\mathcal{A}_j$. Let $\gamma=(\alpha,\beta) \in \mathcal{U}\times \mathcal{V}$.  We first construct some members of $\mathcal{A}_{4m+2}$ that are breakable at $2m+1$ from ordered pairs $(\alpha,\beta)$.  If $\beta \in \mathcal{A}_{2m+1}$, then let
\begin{equation}\label{p2e5}
h(\gamma)=\begin{cases} \alpha+d^1+\beta, &amp; \text{if} \text{~}\text{~} \alpha \in \mathcal{A}_{2m-1}^{(1)}; \\ \alpha+d^2+\beta, &amp; \text{if} \text{~}\text{~} \alpha \in \mathcal{A}_{2m-1}^{(2)};\\ \alpha+s+\beta, &amp; \text{if} \text{~}\text{~} \alpha \in \mathcal{A}_{2m}^{(1)}. \end{cases} \end{equation}
We next construct members of $\mathcal{A}_{4m+2}$ that are not breakable at $2m+1$.  If $\beta \in \mathcal{A}_{2m}$, then let
\begin{equation}\label{p2e6}
h(\gamma)=\begin{cases} \alpha+t+\beta, &amp; \text{if} \text{~}\text{~} \alpha \in \mathcal{A}_{2m-1}^{(1)}; \\ \beta+t+\alpha, &amp; \text{if} \text{~}\text{~} \alpha \in \mathcal{A}_{2m-1}^{(2)};\\ \alpha+d^1+\beta, &amp; \text{if} \text{~}\text{~} \alpha \in \mathcal{A}_{2m}^{(1)};\\ \alpha+d^2+\beta, &amp; \text{if} \text{~}\text{~} \alpha \in \mathcal{A}_{2m}^{(2)}. \end{cases} \end{equation}

Let $\mathcal{S}$ denote the members of $\mathcal{A}_{4m+2}$ that are missed by the mapping $h$.  Note that the breakable members of $\mathcal{S}$ at $2m+1$ are those where the piece directly preceding the boundary at $2m+1$ is a $d^3$ or $t$, while the unbreakable members of $\mathcal{S}$ at $2m+1$ are those where a $d^3$ piece covers the boundary at $2m+1$.  Since $h$ is seen to be one-to-one where it is defined, it suffices to define a bijection between $\mathcal{S}$ and the set $\mathcal{T}$ consisting of ordered pairs $(\alpha,\beta) \in \mathcal{U}\times\mathcal{V}$ such that $\alpha \in \mathcal{A}_{2m}^{(2)}$ and $\beta \in \mathcal{A}_{2m+1}$.

Clearly, one may identify the unbreakable members of $\mathcal{S}$ at $2m+1$ with those members of $\mathcal{T}$ in which $\beta$ starts with a square.  Thus, we need to define a bijection between the members of $\mathcal{S}$ that are breakable at $2m+1$ and the members of $\mathcal{T}$ in which $\beta$ does not start with a square.  This amounts to defining a bijection between the sets $\mathcal{C}_{m+1}$ and $\mathcal{D}_{m+1}$, which has already been done.

Finally, for the $n=4m+3$ case, we construct a bijection between the set $(\mathcal{A}_{2m}^{(1)}\cup\mathcal{A}_{2m}^{(2)}\cup\mathcal{A}_{2m+1}^{(1)}\cup\mathcal{A}_{2m+1}^{(2)})\times(\mathcal{A}_{2m}\cup\mathcal{A}_{2m+1})$
and $\mathcal{A}_{4m+3}$.  The proof follows along roughly similar lines to the $n=4m+2$ case, except that it is more convenient to consider the criterion of breakability at $2m+2$ rather than at $2m+1$.  In the end, it also reduces to finding a bijection between the sets $\mathcal{C}_{m+1}$ and $\mathcal{D}_{m+1}$, which is already done.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{thebibliography}{9}

\bibitem{BPS}
A. T. Benjamin, S. Plott, and J. A. Sellers, Tiling proofs of recent
sum identities involving Pell numbers, \emph{Ann. Comb.} \textbf{12}
(2008), 271--278.

\bibitem{BQ}
A. T. Benjamin and J. J. Quinn, \emph{Proofs that Really Count: The Art
of Combinatorial Proof}, Mathematical Association of America, 2003.

\bibitem{BBK}
J. Bodeen, S. Butler, T. Kim, X. Sun, and S. Wang, Tiling a strip with
triangles, \emph{Electron. J. Combin.} \textbf{21} (2014), \#P1.7.

\bibitem{Sl}
N. J. A. Sloane, \emph{On-Line Encyclopedia of Integer Sequences},
\url{http://oeis.org}, 2010.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary
05A19; Secondary 05A05.

\noindent {\it Keywords}: triangular tiling, Fibonacci number,
combinatorial proof.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 19 2014;
revised version received March 20 2014. 
Published in {\it Journal of Integer Sequences},
March 24 2014.

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