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], [1, -1]}

                                     Then

                (-5 + 6 n)
f[0, 0, 4 n] = 2           pochhammer(5/4, n - 1) pochhammer(3/2, n - 1)

    pochhammer(7/4, n - 1)/(pochhammer(2, n - 1) pochhammer(5/2, n - 1)

    pochhammer(3, n - 1))



                    Proof: By using the obvious recurrence

f[i, j, n] =

    f[i, j + 1, n - 1] + f[i - 1, 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

-64 (-2 + j - n) (1 + n) (3 + n) f[i, j, n]

     + (-4 + 2 i + j - n) (8 + 2 i - j + n) (6 + j + n) f[i, j, 4 + n]

     + 32 j (j + 1) (3 + n) f[i, j + 1, 1 + 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

-64*(-2+j-n)*(1+n)*(3+n)+(-4+2*i+j-n)*(8+2*i-j+n)*(6+j+n)*Sn^4+32*j*(j+1)*(3+n)
*Sj*Sn
            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 - ----- - ----
                                       Si 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->4 n, we get that f[0,0,4 n] satisfies
-64 (-2 - 4 n) (1 + 4 n) (3 + 4 n) f[0, 0, 4 n]

     + (-4 - 4 n) (8 + 4 n) (6 + 4 n) f[0, 0, 4 + 4 n] = 0

But the very same recurrence is also satisfied by h(4 n):=
 (-5 + 6 n)
2           pochhammer(5/4, n - 1) pochhammer(3/2, n - 1)

    pochhammer(7/4, n - 1)/(pochhammer(2, n - 1) pochhammer(5/2, n - 1)

    pochhammer(3, 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