%melech.tex:In How Many Ways Can a King Return Home After n Steps?
%%a Plain TeX file by Shalosh B. Ekhad (3 pages)

%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros
\bf
\centerline
{
In How Many Ways Can a King Return Home After n Steps?
}
\rm
\bigskip
\centerline{ {\it
Shalosh B.
EKHAD }\footnote{$^1$}
{\eightrm  \raggedright
c/o D. Zeilberger,
Department of Mathematics, Rutgers University (New Brunswick),
Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway,
NJ 08854-8019, USA.
%\break
{\eighttt c/o zeilberg  at math dot rutgers dot edu} ,
\hfill \break
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/} .
First version: April 13, 2011.
Accompanied by Maple package \hfill \break
{\eighttt http://www.math.rutgers.edu/\~{}zeilberg/tokhniot/WalkPapers} .
Supported in part by the NSF.
}
}

{\bf Theorem.} If $f(n)$ is the number of ways a Chess King can walk $n$ 
steps, returning to the starting point,
in an ``infinite'' chessboard, then  $f(0)=1,f(1)=0,f(2)=8$ (obviously!) 
and for $n \geq 0$
$$
f \left( n+3 \right)=
$$
$$
%
{\frac {
 \left( 3\,n+5 \right)  \left( n+2 \right)  \left( 3\,n+8 \right) 
 }{ \left( n+3 \right) ^{2} \left( 4+3\,n \right) } f \left( n+2 \right)
}
\, + \, 
{\frac { 4\, \left( 27\,{n}^{3}+144\,{n}^{2}+248\,n+139 \right)  }{ \left( n+3 \right) ^{2} \left( 4+3\,n \right) }} f \left( n+1 \right)
\, + \,
{\frac {32\, \left( 3\,n+7 \right)  \left( n+1 \right) ^{2} }{ \left( n+3 \right) ^{2} \left( 4+3\,n \right) }} 
f \left( n \right)
\quad .
$$
We also have the asymptotic formula:
$$
f(n)=
\frac{2}{3\pi}
\frac{{8}^{n}}{n} ( 1-4/9\,{n}^{-1}+1/18\,{n}^{-2}+{\frac {29}{486}}\,{n}^{-3}+{\frac {445}{17496}}\,{n}^{-4}-{\frac {443}{8748}}\,{n}^{-5}-{\frac {10933}{104976
}}\,{n}^{-6}+
$$
$$
{\frac {35761}{944784}}\,{n}^{-7}+{\frac {3502795}{7558272}}\,{n}^{-8}+{\frac {13332763}{38263752}}\,{n}^{-9}-{\frac {30042779573}{11019960576}
}\,{n}^{-10} )  + O(n^{-12}) \quad .
$$

{\bf Proof.} Since {\it combinatorics is algebra}, and conversely, {\it algebra is combinatorics}, $f(n)$ is the coefficient
of $x^0y^0$ in the polynomial $(x+1/x+y+1/y+xy+1/(xy)+x/y+y/x)^n$, that can be expressed as a (formal!) double-contour
integral, that is beautifully handled by
Moa Apagodu and Doron Zeilberger's Maple package

{\tt http://www.math.rutgers.edu/\Tilde zeilberg/tokhniot/MultiAlmkvistZeilberger} ,

that is explained in their article

{\tt http://www.math.rutgers.edu/\Tilde zeilberg/mamarim/mamarimPDF/multiZ.pdf}
\quad  .

Once we have the recurrence, the asymptotic formula was derived using the Maple package

{\tt http://www.math.rutgers.edu/\Tilde zeilberg/tokhniot/AsyRec} \quad ,

that is briefly explained in Doron Zeilberger's article:

{\tt http://www.math.rutgers.edu/\Tilde zeilberg/mamarim/mamarimPDF/asy.pdf} .

Everything is rigorous {\it except} for the constant in front,
$\frac{2}{3\pi}$. It was found (empirically) by first estimating the constant in front (divide $f(n)$ by the
expression on the right (except for the constant), for large $n$, say $n=1000$, and then getting a numerical estimate for that constant,
and then {\it identifying} it using Maple's built-in command {\tt identify}.)

Of course, that constant can be easily rigorously obtained in other ways.
One  way is to convert the double contour integral into a double trigonometric integral,
and use standard methods, and another way is to use
probability (find the asymptotic covariance matrix, and use the local limit law) , but who cares? \halmos

For the convenience of the readers, all the necessary tools have been assembled into {\bf one} self-contained
Maple package

{\tt http://www.math.rutgers.edu/\Tilde zeilberg/tokhniot/WalkPapers} ,

that can produce as many papers like this one as desired. Some other results 
are posted here:

{\tt http://www.math.rutgers.edu/\Tilde zeilberg/mamarim/mamarimhtml/melech.html} .

{\bf Comment.}  The first few terms of the sequence (staring with $n=1$) are
$$
0 \, , \,  8 \, , \, 24 \, , \, 216 \, , \, 1200 \, , \, 8840 \, , \, 58800 \, , \, 423640 \, , \, 3000480 \, , \, 21824208 \, , \, 158964960
\, , \,
1171230984 \, , \, \dots .
$$
This is Sloane's {\tt http://oeis.org/A098070}, where one can find a {\it fourth}-order, and hence, not
as good as our {\it third}-order, linear recurrence. As with many entries in Sloane's OEIS, one can't tell
whether the recurrence is only {\it guessed} or actually {\it proved}. Of course, thanks to WZ theory, it is
known, {\it a priori}, in many cases, that a linear recurrence (with polynomial coefficients) {\it exists}, and hence we have a 
semi-rigorous meta-proof, that could be made completely rigorous, that the guessed recurrence is {\it provably} correct,
but it is (often) easier to use WZ (or multi-WZ) {\it ab initio}, because the later method gives you a
recurrence, {\bf and its proof}, at the {\it same time}.


{\bf A Quick Guide to the Maple package} {\tt WalkPapers}


Once you have downloaded {\tt WalkPapers} to your current directory, get into Maple,
and type

{ \tt read WalkPapers:} . 

For a list of the procedures, type {\tt ezra();},
and for help with any specific procedure, type {\tt ezra(ProcedureName)}.

The main procedure is {\tt WalkPaper(S,n,m,K1,K2)}, where

(i) {\tt S} is the set of steps (a set of lists of integers of the same size)

(ii) {\tt n} is a symbol

(iii) {\tt m} is a positive integer indicating the desired order for the asymptotic formula for $f(n)$.

(iv) $K1$ is a positive integer, indicating how many terms of the sequence you would like to have displayed.

(v) $K2$ is a large (recommended at least $1000$) that is used to estimate, and {\tt identify} the constant in front
of the asymptotic formula.


For example, the present article was gotten by typing:


{\tt WalkPaper($\{$[1,0],[-1,0],[0,1],[0,-1],[1,-1],[-1,1],[1,1],[-1,-1]$\}$,n,10,30,1000):}  .


{\tt WalkPaperSR(S,n,m,K1,K2, MaxC)} 
is a semi-rigorous analog, that sometimes works faster.
(See the {\it ezra} for the meaning of {\tt MaxC}.)

{\tt Sefer1D} and {\tt Sefer2D} produce webbooks with lots of theorems for different sets of
steps in one and two dimensions, respectively.

{\bf Encore: Knight's Walks} 

For a third-order linear recurrence,
and an asymptotic formula,
for the number of ways for a Knight to return home after $2n$ steps
(in an infinite chessboard), see:

{\tt http://www.math.rutgers.edu/\Tilde zeilberg/tokhniot/oWalkPapersKnightSR} .

The first few terms (starting with $n=1$) are:
$$
8, 168, 5840, 261800, 13180608, 702273264, 38641656768, 2171652448680,
123938999632448, 7158206751686848, \dots \quad .
$$
\end








