In How Many Ways Can a King Return Home After n Steps? Shalosh B. EKHAD ^{1}

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 ≥ 0

f (n + 3) =

\begin{matrix}(3 n + 5) & (n + 2) & (3 n + 8) \\ (n + 3) & 2 & (4 + 3 n) \end{matrix}f (n + 2) + \frac{4 (27 n^{3} + 144 n^{2} + 248 n + 139)}{(n + 3)^{2} (4 + 3 n)}f (n + 1) + \frac{32 (3 n + 7) (n + 1)^{2}}{(n + 3)^{2} (4 + 3 n)} f (n) .

We also have the asymptotic formula:

f(n) = \frac{2}{3π} \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}) .

Proof. Since combinatorics is algebra, and conversely, algebra is combinatorics, f(n) is the coefficient of x^{0}y^{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

http://www.math.rutgers.edu/~zeilberg/tokhniot/MultiAlmkvistZeilberger ,

that is explained in their article

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/multiZ.pdf .

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

http://www.math.rutgers.edu/~zeilberg/tokhniot/AsyRec ,

that is briefly explained in Doron Zeilberger’s article:

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimPDF/asy.pdf .

Everything is rigorous except for the constant in front, \frac{2}{3π}. 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 identifying it using Maple’s built-in command identify.)

1 c/o D. Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus,

110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA. c/o zeilberg at math dot rutgers dot edu , http://www.math.rutgers.edu/~zeilberg/ . First version: April 13, 2011. Accompanied by Maple package http://www.math.rutgers.edu/~zeilberg/tokhniot/WalkPapers . Supported in part by the NSF.

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? For the convenience of the readers, all the necessary tools have been assembled into one selfcontained Maple package

http://www.math.rutgers.edu/~zeilberg/tokhniot/WalkPapers ,

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

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/melech.html .

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 , …. This is Sloane’s http://oeis.org/A098070, where one can find a fourth-order, and hence, not as good as our third-order, linear recurrence. As with many entries in Sloane’s OEIS, one can’t tell whether the recurrence is only guessed or actually proved. Of course, thanks to WZ theory, it is known, a priori, in many cases, that a linear recurrence (with polynomial coefficients) exists, and hence we have a semi-rigorous meta-proof, that could be made completely rigorous, that the guessed recurrence is provably correct, but it is (often) easier to use WZ (or multi-WZ) ab initio, because the later method gives you a recurrence, and its proof, at the same time. A Quick Guide to the Maple package WalkPapers Once you have downloaded WalkPapers to your current directory, get into Maple, and type

read WalkPapers: .

For a list of the procedures, type ezra();, and for help with any specific procedure, type ezra(ProcedureName). The main procedure is WalkPaper(S,n,m,K1,K2), where

(i) S is the set of steps (a set of lists of integers of the same size) (ii) n is a symbol (iii) 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 identify the constant in front of the asymptotic formula.

For example, the present article was gotten by typing:

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

WalkPaperSR(S,n,m,K1,K2, MaxC) is a semi-rigorous analog, that sometimes works faster. (See the ezra for the meaning of MaxC.) Sefer1D and Sefer2D produce webbooks with lots of theorems for different sets of steps in one and two dimensions, respectively. 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:

http://www.math.rutgers.edu/~zeilberg/tokhniot/oWalkPapersKnightSR .

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