Lattice Walks in the Quarter-Plane By Shalosh B. Ekhad (c/o D. Zeilberger), and Manuel Kauers' computer Theorem Let f[i,j,n] be the number of walks from the origin, to the point (i,j), with exactly n steps, staying in the first quarter-plane i>=0, j>=0, using the steps {[0, -1], [1, -1], [0, 1]} Then n 4 pochhammer(1/2, n) f[0, 0, 2 n] = --------------------- pochhammer(1, n + 1) Proof: By using the obvious recurrence f[i, j, n] = f[i, j + 1, n - 1] + f[i, j - 1, n - 1] + f[i + 1, j - 1, n - 1] For n>=1, i>=0, j>=0 subject to the initial conditions f[0,0,0]=1, f[i,j,0]=0 if, (i, j) <> (0, 0) and boundary conditions: f[-1, j, n] = 0, f[i, -1, n] = 0 the computer first generates lots of data and then using the quasi-holonomic ANSATZ as described in Manuel Kauers and Doron Zeilberger's seminal paper : The quasi-holonomic ansatz and restricted lattice paths finds the following partial recurrence equation 4 (n + 1) (2 + n) f[i, j, n] + (-2 + 2 i + j - n) (4 + j + n) f[i, j, 2 + n] = 0 Let Si, Sj, Sn be the fundamental shift operators in the i, j, and n , directions, respectively The above lemma means that f[i,j,n] is annihilated by the operator 4*(n+1)*(2+n)+(-2+2*i+j-n)*(4+j+n)*Sn^2 The proof that this opeator indeed annihilates f[i,j,n] is routine. Indeed, f[i,j,n] is annihilated by the operator 1 Si Sn - Sj - ---- - ---- Sj Sj taking successive commatators we eventually get the 0 operator and all we have to do is check that the inital conditions for the intermediate operators also hold, that is a (fast!) routine verification . Plugging-in i=0,j=0,n->2 n, we get that f[0,0,2 n] satisfies 4 (2 n + 1) (2 + 2 n) f[0, 0, 2 n] + (-2 - 2 n) (4 + 2 n) f[0, 0, 2 + 2 n] = 0 But the very same recurrence is also satisfied by h(2 n):= n 4 pochhammer(1/2, n) --------------------- pochhammer(1, n + 1) since plugging this last expression indeed gives 0 Since the theorem is true for n=0,1,2,3 (check!) It is true in general. QED