.pdf
.ps
.tex
Written: April 13, 2011.
In how many ways can His Majesty, The Chess King, walk n steps on an infinite chessboard,
and return to the starting point? Let this number be f(n). Of course f(0)=1 (there is one way of doing nothing),
f(1)=0 (since every step involves doing something, there is no way of getting back to the starting point in
one step), and f(2)=8 (why?). But what about f(1000)?, f(1000000)?, using the nifty
thirdorder linear computergenerated recurrence
(and computerproved! The proof is politely supressed, but obtuse readers can run the program
and get it, if they wish). Using that recurrence, it can derive very precise asymptotics!
Maple Package
Important: This article is accompanied by the Maple
package

WalkPapers
that automatically generates mathematical articles about the number of walks of anybody,
not just the King.
Sample Input and Output for the Maple package WalkPapers

The
input file
that generated the present article
yields the output file.

For a whole webbook on onedimensional walks with various sets of allowable steps
the input file
yields the output file.

For two simple exaples of enumerating twodimensional walks returning to the staring points
the input file
yields the output file.

For a linear recurrence for the enumerating sequence for
Knight's walks that return to the starting point after 2n steps,
and for order10 asymptotics,
the
input file
yields the output file.
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page