<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[table]{xcolor}
\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}
\newtheorem{idn}[theorem]{Identity}

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

\begin{center}
\vskip 1cm{\LARGE\bf The Tilings of a $(2\times n)$-Board and \\
\vskip .1in
Some New Combinatorial Identities}
\vskip 1cm
\large
Reza Kahkeshani\\
Department of Pure Mathematics\\
Faculty of Mathematical Sciences\\
University of Kashan\\
Kashan\\
Iran\\
\href{mailto:kahkeshanireza@kashanu.ac.ir}{\tt kahkeshanireza@kashanu.ac.ir}\\
\end{center}

\vskip .2 in

\begin{abstract}
We know that the Fibonacci numbers count the tilings of a $(1\times
n)$-board by squares and dominoes, or equivalently, the number of
tilings of a $(2\times n)$-board by dominoes.  We use the tilings of a
$(2\times n)$-board by colored unit squares and dominoes to obtain some
new combinatorial identities.  They are generalization of some known
combinatorial identities and in the special case give us the Fibonacci
identities.
\end{abstract}

\section{Introduction}

The \textit{Fibonacci numbers} (\seqnum{A000045}), $(F_n)_{n\geq 0}$, are the sequence defined by 
$F_0=0$, $F_1=1$, and $F_n=F_{n-1}+F_{n-2}$ for $n\geq 2$ \cite{B,G}.
It is easy to see that the tilings of a $(1\times n)$-board with $(1\times 1)$ squares and $(1\times 2)$ dominoes 
can be counted by the Fibonacci numbers. In fact, if $f_n$ counts such tilings then $f_n=F_{n+1}$.
From now on, we use the word ``square(s)'' to mean ``$(1\times1)$ square(s)''. 
The \textit{Pell numbers} (\seqnum{A000129}) are defined by $P_0=0$, $P_1=1$, and for $n\geq 2$, $P_n=2P_{n-1}+P_{n-2}$. 
The Pell number $P_{n+1}$ counts the tilings of a $(1\times n)$-board with dominoes and two colors of squares. 
Benjamin, Quinn, Plott, and Sellers \cite{BPS,BQ} proved a number of combinatorial identities using these interpretations.  
McQuistan and Lichtman \cite{ML} also studied the tilings of a $(2\times n)$-board by squares and dominoes 
for placing dimers on a lattice and proved that
$$k_n=3k_{n-1}+k_{n-2}-k_{n-3}$$
for $n\geq 3$, where $k_n$ is the number of such tilings 
(see Cipra's comment on (\seqnum{A030186}) in OEIS \cite{S}). 
In following, Katz and Stenson \cite{KS} investigated 
the tilings of a $(2\times n)$-board by colored squares and dominoes. They \cite{KS} obtained the recurrence relation 
$$k_n^{a,b}=(a^2+2b)k_{n-1}^{a,b}+a^2bk_{n-2}^{a,b}-b^3k_{n-3}^{a,b}\quad (n\geq 3)$$
with the initial values $k_0^{a,b}=1$, $k_1^{a,b}=a^2+b$ and $k_2^{a,b}=a^4+4a^2b+2b^2$,
where $k_n^{a,b}$ is the number of tilings of a $(2\times n)$-board by $a$ colors of squares and $b$ colors of dominoes.
Clearly, $k_n=k_{n}^{1,1}$. 
Moreover, they showed that the generating function of $k_n^{a,b}$ is 
$$K^{a,b}(x)=\frac{1-bx}{1-(a^2+2b)x-a^2bx^2+b^3x^3}$$
(see (\seqnum{A253265}) in OEIS \cite{S} for a comment) and proved the following combinatorial identities: 
\begin{align*}
k_n^{a,b}&amp;=(a^2+b)k_{n-1}^{a,b}+(2a^2b+b^2)k_{n-2}^{a,b}+2a^2\sum_{i=0}^{n-3}b^{n-i-1}k_{i}^{a,b},\\
k_{m+n}^{a,b}&amp;=k_m^{a,b}k_n^{a,b}+b^2k_{m-1}^{a,b}k_{n-1}^{a,b}+2a^2\sum_{i=0}^{m-1}\sum_{j=m+1}^{m+n}b^{j-i-1}k_{i}^{a,b}k_{m+n-j}^{a,b},\\
k_{n}^{a,b}&amp;=(a^2+b)^n+\sum_{i=0}^{n-2}k_{i}^{a,b}\Bigl(b^2(a^2+b)^{n-i-2}+2\bigl(b(a^2+b)^{n-i-1}-b^{n-i}\bigr)\Bigr).
\end{align*}
Since $k_{n}^{0,1}=f_n$, these identities in the special case give us the Fibonacci identities \cite{KS}.

In this paper, we explore the tilings of a $(2\times n)$-board by colored squares and dominoes
and obtain some new combinatorial identities according to the style of Benjamin and Quinn \cite{BQ}.
Moreover, we show that they are generalization of some famous Fibonacci identities.

\section{Some combinatorial identities}



Once again, consider a $(2\times n)$-board and, with a scissor, cut out
only a square in the last column of the top row (see Figure \ref{pruned}). 


\begin{figure}[H]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|}\hline
&amp;  &amp; \ $\cdots$ \qquad &amp; &amp; \\ \hline
&amp;  &amp; \ $\cdots$ \qquad &amp; &amp; \\ \hline
\multicolumn{1}{c}{$\scriptstyle 1$} &amp; \multicolumn{1}{c}{$\scriptstyle 2$} &amp;\omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle n$} \\
\end{tabular}
\qquad \qquad
\begin{tabular}{|r|r|c|c|c|c}\cline{1-5}
&amp; &amp; \ \ \ldots\ \ &amp; &amp; &amp; \\ \hline
&amp; &amp; \ \ \ldots\ \ &amp; &amp; &amp; \multicolumn{1}{c|}{} \\ \hline
\multicolumn{1}{c}{$\scriptstyle 1$} &amp; \multicolumn{1}{c}{$\scriptstyle 2$} &amp;\omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle n$} \\
\end{tabular}
\caption{A $(2\times n)$-board and a pruned $(2\times n)$-board.}\label{pruned}
\end{center}
\end{figure}


Let $l_{n}^{a,b}$ count the tilings of 
such board using $a$ colors of squares and $b$ colors of dominoes.
Clearly, $l_1^{a,b}=a$ and $l_2^{a,b}=a^3+2ab$. Also, $l_n^{0,b}=0$.
There are two cases for the tilings of a pruned $(2\times n)$-board, 
those ending with a horizontal domino in the bottom row and those ending with a square in the bottom row.
This implies that
\begin{equation}\label{eql}
l_n^{a,b}=bl_{n-1}^{a,b}+ak_{n-1}^{a,b}
\end{equation}
for $n\geq 2$. Replacing $n$ by 1 in \eqref{eql}, we have $l_0^{a,b}=0$.
Moreover, \eqref{eql} shows that the tilings of a pruned $(2\times n)$-board which 
end with a square in the bottom row are counted by $l_n^{a,b}-bl_{n-1}^{a,b}$.
Now we can obtain a recurrence relation for $l_{n}^{a,b}$.
\begin{theorem}\label{theorem}
For $n\geq 3$, $l_{n}^{a,b}=(a^2+2b)l_{n-1}^{a,b}+a^2bl_{n-2}^{a,b}-b^3l_{n-3}^{a,b}$.
\end{theorem}
\begin{proof}
By definition, there are $l_{n}^{a,b}$ tilings for a pruned $(2\times n)$-board.
On the other hand, we have five cases for the endings of these tilings:

\medskip
 
\noindent (i) There is a domino in the ending of the bottom row. Clearly, they are counted by $bl_{n-1}^{a,b}$.

\medskip

\noindent (ii) There are a square in column $n$ and a vertical domino in column $n-1$. 
By removing column $n-1$, it is seen that these tilings correspond 
to the tilings of a pruned $\bigl(2\times(n-1)\bigr)$-board which end with a square in the bottom row. 
According to the above note, we have $b(l_{n-1}^{a,b}-bl_{n-2}^{a,b})$ such tilings.    

\medskip

\noindent (iii) There are two squares in the ending of the bottom row. The number of these tilings is $a^2l_{n-1}^{a,b}$. 

\medskip

\noindent (iv) Two horizontal dominoes are in columns $n-2$ and $n-1$ and a square is in column $n$. 
If we remove these horizontal dominoes then it is seen that they are corresponded to $b^2(l_{n-2}^{a,b}-bl_{n-3}^{a,b})$ 
tilings of a pruned $\bigl(2\times(n-2)\bigr)$-board which end with a square in the bottom row.

\medskip

\noindent (v) The top row ends with a square and the bottom row ends with a horizontal domino followed by a square.  
Here, the number of tilings is $a^2bl_{n-2}^{a,b}$. 

\medskip

Now by summing over all cases, we get the right-side of the recurrence relation. See Figure \ref{rec}. 



\begin{figure}[H]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}\cline{1-6}
&amp; &amp; \ \ \ldots\ \ &amp; &amp; &amp; &amp; \multicolumn{1}{c}{}\\ \hline
&amp; &amp; \ \ \ldots\ \ &amp; &amp; &amp; \cellcolor{blue} &amp; \cellcolor{blue} \\ \hline
\multicolumn{1}{c}{$\scriptstyle 1$} &amp; \multicolumn{1}{c}{$\scriptstyle 2$} &amp; \multicolumn{1}{c}{$\scriptstyle \cdots$} &amp; 
\multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp;\multicolumn{1}{c}{$\scriptstyle n$} \\
\end{tabular}
\\ \vspace{.4cm}
\begin{tabular}{|c|c|c|c|c|c|c}\cline{1-6}
&amp; &amp; \ \ \ldots\ \ &amp; &amp; &amp; \cellcolor{blue} &amp; \multicolumn{1}{c}{} \\ \hline
&amp; &amp; \ \ \ldots\ \ &amp; &amp; &amp; \cellcolor{blue} &amp; \cellcolor{red} \\ \hline
\multicolumn{1}{c}{$\scriptstyle 1$} &amp; \multicolumn{1}{c}{$\scriptstyle 2$} &amp; \multicolumn{1}{c}{$\scriptstyle \cdots$} &amp; 
\multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp;\multicolumn{1}{c}{$\scriptstyle n$} \\
\end{tabular}
\qquad \qquad
\begin{tabular}{|c|c|c|c|c|c|c}\cline{1-6}
&amp; &amp; \ \ \ldots\ \ &amp; &amp; &amp; &amp; \multicolumn{1}{c}{} \\ \hline
&amp; &amp; \ \ \ldots\ \ &amp; &amp; &amp; \cellcolor{black} &amp; \cellcolor{red} \\ \hline
\multicolumn{1}{c}{$\scriptstyle 1$} &amp; \multicolumn{1}{c}{$\scriptstyle 2$} &amp; \multicolumn{1}{c}{$\scriptstyle \cdots$} &amp; 
\multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp;\multicolumn{1}{c}{$\scriptstyle n$} \\
\end{tabular}
\\ \vspace{.4cm}
\begin{tabular}{|c|c|c|c|c|c|c}\cline{1-6}
&amp; &amp; \ \ \ldots\ \ &amp; &amp; \cellcolor{blue} &amp; \cellcolor{blue} &amp; \multicolumn{1}{c}{} \\ \hline
&amp; &amp; \ \ \ldots\ \ &amp; &amp; \cellcolor{green} &amp; \cellcolor{green} &amp; \cellcolor{red} \\ \hline
\multicolumn{1}{c}{$\scriptstyle 1$} &amp; \multicolumn{1}{c}{$\scriptstyle 2$} &amp; \multicolumn{1}{c}{$\scriptstyle \cdots$} &amp; 
\multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp;\multicolumn{1}{c}{$\scriptstyle n$} \\
\end{tabular}
\qquad \qquad
\begin{tabular}{|c|c|c|c|c|c|c}\cline{1-6}
&amp; &amp; \ \ \ldots\ \ &amp; &amp; &amp; \cellcolor{black} &amp; \multicolumn{1}{c}{} \\ \hline
&amp; &amp; \ \ \ldots\ \ &amp; &amp; \cellcolor{blue} &amp; \cellcolor{blue} &amp; \cellcolor{red} \\ \hline
\multicolumn{1}{c}{$\scriptstyle 1$} &amp; \multicolumn{1}{c}{$\scriptstyle 2$} &amp; \multicolumn{1}{c}{$\scriptstyle \cdots$} &amp; 
\multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp;\multicolumn{1}{c}{$\scriptstyle n$} \\
\end{tabular}
\caption{The endings for obtaining a recurrence relation for $l_{n}^{a,b}$.}\label{rec}
\end{center}
\end{figure}

\end{proof}
It is easy to find that the generating function for $l_{n}^{a,b}$ is
$$L^{a,b}(x)=\frac{ax}{1-(a^2+2b)x-a^2bx^2+b^3x^3}.$$

The following proofs, as we shall see, are based on the double counting principle
such that one of the ways of counting breaks the problem into disjoint cases.
\begin{idn}\label{idn1}
$\displaystyle k_n^{a,b}=a^{2n}+b\sum_{i=1}^{n}a^{2(n-i)}k_{i-1}^{a,b}+2b\sum_{i=2}^{n}a^{2(n-i)+1}l_{i-1}^{a,b}+b^2\sum_{i=2}^{n}a^{2(n-i)}k_{i-2}^{a,b}$.
\end{idn}

\begin{proof}
Consider the tilings of a $(2\times n)$-board with at least one domino. 
There are $k_n^{a,b}-a^{2n}$ such tilings. On the other hand, there are four cases for the location of the last domino as shown in Figure \ref{id1}:


\begin{figure}[H]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}\hline
&amp; \ $\cdots$ \qquad &amp; &amp; \cellcolor{blue} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
&amp; \ $\cdots$ \qquad &amp; &amp; \cellcolor{blue} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
\multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle i$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} \\
\end{tabular}
\qquad \qquad
\begin{tabular}{|c|c|c|c|c|c|c|}\hline
&amp; \ $\cdots$ \qquad &amp; \cellcolor{blue} &amp; \cellcolor{blue} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
&amp; \ $\cdots$ \qquad &amp; &amp; \cellcolor{red} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
\multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle i$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} \\
\end{tabular}
\\ \vspace{.4cm}
\begin{tabular}{|c|c|c|c|c|c|c|}\hline
&amp; \ $\cdots$ \qquad &amp; &amp; \cellcolor{red} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
&amp; \ $\cdots$ \qquad &amp; \cellcolor{blue} &amp; \cellcolor{blue} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
\multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle i$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} \\
\end{tabular}
\qquad \qquad
\begin{tabular}{|c|c|c|c|c|c|c|}\hline
&amp; \ $\cdots$ \qquad &amp; \cellcolor{blue} &amp; \cellcolor{blue} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
&amp; \ $\cdots$ \qquad &amp; \cellcolor{red} &amp; \cellcolor{red} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
\multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle i$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} \\
\end{tabular}\caption{To prove Identity~\ref{idn1}, condition on the location of the last domino.}\label{id1}
\end{center}
\end{figure}

\medskip

\noindent (i) The last domino is vertical. If the last domino occupies column $i$ ($1\leq i\leq n$) then cells 1 through $i-1$ in the both rows
can be tiled in $k_{i-1}^{a,b}$ ways, column $i$ must be covered by one of the $b$ colored dominoes and remainder cells must be covered in $a^{2(n-i)}$ ways. 
Thus, the number of tilings in this case is $\sum_{i=1}^{n}ba^{2(n-i)}k_{i-1}^{a,b}$.

\medskip

\noindent (ii) The last domino is horizontal in the first row. If the last domino covers cells $i-1$ and $i$ in the first row, where $2\leq i\leq n$,
then cell $i$ in the second row must be covered by a square. So, cells 1 through $i-2$ in the first row and cells 1 through $i-1$ in the second row can be together tiled in $l_{i-1}^{a,b}$ ways and remainder cells must be covered by squares in $a^{2(n-i)}$ ways.     
So, the number is $\sum_{i=2}^{n}baa^{2(n-i)}l_{i-1}^{a,b}$.

\medskip

\noindent (iii) The last domino is horizontal in the second row. This is similar to (ii).

\medskip

\noindent (iv) The last domino is horizontal in the both rows.
If cells $i-1$ and $i$ in the both rows coverd by two horizontal dominoes ($2\leq i\leq n$) 
then cells 1 through $i-2$ can be covered in $k_{i-2}^{a,b}$ ways and cells $i+1$ through $n$ in the both rows must be tiled by squares.
So, there are $\sum_{i=2}^{n}b^2a^{2(n-i)}k_{i-2}^{a,b}$ such tilings.

\medskip

Now we sum over all cases to get the identity.
\end{proof}

\begin{idn}\label{idn2}
$\displaystyle k_n^{a,b}=k_{n}^{0,b}+2ab\sum_{i=2}^{n}l_{i-1}^{a,b}k_{n-i}^{0,b}+a^2\sum_{i=1}^{n}k_{i-1}^{a,b}k_{n-i}^{0,b}$.
\end{idn}

\begin{proof}
The left-hand side of this identity counts the tilings of a $(2\times n)$-board. On the other hand, 
we obtain the right-hand side by conditioning on the location of the last square. There are four cases as shown in Figure \ref{id2}:

\begin{figure}[H]
\begin{center}
\begin{tabular}{|c|c|c|c|c|}\hline
&amp; &amp; \ $\cdots$ \qquad &amp; &amp; \\ \hline
&amp; &amp; \ $\cdots$ \qquad &amp; &amp; \\ \hline
\omit\span\omit\span\omit\span\omit\span\omit\mathstrut\upbracefill \\
\multicolumn{5}{c}{$\scriptstyle \text{no square}$}\\
\end{tabular}
\\ \vspace{.4cm}
\begin{tabular}{|c|c|c|c|c|c|c|}\hline
&amp; \ $\cdots$ \qquad &amp; &amp; \cellcolor{red} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
&amp; \ $\cdots$ \qquad &amp; \cellcolor{blue} &amp; \cellcolor{blue} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
\multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle i$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} \\
\end{tabular}
\qquad \qquad 
\begin{tabular}{|c|c|c|c|c|c|c|}\hline
&amp; \ $\cdots$ \qquad &amp; &amp; \cellcolor{red} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
&amp; \ $\cdots$ \qquad &amp; &amp; \cellcolor{blue} &amp; \cellcolor{blue} &amp; \ $\cdots$ \qquad &amp; \\ \hline
\multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle i$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} \\
\end{tabular}
\\ \vspace{.4cm}
\begin{tabular}{|c|c|c|c|c|c|c|}\hline
&amp; \ $\cdots$ \qquad &amp; \cellcolor{blue} &amp; \cellcolor{blue} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
&amp; \ $\cdots$ \qquad &amp; &amp; \cellcolor{red} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
\multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle i$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} \\
\end{tabular}
\qquad \qquad 
\begin{tabular}{|c|c|c|c|c|c|c|}\hline
&amp; \ $\cdots$ \qquad &amp; &amp; \cellcolor{blue} &amp; \cellcolor{blue} &amp; \ $\cdots$ \qquad &amp; \\ \hline
&amp; \ $\cdots$ \qquad &amp; &amp; \cellcolor{red} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
\multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle i$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} \\
\end{tabular}
\\ \vspace{.4cm}
\begin{tabular}{|c|c|c|c|c|c|c|}\hline
&amp; \ $\cdots$ \qquad &amp;  &amp; \cellcolor{blue} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
&amp; \ $\cdots$ \qquad &amp;  &amp; \cellcolor{red} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
\multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \multicolumn{1}{c}{$\scriptstyle i$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{ }$} \\
\end{tabular}\caption{To prove Identity~\ref{idn2}, condition on the location of the last square.}\label{id2}
\end{center}
\end{figure}

\medskip

\noindent (i) There is no square in the tiling. Obviously, we have $k_n^{0,b}$ of these.

\medskip

\noindent (ii) The last square is in the first row. If the last square covers column $i$ then we have two subcases for the second row: 
either cells $i-1$ and $i$ tiled by a domino ($2\leq i\leq n$) or cells $i$ and $i+1$ tiled by a domino ($1\leq i\leq n-1$).
In the first subcase, cells 1 through $i-1$ in the first row and cells 1 through $i-2$ in the second row can be together covered
in $l_{i-1}^{a,b}$ ways and moreover, cells $i+1$ through $n$ in the both rows must be tiled in $k_{n-i}^{0,b}$ ways. 
Thus, there is $\sum_{i=2}^{n}abl_{i-1}^{a,b}k_{n-i}^{0,b}$ such tilings.
In the second subcase, the pruned board in columns $i+1$ to $n$ must be tiled in $l_{n-i}^{0,b}$ ways. 
But $l_{n-i}^{0,b}=0$ and this subcase will not occur.

\medskip

\noindent (iii) The last square is in the second row. This is similar to (ii).

\medskip

\noindent (iv) The last square is in the both rows. 
If the last square is in column $i$ of the both rows ($1\leq i\leq n$) then  
we have no restriction in the left-hand side of column $i$ and cells $i+1$ through $n$ in the both rows must be together tiled only by dominoes.
So, there are $\sum_{i=1}^{n}a^2k_{i-1}^{a,b}k_{n-i}^{0,b}$ of these tilings.

\medskip

Now, by summing over all cases, we get the identity.
\end{proof}

Identity \ref{idn3}, as illustrated below, depends on the notion of breakability. A tiling of a $(2\times n)$-board is \textit{breakable}
at column $i$ if we can decompose the tiling into two tilings, one covering columns 1 through $i$ and the other
covering columns $i+1$ through $n$. Otherwise, we call the tiling \textit{unbreakable}.

\begin{idn}\label{idn3}
$k_{m+n}^{a,b}=k_{m}^{a,b}k_{n}^{a,b}+2bl_{m}^{a,b}l_{n}^{a,b}+b^2k_{m-1}^{a,b}k_{n-1}^{a,b}$.
\end{idn}

\begin{proof}
We know that there are $k_{m+n}^{a,b}$ tilings for a $\bigl(2\times (m+n)\bigr)$-board. 
This gives us the left-side hand of the identity.
On the other hand, let us condition on breakability at column $m$. There are four cases as shown in Figure \ref{id3}:


\begin{figure}[H]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|}\hline
&amp; \ $\cdots$ \qquad &amp;  &amp; &amp; &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
&amp; \ $\cdots$ \qquad &amp; &amp; &amp; &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
\multicolumn{1}{c}{$\scriptstyle 1\ $} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} &amp; \multicolumn{1}{c}{$\scriptstyle m$} &amp; 
\multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$}  &amp; \multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$}\\ 
\omit\span\omit\span\omit\span\omit\mathstrut\upbracefill &amp; \omit\span\omit\span\omit\span\omit\mathstrut\upbracefill \\
\end{tabular}
\qquad \qquad 
\begin{tabular}{|c|c|c|c|c|c|c|c|}\hline
&amp; \ $\cdots$ \qquad &amp; &amp; \cellcolor{blue} &amp; \cellcolor{blue} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
&amp; \ $\cdots$ \qquad &amp; &amp; &amp;  &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
\multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} &amp; \multicolumn{1}{c}{${\scriptstyle m}$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} &amp;\omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} \\
\end{tabular}
\\ \vspace{.4cm}
\begin{tabular}{|c|c|c|c|c|c|c|c|}\hline
&amp; \ $\cdots$ \qquad &amp; &amp; &amp;  &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
&amp; \ $\cdots$ \qquad &amp; &amp; \cellcolor{blue} &amp; \cellcolor{blue} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
\multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} &amp; \multicolumn{1}{c}{$\scriptstyle m$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} &amp;\omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} \\
\end{tabular}
\qquad \qquad
\begin{tabular}{|c|c|c|c|c|c|c|c|}\hline
&amp; \ $\cdots$ \qquad &amp; &amp; \cellcolor{blue} &amp; \cellcolor{blue} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
&amp; \ $\cdots$ \qquad &amp; &amp; \cellcolor{red} &amp; \cellcolor{red} &amp; &amp; \ $\cdots$ \qquad &amp; \\ \hline
\multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} &amp; \omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} &amp; \multicolumn{1}{c}{$\scriptstyle m$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} &amp; \multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} &amp;\omit &amp; \multicolumn{1}{c}{$\scriptstyle \text{\ \ \ }$} \\
\end{tabular}
\caption{To see Identity~\ref{idn3}, count the $(m+n)$-tilings based on breakability at cell $m$.}\label{id3}
\end{center}
\end{figure}

\medskip

\noindent (i) An $(m+n)$-tiling is breakable at column $m$. There are $k_m^{a,b}k_n^{a,b}$ of these.

\medskip

\noindent (ii) Only the first row causes the tiling be unbreakable. Thus, cells $m$ and $m+1$ in the first row are covered by a domino.
Here, we have two pruned boards, the first in columns 1 through $m$ and the second in columns $m+1$ through $m+n$.
So, there are $bl_{m}^{a,b}l_{n}^{a,b}$ tilings. 

\medskip

\noindent (iii) Only the second row causes the tiling be unbreakable. This is similar to (ii).

\medskip

\noindent (iv) The both rows cause the tiling be unbreakable. Thus, there are two horizontal dominoes covering columns $m$ and $m+1$.
Therefore, cells $1$ through $m-1$ and cells $m+2$ through $m+n$ in the both rows can be tiled arbitary and  
we have $b^2k_{m-1}^{a,b}k_{n-1}^{a,b}$ tilings.

\medskip

Now we obtain the identity by summing over all cases.
\end{proof}

Let $J_n^{a,b}$ be the number of tilings of a $(1\times n)$-board by $a$ colors of squares and $b$ colors of dominoes.
It is clear that $J_n^{1,1}=f_n$ and 
\[
J_n^{0,1}=\begin{cases}
0, &amp; \text{if $n$ is odd};\\
1, &amp; \text{if $n$ is even}.
\end{cases}
\]
\begin{idn}\label{idn4}
$\displaystyle k_n^{a,b}=\sum_{i=0}^{n}\sum_{x_0+x_1+\cdots+x_i=n-i}b^i\left(J_{x_0}^{a,b}\right)^2\left(J_{x_1}^{a,b}\right)^2\cdots\left(J_{x_i}^{a,b}\right)^2$.
\end{idn}
\begin{proof}
There are $k_{n}^{a,b}$ tilings for a $(2\times n)$-board. On the other hand, condition on the number of vertical dominoes. 
Suppose that we have $i$ vertical dominoes ($0\leq i\leq n$) such that there are $x_0$ columns to the left of the first vertical domino,
$x_1$ columns between the first and the second vertical dominoes, $\ldots$, and finally, 
$x_i$ columns to the right of the last vertical domino (see Figure \ref{id4}).

\begin{figure}[H]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline
&amp; \ $\cdots$ \qquad&amp; &amp;\cellcolor{blue} &amp; &amp;\ $\cdots$ \qquad &amp; &amp;\cellcolor{blue}&amp;\qquad\ $\cdots$ \qquad\qquad&amp; \cellcolor{blue} &amp; &amp;\ $\cdots$ \qquad &amp; \\ \hline
&amp; \ $\cdots$ \qquad &amp; &amp; \cellcolor{blue}&amp; &amp; \ $\cdots$\qquad&amp; &amp;\cellcolor{blue}&amp;\qquad\ $\cdots$ \qquad\qquad &amp; \cellcolor{blue}&amp; &amp;\ $\cdots$ \qquad &amp; \\ \hline
\omit\span\omit\span\omit\mathstrut\upbracefill &amp; \omit&amp; \omit\span\omit\span\omit\mathstrut\upbracefill &amp;\omit&amp;\omit&amp;\omit&amp;\omit\span\omit\span\omit\mathstrut\upbracefill\\
\omit &amp; \multicolumn{1}{c}{$\scriptstyle x_0$} &amp; \omit &amp;\omit &amp;\omit &amp;\multicolumn{1}{c}{$\scriptstyle x_1$}&amp;\omit &amp;\omit &amp;\multicolumn{1}{c}{$\scriptstyle \cdots$}&amp;\omit&amp;\omit &amp;\multicolumn{1}{c}{$\scriptstyle x_i$} &amp; \omit \\
\end{tabular}\caption{To see Identity~\ref{idn4}, consider all of the vertical dominoes.}\label{id4}
\end{center}
\end{figure}



Thus, $x_0+x_1+\cdots+x_i=n-i$ and each $(2\times x_j)$-subboard, where $0\leq j\leq i$, must be tiled by horizontal dominoes and squares. 
Since the rows in these subboards are sepapately tiled, there are $b^i (J_{x_0}^{a,b})^2(J_{x_1}^{a,b})^2\cdots (J_{x_i}^{a,b})^2$ ways
to tile the $(2\times n)$-board. Now the assertion is implied by summing over all cases.
\end{proof}

In the special case $(a,b)=(0,1)$, Identity \ref{idn1} and Identity \ref{idn3} reduce to the well-known formulas 
$$f_n=f_{n-1}+f_{n-2}$$
and
$$f_{m+n}=f_{m-1}f_{n-1}+f_{m}f_{n},$$
respectively. Moreover, in the special cases $(a,b)=(0,1)$ and $(a,b)=(1,1)$, Identity \ref{idn4} gives us
the formulas
\begin{equation}\label{eq1}
f_n=\sum_{i=0}^{n}\mathcal{A}_{i,n}
\end{equation}
and
\begin{equation}\label{eq2}
k_n=\sum_{i=0}^{n}\sum_{x_0+x_1+\cdots+x_i=n-i}f_{x_0}^2f_{x_1}^2\cdots f_{x_i}^2,
\end{equation}
respectively, where $\mathcal{A}_{i,n}$ is the number of nonnegative even integer solutions 
to the equation $x_0+x_1+\cdots+x_i=n-i$. By taking $x_i=2y_i$, we can consider $\mathcal{A}_{i,n}$ as 
the nonnegative integer solutions to the equation $y_0+y_1+\cdots+y_i=(n-i)/2$.
Notice that $n-i$ must be even since each $x_i$ is even. 
Therefore, we get $\mathcal{A}_{i,n}=\binom{\frac{n+i}{2}}{i}$ by using a standard argument \cite{B,G},
and \eqref{eq1} becomes
\begin{equation}
f_n=\sum_{i=0}^{n}\binom{\frac{n+i}{2}}{i}.\label{eq3}
\end{equation}
Depending on the parity of $n$, \eqref{eq3} gives the following known formulas:
$$f_{2n}=\sum_{k=0}^{n}\binom{n+k}{2k} \quad\text{and}\quad f_{2n-1}=\sum_{k=0}^{n-1}\binom{n+k}{2k+1}$$
for $n\geq0$ and $n\geq 1$, respectively \cite[Identities 165--166]{BQ}.
Moreover, we can obtain \eqref{eq2} by repeated application of 
$$k_n-(f_n)^2=\sum_{m=1}^{n}k_{m-1}(f_{n-m})^2,$$
which is due to Cipra \cite[Identity 5(i)]{KS}.

\section{Concluding remarks}
In this paper, we have considered a $(2\times n)$-board, examined its tilings by colored squares and dominoes
and proved four identities.
Our proofs are respectively based on these ideas: location of the last domino, location of the last square,
breakability at a column and the number of vertical dominoes.
Benjamin and Quinn \cite[Chap.\ 1]{BQ} have used more ideas on a $(1\times n)$-board and proved several identities. 
This suggests that further results on the tilings can be obtained if we can use the ideas discussed in \cite{BQ} on a $(2\times n)$-board. 

\section{Acknowledgments}
The author is partially supported by the University of Kashan 
under grant number 364996/2.
The author would like to thank the anonymous referees for carefully reading the paper 
and specially for providing useful comments on identities 2--4 and equations \eqref{eq1} and \eqref{eq2}
which have much improved the quality of this paper.

\begin{thebibliography}{5}

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

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

\bibitem{B} R.~A.~Brualdi, {\it Introductory Combinatorics},
5th edition, Pearson Prentice Hall, 2009.

\bibitem{G} R.~P.~Grimaldi, {\it Discrete and Combinatorial Mathematics}, 
5th edition, Addison Wesley, 2004.

\bibitem{KS} M.~Katz and C.~Stenson, Tiling a $(2\times n)$-board with 
squares and dominoes, {\it J. Integer Seq.} {\bf 12} (2009),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL12/Stenson/stenson8.html}{Article 9.2.2}.

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

\bibitem{S} N.~J.~A.~Sloane, The On-Line Encyclopedia of Integer Sequences,
\url{http://oeis.org}.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 05A19; 
Secondary 05A15, 05B45, 11B39.

\noindent \emph{Keywords: } domino, tiling, Fibonacci number, combinatorial identity.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 17 2016;
revised versions received  October 14 2016; October 19 2016; March 28 2017.
Published in {\it Journal of Integer Sequences}, April 8 2017.

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