In How Many Ways Can a King Return Home After Walking n Steps?
By Shalosh B. EKHAD
.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
third-order linear computer-generated recurrence
(and computer-proved! 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 web-book on one-dimensional walks with various sets of allowable steps
the input file
yields the output file.
-
For two simple exaples of enumerating two-dimensional 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 order-10 asymptotics,
the
input file
yields the output file.
Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
Doron Zeilberger's Home Page