%
% Version 3 of the paper - responding to referee's comments 
% mailed to me from J. Shallit, 5/2/02 - inserted additional
% material at the very end involving the 16 order recurrence 
%

\documentclass[12pt,reqno]{article}
\usepackage{amssymb}
\usepackage
[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\usepackage{amsthm,amssymb,color,epsf}


\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\newtheorem{Definition}{Definition}[section]
\newtheorem{Lemma}[Definition]{Lemma}
\newtheorem{Theorem}[Definition]{Theorem}
\newtheorem{Notation}[Definition]{Notation}
\newtheorem{Prop}[Definition]{Proposition}
\newtheorem{Cor}[Definition]{Corollary}


\renewcommand{\baselinestretch}{1.2} 
\renewcommand{\arraystretch}{.7} 

\makeatletter
\def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus
 -.2ex}{2.3ex plus .2ex}{\normalsize\bf}}
\makeatother


\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\begin{center}
%\epsfxsize=4in
%\leavevmode\epsffile{logo0019.eps}
\vskip 1cm
{\LARGE\bf Domino Tilings and Products of Fibonacci and Pell Numbers}
\vskip 1cm
\large James A. Sellers \\ 
\vskip 0.5cm
Department of Mathematics \\
The Pennsylvania State University \\
107 Whitmore Lab \\
University Park, PA  16802 \\
\vskip 0.5cm
{ \href{mailto:sellersj@math.psu.edu}{\tt sellersj@math.psu.edu} }
\vskip 1cm
\bf {Abstract}
\end{center}
{\em In this brief note, we prove a result which was ``accidentally'' found thanks to Neil Sloane's Online
Encyclopedia of Integer Sequences.  Namely, we prove via elementary techniques that the number of domino tilings of 
the graph $W_4 \times P_{n-1}$ equals $f_np_n,$ the product of the $n^{th}$ Fibonacci number and the $n^{th}$ Pell number.   
}

%\vspace*{+.1in}


\begin{section}{Introduction}

Recently I received an electronic mail message \cite{Ellerman} in which I was notified that a  pair of duplicate 
sequences existed in Neil Sloane's Online Encyclopedia of Integer Sequences \cite{Sloane}.   This involved sequence \seqnum{A001582} 
and the former sequence \seqnum{A003763}.  One of these sequences was described as the product of Fibonacci and Pell numbers, 
while the other was the number of domino tilings of the graph $W_4 \times P_{n-1}.$  

I soon notified Neil Sloane of this fact and he promptly combined the two sequence entries into one entry, \seqnum{A001582}.  Upon combining these
two entries, he also noted that it was not officially a theorem (that the product of the Fibonacci and Pell numbers was always equal to the 
number of domino tilings of $W_4 \times P_{n-1}$), but that is was ``certainly true.'' 

The primary goal of this short note is to prove this result so that its status is indeed a theorem.  We close the paper by noting two other results relating domino tiling sequences in \cite{Faase} with Fibonacci numbers.  

Before proving the main result, we supply some definitions and notation for the sake of completeness.  
First, we note that the graph $W_4$ is $K_4 - e.$  
Moreover, the graph $P_n$ is the path graph on $n$ vertices.  
The Fibonacci numbers \seqnum{A000045} are defined as the sequence of integers 
\begin{equation}
\label{fibrecur}
f_1 = 1, f_2 = 1, \mathrm{\ and\ } f_{n+2} = f_{n+1} +f_n \mathrm{\ for\ all\ } n\geq 0. 
\end{equation}
The Pell numbers \seqnum{A000129} are defined as the sequence of integers 
\begin{equation}
\label{pellrecur}
p_1 = 1, p_2 = 2, \mathrm{\ and\ } p_{n+2} = 2p_{n+1} + p_n\mathrm{\ for\ all\ } n\geq 0. 
\end{equation}

\end{section}

\begin{section}{The Results}

\begin{Theorem}
\label{mainresult}
The number of domino tilings of $W_4 \times P_{n-1}$ equals $f_np_n$ for all $n\geq 2.$  
\end{Theorem} 


\begin{proof}
Thanks to an article of Faase \cite[page 146]{Faase}, we know that the number of domino tilings of $W_4 \times P_{n-1}$, which we will denote by 
$c_n,$ satisfies $c_2 = 2,$ $c_3 = 10,$ $c_4 = 36,$ $c_5 = 145$ and 
\begin{equation}
\label{recur}
c_{n+4} - 2c_{n+3}-7c_{n+2}-2c_{n+1}+c_{n} = 0
\end{equation}
for all $n\geq 2.$  (This is slightly different than the notation used in Faase, where he defines a function $C(n)$ wherein $c_n = C(n-1)$ and then does all work in terms of $C(n)$
rather than $c_n.$)

It is easy to check that $f_np_n$ satisfies the initial conditions above.  Hence, we focus on checking that $f_np_n$ satisfies 
(\ref{recur}).  

Repeated applications of (\ref{fibrecur}) and (\ref{pellrecur}) yield
\begin{equation}
\label{fibeqns}
f_{n+2} = f_n+f_{n+1},\ f_{n+3} = f_n+2f_{n+1}, \mathrm{\ and\ } f_{n+4} = 2f_n+3f_{n+1}
\end{equation}
while
\begin{equation}
\label{pelleqns}
p_{n+2} = p_n+2p_{n+1},\ p_{n+3} = 2p_n+5p_{n+1}, \mathrm{\ and\ } p_{n+4} = 5p_n+12p_{n+1}.
\end{equation}
We now substitute the findings in (\ref{fibeqns}) and (\ref{pelleqns}) into the left-hand side of (\ref{recur}) and simplify:
\begin{eqnarray*}
&& f_{n+4}p_{n+4} - 2f_{n+3}p_{n+3}-7f_{n+2}p_{n+2}-2f_{n+1}p_{n+1}+f_{n}p_n \\
&=& (2f_n+3f_{n+1})(5p_n+12p_{n+1}) -2(f_n+2f_{n+1}  )(2p_n+5p_{n+1}  )-7(f_n+f_{n+1} )( p_n+2p_{n+1})  \\
&& -2f_{n+1}p_{n+1}+f_{n}p_n \\
&=& f_np_n(10-4-7+1)  + f_{n+1}p_n(15-8-7) + f_np_{n+1}(24-10-14) + f_{n+1}p_{n+1}(36-20-14-2) \\
&=& 0
\end{eqnarray*}
Thus, $c_n = f_np_n$ for all $n\geq 2$ and the proof is complete.
\end{proof}
We note that at least two other domino tiling sequences that appear in \cite{Faase} are also closely related to Fibonacci numbers.  

We first consider sequence \seqnum{A003775} which appears in \cite[p. 147]{Faase} in relationship to the number of domino tilings of $P_5\times P_{2n}. $ Based on this sequence, we define $d_1=1, d_2=8, d_3=95, d_4=1183$ and 
\begin{equation}
\label{brecur}
d_{n+4} -15d_{n+3}+32d_{n+2}-15d_{n+1}+d_n = 0
\end{equation}
for all $n\geq 1.$ 
Computational experimentation indicates that $f_{2n-1} \,|\, d_n$ for several values of $n.$  This leads to the following theorem:
\begin{Theorem}
For all $n\geq 1,$ $d_n = g_nh_n$ where $g_n$ is the $n^{th}$ term in the sequence \seqnum{A004253} and $h_n = f_{2n-1}$ for all $n\geq 1.$  
\end{Theorem}

\noindent 
Remark:  Note that \seqnum{A004253} is related to the number of domino tilings in $K_3\times P_{2n}$ and $S_4\times P_{2n}$ as noted by Faase in \cite[pp. 146-147]{Faase}.  Moreover, \seqnum{A004253} is quite similar to \seqnum{A028475}.

\begin{proof}
The proof here follows a similar line of argument to that of Theorem \ref{mainresult}.  
From the information given in \seqnum{A004253}, we know that 
\begin{equation}
\label{k3stuff}
g_1 = 1, g_2 = 4, \mathrm{\ and\ } g_{n+2} = 5g_{n+1} - g_n.
\end{equation}
Moreover, we have
\begin{equation}
\label{oddfibs}
h_1=1, h_2=2, \mathrm{\ and\ } h_{n+2} = 3h_{n+1} - h_n.
\end{equation}
It is easy to check that $d_n = g_nh_n$ for $1\leq n\leq 4,$ so we focus our attention on the recurrence (\ref{brecur}).  We know from (\ref{k3stuff}) that 
\begin{equation}
\label{geqns}
g_{n+2} = 5g_{n+1} - g_n,\ g_{n+3} = 24g_{n+1} - 5g_n, \mathrm{\ and\ } g_{n+4} = 115g_{n+1} - 24g_n
\end{equation}
while (\ref{oddfibs}) yields
\begin{equation}
\label{heqns}
h_{n+2} = 3h_{n+1} - h_n,\ h_{n+3} = 8h_{n+1} - 3h_n, \mathrm{\ and\ } h_{n+4} = 21h_{n+1} - 8h_n.
\end{equation}
We now substitute the information from (\ref{geqns}) and (\ref{heqns}) into the left-hand side of (\ref{brecur}) and obtain the following:
\begin{eqnarray*}
&&g_{n+4}h_{n+4} -15g_{n+3}h_{n+3} +32g_{n+2}h_{n+2} -15g_{n+1}h_{n+1} +g_nh_n \\
&=& (115g_{n+1} - 24g_n)(21h_{n+1} - 8h_n) -15(24g_{n+1} - 5g_n)(8h_{n+1} - 3h_n) +32(5g_{n+1} - g_n)(3h_{n+1} - h_n) \\
&& -15g_{n+1}h_{n+1} + g_nh_n \\
&=& g_nh_n(192-225+32+1) + g_{n+1}h_n(-920+1080-160) \\
&& + g_nh_{n+1}(-504+600-96) + g_{n+1}h_{n+1}(2415-2880+480-15) \\
&=& 0
\end{eqnarray*}
This completes the proof. 

\end{proof}
Finally, we consider the last sequence of values in \cite{Faase}, which is related to the number of domino tilings of $P_8 \times P_n$ and appears as \seqnum{A028470} in \cite{Sloane}.  The first 32 values of the sequence are as follows:

%\setlength{\extrarowheight}{2pt}
\begin{center}
\begin{tabular}{ | r | r |}
\hline
$n$ & $C_n$ \\
\hline
1 & 1 \\
2 & 34 \\
3 & 153 \\
4 & 2245 \\
5 & 14824 \\
6 & 167089 \\
7 & 1292697 \\
8 & 12988816 \\
9 & 108435745 \\
10 & 1031151241 \\
11 & 8940739824 \\
12 & 82741005829 \\
13 & 731164253833 \\
14 & 6675498237130 \\
15 & 59554200469113 \\
16 & 540061286536921 \\
17 & 4841110033666048 \\
18 & 43752732573098281 \\
19 & 393139145126822985 \\
20 & 3547073578562247994 \\
21 & 31910388243436817641 \\
22 & 287665106926232833093 \\
23 & 2589464895903294456096 \\
24 & 23333526083922816720025 \\
25 & 210103825878043857266833 \\
26 & 1892830605678515060701072 \\
27 & 17046328120997609883612969 \\
28 & 153554399246902845860302369 \\
29 & 1382974514097522648618420280 \\
30 & 12457255314954679645007780869 \\
31 & 112199448394764215277422176953 \\
32 & 1010618564986361239515088848178 \\
\hline
\end{tabular}
\end{center}
The recurrence relation satisfied by the values of $C_n$ is given by 
\begin{eqnarray*}
C_{n+32} &=& 153C_{n+30}-7480C_{n+28}+151623C_{n+26} -1552087C_{n+24}+8933976C_{n+22}-30536233C_{n+20} \\
&& +63544113C_{n+18} - 81114784C_{n+16}+63544113C_{n+14} -30536233C_{n+12} +8933976C_{n+10} \\
&& -1552087C_{n+8}+151623C_{n+6} -7480C_{n+4}+153C_{n+2}-C_n
\end{eqnarray*}
for all $n\geq 1.$  

We note that $f_{n+1}\,|\, C_n$ for several values of $n.$  

\begin{center}
\begin{tabular}{ | r | r |}
\hline
$n$ & $C_n/f_{n+1}$ \\
\hline
1 & 1 \\
2 & 17 \\
3 & 51 \\
4 & 449 \\
5 & 1853 \\
6 & 12853 \\
7 & 61557 \\
8 & 382024 \\
9 & 1971559 \\
10 & 11585969 \\
11 & 62088471 \\
12 & 355111613 \\
13 & 1939427729 \\
14 & 10943439733 \\
15 & 60338602299 \\
16 & 338172377293 \\
17 & 1873494595072 \\
18 & 10464657396101 \\
19 & 58113694771149 \\
20 & 324052035315389 \\
21 & 1801727076022631 \\
22 & 10038214290617749 \\
23 & 55845947547948897 \\
24 & 311010011115265801 \\
25 & 1730773816266538081 \\
26 & 9636747170211055304 \\
27 & 53636683818362516979 \\
28 & 298610928685279993661 \\
29 & 1662149072277201394907 \\
30 & 9253169548548380483401 \\
31 & 51507590702129135617317 \\
32 & 286734628936105610236201 \\
33 & 1596133084485272225826727 \\
34 & 8885301696820653301727657 \\
35 & 49461269578409945493024768 \\
36 & 275337533349256635378114713 \\
37 & 1532712030034359905504838377 \\
38 & 8532165290411528453455489081 \\
39 & 47495826004154548026644356683 \\
40 & 264395102236750242015097270393 \\
\hline
\end{tabular}
\end{center}


This leads to the conjecture that $f_{n+1} \,|\,C_n$ for all $n\geq 1.$  We leave the proof of this (assuming it is true) to the reader, as the calculations involved herein would be straightforward but tedious.  
\end{section}


\begin{section}
{\bf {Acknowledgements}}

The author gratefully acknowledges Frank Ellerman for bringing this problem to his attention and Per Hakan Lundow for 
valuable e-conversations.  The author also thanks the referees for their helpful insights. 

\end{section}

\begin{thebibliography}{99}

\bibitem{Ellerman} Personal communication from Frank Ellerman, 
frank.ellermann@t-online.de, February 9, 2002.

\bibitem{Faase}
F. J. Faase, 
On the number of specific spanning subgraphs of the graphs $G\times P_n$, 
\emph{Ars Combinatoria}, 
\textbf{49} (1998), 129-154. 

\bibitem{Sloane} N. J. A. Sloane,
The On-Line Encyclopedia of Integer Sequences.
Published electronically at \htmladdnormallink{http://www.research.att.com/$\sim
$njas/sequences/}{http://www.research.att.com/~njas/sequences/}.
    

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}: \ \ 11B37, 11B39


\noindent \emph{Keywords: domino tilings, Fibonacci numbers, Pell numbers}

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A000045}, \seqnum{A000129}, \seqnum{A001582}, \seqnum{A003775}, \seqnum{A004253}, \seqnum{A028470} and \seqnum{A028475}.)

\vspace*{+.1in}
\noindent
Received March 20, 2002;
revised version received May 1, 2002.
Published in Journal of Integer Sequences May 6, 2002.



\bigskip
\hrule
\bigskip

\noindent 
Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.




\end{document}


\bibitem{Tucker}  Alan Tucker,
``Applied Combinatorics,''  3rd edition,
John Wiley \& Sons, 
1995.