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