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 {[1, 1], [0, -1], [-1, 0]} 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 + 1, j + 1, n - 1] + f[i, j - 1, n - 1] + f[i - 1, j, 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 1458 (1 + n) (2 + n) (159 + 136 i - 68 j + 80 n + 9 n ) f[i, j, n] + 9 (-44478 2 2 2 - 482904 i j n - 41001 n - 181221 i - 105576 j - 13788 n + 130420 i 3 4 2 3 4 3 + 230800 i + 67888 i + 146560 j - 76568 j + 139120 j - 2013 n 4 2 2 2 2 - 108 n - 99288 i j n + 460440 i j n - 100668 i j n + 707820 i j 2 2 2 3 + 443604 i j + 130316 i j + 191808 i n + 122400 j n - 540608 i j 3 2 2 3 - 381864 i n - 132048 j n - 16164 j n - 116667 i n - 4896 i n 3 2 3 3 - 6120 j n - 660372 i j - 371924 i j + 142848 i n - 25878 j n 2 2 2 2 2 + 71940 i n + 50988 j n ) f[i, j, 3 + n] - (-21060 - 160152 i j n 2 2 3 - 15948 n - 969246 i + 59382 j - 4167 n + 480993 i + 244165 i 4 2 3 4 3 4 + 21886 i + 275232 j - 207332 j + 34480 j - 457 n - 18 n 2 2 2 2 2 - 259606 i j n + 151848 i j n - 33556 i j n + 218100 i j + 734634 i j 2 2 3 - 418482 i j + 219325 i n + 143470 j n - 156416 i j - 407910 i n 3 2 2 3 3 - 42928 j n - 20824 j n - 50857 i n - 1632 i n - 2040 j n 2 3 3 2 2 - 802518 i j - 118028 i j + 47480 i n - 41586 j n + 23980 i n 2 2 2 + 16996 j n ) f[i, j, 6 + n] + 54 (235536 i j n + 29349 i + 149382 j 2 3 4 2 3 4 + 159690 i - 200400 i + 204 i + 222159 j + 207660 j - 408 j 2 2 2 2 2 + 137675 i j n - 236136 i j n + 96992 i j n + 306 i j - 701676 i j 2 2 3 - 451641 i j - 137462 i n - 26777 j n + 816 i j + 202284 i n 3 2 2 3 3 2 + 69968 j n - 5893 j n + 63827 i n - 204 i n + 3060 j n + 701100 i j 3 3 2 2 2 2 - 714 i j - 67480 i n + 5901 j n - 64040 i n - 34052 j n ) 2 2 f[i, j + 1, 2 + n] + (-469848 i j n - 3466116 i + 689364 j + 2445516 i 3 4 2 3 4 + 914918 i + 7696 i + 758460 j - 927346 j - 15392 j - 1729387 i j n 2 2 2 2 2 + 466152 i j n - 193984 i j n + 11544 i j + 3158151 i j - 2822667 i j 2 2 3 3 + 1222792 i n + 568135 j n + 30784 i j - 1379574 i n - 135856 j n 2 2 3 3 2 - 34114 j n - 124594 i n + 408 i n - 6120 j n - 3123939 i j 3 3 2 2 2 2 - 26936 i j + 135368 i n + 149691 j n + 128080 i n + 68104 j n ) 2 3 f[i, j + 1, 5 + n] - 324 (2 + n) (52536 i - 50202 i + 204 i - 33009 j 2 2 2 3 + 73800 i j - 306 i j - 25524 j - 306 i j + 204 j + 18124 i n 2 2 - 16768 i n - 11411 j n + 25195 i j n - 8797 j n) f[i, 2 + j, 1 + n] + 3 2 4 3 (2717076 i - 2631694 i + 7288 i - 1709010 j + 3883759 i j + 7288 i j 2 2 2 3 4 2 - 1342069 j - 5466 i j - 3644 i j + 1822 j + 896840 i n - 840272 i n 2 2 2 2 - 563062 j n + 1256708 i j n - 436808 j n + 72496 i n - 67072 i n 2 2 2 2 - 45644 j n + 100780 i j n - 35188 j n ) f[i, 2 + j, 4 + n] + 49572 (2 i - j) (2 + i + j) (1 + n) (2 + n) f[i, 3 + j, n] - 54 (2 i - j) (2 + i + j) (4 + n) (211 + 34 n) f[i, 3 + j, 3 + n] + 162 ( 2 3 2 2 63579 i + 15192 i + 408 i - 21018 j - 28254 i j - 1326 i j + 3372 j 2 2 2 + 1020 i j + 45380 i n + 7988 i n - 10290 j n - 15062 i j n + 1124 j n 2 2 2 2 2 3 + 10465 i n + 884 i n - 800 j n - 1768 i j n + 884 i n ) 2 3 f[i + 1, j, 2 + n] - 6 (254940 i + 57967 i + 187 i - 56385 j - 119975 i j 2 2 3 2 + 26784 j - 1632 i j + 1768 j + 113065 i n + 14678 i n - 14103 j n 2 2 2 2 2 - 29768 i j n + 3776 j n + 17095 i n + 884 i n - 800 j n 2 3 - 1768 i j n + 884 i n ) f[i + 1, j, 5 + n] + 972 j (2 + n) (384 + 179 n) f[i + 1, j + 1, 1 + n] 2 - 9 j (23381 + 8248 n + 716 n ) f[i + 1, j + 1, 4 + n] - 148716 j (1 + n) (2 + n) f[i + 1, 2 + j, n] + 162 j (4 + n) (211 + 34 n) f[i + 1, 2 + j, 3 + n] + 5832 (2 + n) (104 i - 68 j + 63 i n - 68 j n) f[2 + i, j, 1 + n] - 54 2 2 (7377 i - 6752 j + 2760 i n - 2776 j n + 252 i n - 272 j n ) f[2 + i, j, 4 + n] - 99144 (i - 2 j) (1 + n) (2 + n) f[3 + i, j, n] + 108 (i - 2 j) (4 + n) (211 + 34 n) f[3 + i, j, 3 + 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 1458*(1+n)*(2+n)*(159+136*i-68*j+80*n+9*n^2)+9*(-44478-482904*i^2*j*n-41001*n-\ 181221*i-105576*j-13788*n^2+130420*i^2+230800*i^3+67888*i^4+146560*j^2-76568*j^ 3+139120*j^4-2013*n^3-108*n^4-99288*i*j*n+460440*i*j^2*n-100668*i*j*n^2+707820* i^2*j^2+443604*i*j^2+130316*i*j+191808*i^2*n+122400*j^2*n-540608*i*j^3-381864*i *n-132048*j^3*n-16164*j*n^2-116667*i*n^2-4896*i*n^3-6120*j*n^3-660372*i^2*j-\ 371924*i^3*j+142848*i^3*n-25878*j*n+71940*i^2*n^2+50988*j^2*n^2)*Sn^3-(-21060-\ 160152*i^2*j*n-15948*n-969246*i+59382*j-4167*n^2+480993*i^2+244165*i^3+21886*i^ 4+275232*j^2-207332*j^3+34480*j^4-457*n^3-18*n^4-259606*i*j*n+151848*i*j^2*n-\ 33556*i*j*n^2+218100*i^2*j^2+734634*i*j^2-418482*i*j+219325*i^2*n+143470*j^2*n-\ 156416*i*j^3-407910*i*n-42928*j^3*n-20824*j*n^2-50857*i*n^2-1632*i*n^3-2040*j*n ^3-802518*i^2*j-118028*i^3*j+47480*i^3*n-41586*j*n+23980*i^2*n^2+16996*j^2*n^2) *Sn^6+54*(235536*i^2*j*n+29349*i+149382*j+159690*i^2-200400*i^3+204*i^4+222159* j^2+207660*j^3-408*j^4+137675*i*j*n-236136*i*j^2*n+96992*i*j*n^2+306*i^2*j^2-\ 701676*i*j^2-451641*i*j-137462*i^2*n-26777*j^2*n+816*i*j^3+202284*i*n+69968*j^3 *n-5893*j*n^2+63827*i*n^2-204*i*n^3+3060*j*n^3+701100*i^2*j-714*i^3*j-67480*i^3 *n+5901*j*n-64040*i^2*n^2-34052*j^2*n^2)*Sj*Sn^2+(-469848*i^2*j*n-3466116*i+ 689364*j+2445516*i^2+914918*i^3+7696*i^4+758460*j^2-927346*j^3-15392*j^4-\ 1729387*i*j*n+466152*i*j^2*n-193984*i*j*n^2+11544*i^2*j^2+3158151*i*j^2-2822667 *i*j+1222792*i^2*n+568135*j^2*n+30784*i*j^3-1379574*i*n-135856*j^3*n-34114*j*n^ 2-124594*i*n^2+408*i*n^3-6120*j*n^3-3123939*i^2*j-26936*i^3*j+135368*i^3*n+ 149691*j*n+128080*i^2*n^2+68104*j^2*n^2)*Sj*Sn^5-324*(2+n)*(52536*i-50202*i^2+ 204*i^3-33009*j+73800*i*j-306*i^2*j-25524*j^2-306*i*j^2+204*j^3+18124*i*n-16768 *i^2*n-11411*j*n+25195*i*j*n-8797*j^2*n)*Sj^2*Sn+3*(2717076*i-2631694*i^2+7288* i^4-1709010*j+3883759*i*j+7288*i^3*j-1342069*j^2-5466*i^2*j^2-3644*i*j^3+1822*j ^4+896840*i*n-840272*i^2*n-563062*j*n+1256708*i*j*n-436808*j^2*n+72496*i*n^2-\ 67072*i^2*n^2-45644*j*n^2+100780*i*j*n^2-35188*j^2*n^2)*Sj^2*Sn^4+49572*(2*i-j) *(2+i+j)*(1+n)*(2+n)*Sj^3-54*(2*i-j)*(2+i+j)*(4+n)*(211+34*n)*Sj^3*Sn^3+162*( 63579*i+15192*i^2+408*i^3-21018*j-28254*i*j-1326*i^2*j+3372*j^2+1020*i*j^2+ 45380*i*n+7988*i^2*n-10290*j*n-15062*i*j*n+1124*j^2*n+10465*i*n^2+884*i^2*n^2-\ 800*j*n^2-1768*i*j*n^2+884*i*n^3)*Si*Sn^2-6*(254940*i+57967*i^2+187*i^3-56385*j -119975*i*j+26784*j^2-1632*i*j^2+1768*j^3+113065*i*n+14678*i^2*n-14103*j*n-\ 29768*i*j*n+3776*j^2*n+17095*i*n^2+884*i^2*n^2-800*j*n^2-1768*i*j*n^2+884*i*n^3 )*Si*Sn^5+972*j*(2+n)*(384+179*n)*Si*Sj*Sn-9*j*(23381+8248*n+716*n^2)*Si*Sj*Sn^ 4-148716*j*(1+n)*(2+n)*Si*Sj^2+162*j*(4+n)*(211+34*n)*Si*Sj^2*Sn^3+5832*(2+n)*( 104*i-68*j+63*i*n-68*j*n)*Si^2*Sn-54*(7377*i-6752*j+2760*i*n-2776*j*n+252*i*n^2 -272*j*n^2)*Si^2*Sn^4-99144*(i-2*j)*(1+n)*(2+n)*Si^3+108*(i-2*j)*(4+n)*(211+34* n)*Si^3*Sn^3 The proof that this opeator indeed annihilates f[i,j,n] is routine. Indeed, f[i,j,n] is annihilated by the operator 1 1 Sn - Si Sj - ---- - ---- Sj Si 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 2 1458 (1 + 3 n) (2 + 3 n) (159 + 240 n + 81 n ) f[0, 0, 3 n] 2 3 4 + 9 (-44478 - 123003 n - 124092 n - 54351 n - 8748 n ) f[0, 0, 3 + 3 n] 2 3 4 - (-21060 - 47844 n - 37503 n - 12339 n - 1458 n ) f[0, 0, 6 + 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