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

                                      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 + 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

4 (n + 1) (2 + n) f[i, j, n] + (-2 + j - n) (4 + 2 i - 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+j-n)*(4+2*i-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
                            Sn - Sj - Si Sj - -----
                                              Si 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