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, 0], [-1, -1]} Then (n - 1) 2 27 pochhammer(4/3, n - 1) pochhammer(5/3, n - 1) f[0, 0, 3 n] = --------------------------------------------------------- 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, 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 2 324 (1 + n) (2 + n) (-161807382 - 361402992 i + 117562422 i + 2186788311 j 2 - 357038332 i j + 345862676 j - 53935794 n + 39718416 i n + 378457301 j n ) f[i, j, n] - 6 (-6310487898 n - 26047985508 i + 139130517753 j 2 2 3 4 + 6818097780 i + 11735231679 j + 1079686332 i + 101282616 i 3 4 2 3 - 4949594178 j + 7342056 j - 1456266438 n - 107871588 n 2 3 3 3 + 2441810934 i n - 284363082 i j + 170786004 i n - 96481962 i j 2 2 2 2 + 4751344374 i j + 10780624884 i j + 63337824 i n - 654148004 i j n 2 2 3 + 2886745852 i j n + 6584892129 j n + 2420966475 i j n - 1050093764 j n 2 2 2 + 1665866084 i j n - 7654038300 i n + 72121389444 j n - 489469716 i j 2 2 2 + 12177351159 j n + 18270318267 i j + 259096308 i n - 8737598628 3 2 2 3 + 71446344 i n + 745661146 j n + 738936004 j n ) f[i, j, 3 + n] + 221958 (-9 + 2 i + 2 j - 2 n) (-6 + i + j - n) 2 2 (-12 i + 4 i - 45 j + 4 i j + 9 j - 4 i n - 9 j n) f[i, j, 6 + n] + 108 2 3 (2 + n) (1341273078 i - 380859096 i + 679982424 i - 29444607294 j 2 2 2 + 4802210545 i j - 2116467770 i j - 11338053458 j + 1320164786 i j 3 2 - 806165600 j - 507801171 i n - 168831486 i n - 12450237929 j n 2 2 2 + 1500710373 i j n - 2878454214 j n - 203573199 i n - 1089181301 j n ) 2 f[i, j + 1, 1 + n] - 2 (48694390677 i - 615115076571 j - 49587886395 i 2 3 4 3 - 123430227669 j + 3242730060 i + 572951328 i + 19418908362 j 4 2 3 3 + 1995815626 j - 11062831518 i n - 3431964366 i j + 362844864 i n 3 2 2 2 + 533897836 i j - 18610237392 i j - 29989392411 i j - 4883493123 i n 2 2 2 + 3001420746 i j n - 5529289200 i j n - 52777744590 j n 3 2 + 31344447732 i j n + 3045679698 j n - 1305649506 i j n - 4896918072 i n 2 2 2 - 295597402254 j n - 2338557432 i j - 45594920577 j n + 79088276808 i j 2 2 3 2 2 3 - 337662972 i n - 407146398 i n - 5756908428 j n - 2178362602 j n ) 2 f[i, j + 1, 4 + n] + 36 (7834259979 i + 92076876306 j - 8211061557 i 2 3 4 3 + 56303580222 j - 4042349490 i + 548815242 i + 7988016910 j 4 2 3 3 + 225479306 j - 1231144188 i n - 628088760 i j - 976094814 i n 3 2 2 2 - 2662749358 i j - 2527334818 i j + 10023460834 i j + 627708555 i n 2 2 2 - 2359503360 i j n + 2760792700 i j n + 28278373679 j n 3 2 - 7420484152 i j n + 2166578212 j n - 1547653732 i j n + 2994620823 i n 2 2 2 + 65674109148 j n + 3319038204 i j + 14612744025 j n + 941016798 i j 2 2 3 2 2 3 + 397629918 i n + 254684835 i n + 3719079837 j n + 831733113 j n ) 2 f[i, 2 + j, 2 + n] - (-71660872692 i + 581111421372 j + 44271304920 i 2 3 4 3 + 195726005532 j - 10699491042 i + 474027420 i - 15947928216 j 4 2 3 3 - 4448956288 j + 7420759002 i n + 4428790272 i j - 1343780424 i n 3 2 2 2 - 2791603876 i j + 575052462 i j + 35381671380 i j + 3383793090 i n 2 2 2 - 3146004480 i j n + 3329378220 i j n + 70824697650 j n 3 2 - 43703039358 i j n + 1895218968 j n - 2771477760 i j n - 599519961 i n 2 2 2 + 227650414572 j n + 2552696880 i j + 27800989830 j n 2 2 3 2 2 - 135733082994 i j + 530173224 i n + 339579780 i n + 4958773116 j n 3 + 1108977484 j n ) f[i, 2 + j, 5 + n] - 324 (1 + n) (2 + n) (-2435759208 i 2 2 + 261257214 i + 6143120856 j - 1300275820 i j + 1504504934 j + 62433849 i n - 281874088 j n) f[i, 3 + j, n] - 6 (142241424003 i 2 2 3 - 571502357892 j - 55941068772 i - 350601102252 j - 4285629864 i 4 3 4 2 + 590475456 i - 75686061582 j - 6107924028 j + 4060071900 i n 3 3 3 2 + 13033447128 i j - 1275217386 i n - 1306820478 i j + 117914169366 i j 2 2 2 - 24371928378 i j + 5967273501 i n + 942800780 i j n 2 2 + 2228164622 i j n - 46103657754 j n + 19641770430 i j n 3 2 - 3830114044 j n + 2604790534 i j n + 32175245925 i n - 109731184848 j n 2 2 2 2 2 - 4857385194 i j + 392083806 j n + 320905048338 i j + 51241134 i n 3 2 2 3 + 95028348 i n - 1474270468 j n + 835168484 j n ) f[i, 3 + j, 3 + n] + 2 2 27 (-612624132 i + 2690738280 j + 288214227 i + 868196700 j 3 4 3 4 2 - 148997740 i + 8341956 i - 34889320 j - 12967392 j + 115614314 i n 3 3 3 2 + 30775944 i j - 14874068 i n - 16106148 i j + 40293048 i j 2 2 2 2 + 75381552 i j + 33383426 i n - 13644040 i j n + 27516276 i j n 2 3 2 + 262342832 j n - 340402460 i j n + 12084640 j n - 29438460 i j n 2 2 2 + 19017765 i n + 825156738 j n - 14422044 i j + 72383720 j n 2 2 3 2 2 - 1123678080 i j + 4722268 i n + 1809844 i n + 12631600 j n 3 + 2233912 j n ) f[i, 3 + j, 6 + n] - 108 (2 + n) (23405624235 i 2 3 - 5442322881 i + 286480878 i - 57236949483 j + 28014963724 i j 2 2 2 3 - 2158173092 i j - 32299509770 j + 5031664712 i j - 3722484080 j 2 + 270441033 i n - 153809667 i n + 2357872441 j n + 705316386 i j n 2 2 2 - 658666266 j n - 90395427 i n + 384733666 j n ) f[i, 4 + j, 1 + n] - ( 2 2 -350813646594 i + 1924693057080 j + 58253431338 i + 1401641874576 j 3 4 3 4 - 5593458150 i + 203436888 i + 246568373772 j + 12633689392 j 2 3 3 3 + 21151184166 i n - 17744449392 i j - 1180257264 i n - 3196812512 i j 2 2 2 - 245706310842 i j + 88354144194 i j + 2353262094 i n 2 2 2 - 2821265544 i j n + 9913853520 i j n + 165432428556 j n 3 2 - 129401379624 i j n + 17989200000 j n - 21963993768 i j n 2 2 - 78171066549 i n + 129927275442 j n + 11256946968 i j 2 2 2 3 - 24051369072 j n - 811652447862 i j + 615238668 i n + 361581708 i n 2 2 3 + 2634665064 j n - 1538934664 j n ) f[i, 4 + j, 4 + n] - 18 ( 2 2 -94091785380 i + 220570246368 j + 24380245872 i + 189975153480 j 3 4 3 4 - 2365543356 i + 77656848 i + 42421527344 j + 2799477808 j 2 3 3 3 - 731185284 i n - 5024542896 i j - 10206582 i n - 866893664 i j 2 2 2 2 - 55573311680 i j + 21912360716 i j + 1843424973 i n + 664952652 i j n 2 2 3 + 274226948 i j n - 5557210592 j n + 1926806188 i j n + 419342552 j n 2 2 2 - 717298844 i j n + 6638178231 i n - 51635213082 j n + 3235561932 i j 2 2 2 3 - 7800929370 j n - 159714614820 i j - 138688524 i n + 69344262 i n 2 2 3 - 946571184 j n - 232561368 j n ) f[i, 5 + j, 2 + n] + 6669 2 (-18 + i - 2 j - n) (-144243 i + 39750 i + 2893770 j - 181236 i j 2 2 3 2 + 486216 j - 9384 i j + 18768 j - 111492 i n + 6932 i n + 535716 j n 2 2 2 - 29360 i j n + 48128 j n - 6932 i n + 23248 j n ) f[i, 5 + j, 5 + n] - 73465704 (i - 2 j) (-216 + 15 i - 30 j - 17 n) (1 + n) (2 + n) f[i, 6 + j, n] + 1360476 (i - 2 j) (-18 + i - 2 j - n) 2 (-1320 + 137 i - 274 j + 177 n + 4 i n - 8 j n + 34 n ) f[i, 6 + j, 3 + n] 2 + 323614764 (2 + n) (3 + n) (64 i + 40 i - 71 j - 59 i j + 6 i n - 3 j n) 2 2 3 f[i + 1, j, 1 + n] - 5992866 (5176 i - 7725 j + 4320 i + 1301 j + 1088 i 4 3 4 2 3 3 3 + 96 i - 98 j + 6 j + 1180 i n - 110 i j + 144 i n - 440 i j 2 2 2 2 2 2 + 1855 i j - 3862 i j + 278 i n - 118 i j n - 456 i j n + 165 j n 2 2 2 2 - 2207 i j n + 192 i j n + 2098 i n - 2336 j n + 392 i j - 217 j n 2 2 3 3 - 9899 i j + 80 i n + 12 i n - 6 j n ) f[i + 1, j, 4 + n] - 323614764 2 2 2 (3 + n) (40 i + 40 i - 139 j - 95 i j - 51 j - 39 i j - 19 j n - 4 i j n 2 2 2 - 3 j n - j n ) f[i + 1, j + 1, 2 + n] - 5992866 (-52 i - 52 i + 1740 j 2 2 2 3 3 4 + 562 i j + 12 i j + 386 j + 38 i j - 2 j + 16 i j - 8 j - 8 i n 2 2 2 2 2 2 - 8 i n + 559 j n + 130 i j n + 93 j n + 59 j n + 8 i j n + 6 j n 3 + 2 j n ) f[i + 1, j + 1, 5 + 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 324*(1+n)*(2+n)*(-161807382-361402992*i+117562422*i^2+2186788311*j-357038332*i* j+345862676*j^2-53935794*n+39718416*i*n+378457301*j*n)-6*(-6310487898*n-\ 26047985508*i+139130517753*j+6818097780*i^2+11735231679*j^2+1079686332*i^3+ 101282616*i^4-4949594178*j^3+7342056*j^4-1456266438*n^2-107871588*n^3+ 2441810934*i^2*n-284363082*i*j^3+170786004*i^3*n-96481962*i^3*j+4751344374*i*j^ 2+10780624884*i^2*j+63337824*i*n^2-654148004*i*j*n^2+2886745852*i^2*j*n+ 6584892129*j^2*n+2420966475*i*j*n-1050093764*j^3*n+1665866084*i*j^2*n-\ 7654038300*i*n+72121389444*j*n-489469716*i^2*j^2+12177351159*j*n^2+18270318267* i*j+259096308*i^2*n^2-8737598628+71446344*i*n^3+745661146*j^2*n^2+738936004*j*n ^3)*Sn^3+221958*(-9+2*i+2*j-2*n)*(-6+i+j-n)*(-12*i+4*i^2-45*j+4*i*j+9*j^2-4*i*n -9*j*n)*Sn^6+108*(2+n)*(1341273078*i-380859096*i^2+679982424*i^3-29444607294*j+ 4802210545*i*j-2116467770*i^2*j-11338053458*j^2+1320164786*i*j^2-806165600*j^3-\ 507801171*i*n-168831486*i^2*n-12450237929*j*n+1500710373*i*j*n-2878454214*j^2*n -203573199*i*n^2-1089181301*j*n^2)*Sj*Sn-2*(48694390677*i-615115076571*j-\ 49587886395*i^2-123430227669*j^2+3242730060*i^3+572951328*i^4+19418908362*j^3+ 1995815626*j^4-11062831518*i^2*n-3431964366*i*j^3+362844864*i^3*n+533897836*i^3 *j-18610237392*i*j^2-29989392411*i^2*j-4883493123*i*n^2+3001420746*i*j*n^2-\ 5529289200*i^2*j*n-52777744590*j^2*n+31344447732*i*j*n+3045679698*j^3*n-\ 1305649506*i*j^2*n-4896918072*i*n-295597402254*j*n-2338557432*i^2*j^2-\ 45594920577*j*n^2+79088276808*i*j-337662972*i^2*n^2-407146398*i*n^3-5756908428* j^2*n^2-2178362602*j*n^3)*Sj*Sn^4+36*(7834259979*i+92076876306*j-8211061557*i^2 +56303580222*j^2-4042349490*i^3+548815242*i^4+7988016910*j^3+225479306*j^4-\ 1231144188*i^2*n-628088760*i*j^3-976094814*i^3*n-2662749358*i^3*j-2527334818*i* j^2+10023460834*i^2*j+627708555*i*n^2-2359503360*i*j*n^2+2760792700*i^2*j*n+ 28278373679*j^2*n-7420484152*i*j*n+2166578212*j^3*n-1547653732*i*j^2*n+ 2994620823*i*n+65674109148*j*n+3319038204*i^2*j^2+14612744025*j*n^2+941016798*i *j+397629918*i^2*n^2+254684835*i*n^3+3719079837*j^2*n^2+831733113*j*n^3)*Sj^2* Sn^2-(-71660872692*i+581111421372*j+44271304920*i^2+195726005532*j^2-\ 10699491042*i^3+474027420*i^4-15947928216*j^3-4448956288*j^4+7420759002*i^2*n+ 4428790272*i*j^3-1343780424*i^3*n-2791603876*i^3*j+575052462*i*j^2+35381671380* i^2*j+3383793090*i*n^2-3146004480*i*j*n^2+3329378220*i^2*j*n+70824697650*j^2*n-\ 43703039358*i*j*n+1895218968*j^3*n-2771477760*i*j^2*n-599519961*i*n+ 227650414572*j*n+2552696880*i^2*j^2+27800989830*j*n^2-135733082994*i*j+ 530173224*i^2*n^2+339579780*i*n^3+4958773116*j^2*n^2+1108977484*j*n^3)*Sj^2*Sn^ 5-324*(1+n)*(2+n)*(-2435759208*i+261257214*i^2+6143120856*j-1300275820*i*j+ 1504504934*j^2+62433849*i*n-281874088*j*n)*Sj^3-6*(142241424003*i-571502357892* j-55941068772*i^2-350601102252*j^2-4285629864*i^3+590475456*i^4-75686061582*j^3 -6107924028*j^4+4060071900*i^2*n+13033447128*i*j^3-1275217386*i^3*n-1306820478* i^3*j+117914169366*i*j^2-24371928378*i^2*j+5967273501*i*n^2+942800780*i*j*n^2+ 2228164622*i^2*j*n-46103657754*j^2*n+19641770430*i*j*n-3830114044*j^3*n+ 2604790534*i*j^2*n+32175245925*i*n-109731184848*j*n-4857385194*i^2*j^2+ 392083806*j*n^2+320905048338*i*j+51241134*i^2*n^2+95028348*i*n^3-1474270468*j^2 *n^2+835168484*j*n^3)*Sj^3*Sn^3+27*(-612624132*i+2690738280*j+288214227*i^2+ 868196700*j^2-148997740*i^3+8341956*i^4-34889320*j^3-12967392*j^4+115614314*i^2 *n+30775944*i*j^3-14874068*i^3*n-16106148*i^3*j+40293048*i*j^2+75381552*i^2*j+ 33383426*i*n^2-13644040*i*j*n^2+27516276*i^2*j*n+262342832*j^2*n-340402460*i*j* n+12084640*j^3*n-29438460*i*j^2*n+19017765*i*n+825156738*j*n-14422044*i^2*j^2+ 72383720*j*n^2-1123678080*i*j+4722268*i^2*n^2+1809844*i*n^3+12631600*j^2*n^2+ 2233912*j*n^3)*Sj^3*Sn^6-108*(2+n)*(23405624235*i-5442322881*i^2+286480878*i^3-\ 57236949483*j+28014963724*i*j-2158173092*i^2*j-32299509770*j^2+5031664712*i*j^2 -3722484080*j^3+270441033*i*n-153809667*i^2*n+2357872441*j*n+705316386*i*j*n-\ 658666266*j^2*n-90395427*i*n^2+384733666*j*n^2)*Sj^4*Sn-(-350813646594*i+ 1924693057080*j+58253431338*i^2+1401641874576*j^2-5593458150*i^3+203436888*i^4+ 246568373772*j^3+12633689392*j^4+21151184166*i^2*n-17744449392*i*j^3-1180257264 *i^3*n-3196812512*i^3*j-245706310842*i*j^2+88354144194*i^2*j+2353262094*i*n^2-\ 2821265544*i*j*n^2+9913853520*i^2*j*n+165432428556*j^2*n-129401379624*i*j*n+ 17989200000*j^3*n-21963993768*i*j^2*n-78171066549*i*n+129927275442*j*n+ 11256946968*i^2*j^2-24051369072*j*n^2-811652447862*i*j+615238668*i^2*n^2+ 361581708*i*n^3+2634665064*j^2*n^2-1538934664*j*n^3)*Sj^4*Sn^4-18*(-94091785380 *i+220570246368*j+24380245872*i^2+189975153480*j^2-2365543356*i^3+77656848*i^4+ 42421527344*j^3+2799477808*j^4-731185284*i^2*n-5024542896*i*j^3-10206582*i^3*n-\ 866893664*i^3*j-55573311680*i*j^2+21912360716*i^2*j+1843424973*i*n^2+664952652* i*j*n^2+274226948*i^2*j*n-5557210592*j^2*n+1926806188*i*j*n+419342552*j^3*n-\ 717298844*i*j^2*n+6638178231*i*n-51635213082*j*n+3235561932*i^2*j^2-7800929370* j*n^2-159714614820*i*j-138688524*i^2*n^2+69344262*i*n^3-946571184*j^2*n^2-\ 232561368*j*n^3)*Sj^5*Sn^2+6669*(-18+i-2*j-n)*(-144243*i+39750*i^2+2893770*j-\ 181236*i*j+486216*j^2-9384*i*j^2+18768*j^3-111492*i*n+6932*i^2*n+535716*j*n-\ 29360*i*j*n+48128*j^2*n-6932*i*n^2+23248*j*n^2)*Sj^5*Sn^5-73465704*(i-2*j)*(-\ 216+15*i-30*j-17*n)*(1+n)*(2+n)*Sj^6+1360476*(i-2*j)*(-18+i-2*j-n)*(-1320+137*i -274*j+177*n+4*i*n-8*j*n+34*n^2)*Sj^6*Sn^3+323614764*(2+n)*(3+n)*(64*i+40*i^2-\ 71*j-59*i*j+6*i*n-3*j*n)*Si*Sn-5992866*(5176*i-7725*j+4320*i^2+1301*j^2+1088*i^ 3+96*i^4-98*j^3+6*j^4+1180*i^2*n-110*i*j^3+144*i^3*n-440*i^3*j+1855*i*j^2-3862* i^2*j+278*i*n^2-118*i*j*n^2-456*i^2*j*n+165*j^2*n-2207*i*j*n+192*i*j^2*n+2098*i *n-2336*j*n+392*i^2*j^2-217*j*n^2-9899*i*j+80*i^2*n^2+12*i*n^3-6*j*n^3)*Si*Sn^4 -323614764*(3+n)*(40*i+40*i^2-139*j-95*i*j-51*j^2-39*i*j^2-19*j*n-4*i*j*n-3*j^2 *n-j*n^2)*Si*Sj*Sn^2-5992866*(-52*i-52*i^2+1740*j+562*i*j+12*i^2*j+386*j^2+38*i *j^2-2*j^3+16*i*j^3-8*j^4-8*i*n-8*i^2*n+559*j*n+130*i*j*n+93*j^2*n+59*j*n^2+8*i *j*n^2+6*j^2*n^2+2*j*n^3)*Si*Sj*Sn^5 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 - ----- 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->3 n, we get that f[0,0,3 n] satisfies 324 (1 + 3 n) (2 + 3 n) (-161807382 - 161807382 n) f[0, 0, 3 n] - 6 2 3 (-18931463694 n - 13106397942 n - 2912532876 n - 8737598628) f[0, 0, 3 + 3 n] = 0 But the very same recurrence is also satisfied by h(3 n):= (n - 1) 2 27 pochhammer(4/3, n - 1) pochhammer(5/3, 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