#inMishna6 steps := [[0,1],[1,0],[-1,-1]]: # must have length 3. offset := 3: closedform := 2*27^(n-1)*pochhammer(4/3,n-1)*pochhammer(5/3,n-1)/pochhammer(5/2,n-1)/pochhammer(3,n-1): obviousrec := f[i,j,n]=f[i+steps[1,1],j+steps[1,2],n-1]+f[i+steps[2,1],j+steps[2,2],n-1]+ f[i+steps[3,1],j+steps[3,2],n-1]: operator := Sn - (Si^steps[1,1]*Sj^steps[1,2]+Si^steps[2,1]*Sj^steps[2,2]+Si^steps[3,1]*Sj^steps[3,2]): gu := 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)*f[i, j, n] - 6*(-8737598628 - 26047985508*i + 6818097780*i^2 + 1079686332*i^3 + 101282616*i^4 + 139130517753*j + 18270318267*i*j + 10780624884*i^2*j - 96481962*i^3*j + 11735231679*j^2 + 4751344374*i*j^2 - 489469716*i^2*j^2 - 4949594178*j^3 - 284363082*i*j^3 + 7342056*j^4 - 6310487898*n - 7654038300*i*n + 2441810934*i^2*n + 170786004*i^3*n + 72121389444*j*n + 2420966475*i*j*n + 2886745852*i^2*j*n + 6584892129*j^2*n + 1665866084*i*j^2*n - 1050093764*j^3*n - 1456266438*n^2 + 63337824*i*n^2 + 259096308*i^2*n^2 + 12177351159*j*n^2 - 654148004*i*j*n^2 + 745661146*j^2*n^2 - 107871588*n^3 + 71446344*i*n^3 + 738936004*j*n^3)*f[i, j, 3 + n] + 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)*f[i, j, 6 + n] + 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)* f[i, 1 + j, 1 + n] - 2*(48694390677*i - 49587886395*i^2 + 3242730060*i^3 + 572951328*i^4 - 615115076571*j + 79088276808*i*j - 29989392411*i^2*j + 533897836*i^3*j - 123430227669*j^2 - 18610237392*i*j^2 - 2338557432*i^2*j^2 + 19418908362*j^3 - 3431964366*i*j^3 + 1995815626*j^4 - 4896918072*i*n - 11062831518*i^2*n + 362844864*i^3*n - 295597402254*j*n + 31344447732*i*j*n - 5529289200*i^2*j*n - 52777744590*j^2*n - 1305649506*i*j^2*n + 3045679698*j^3*n - 4883493123*i*n^2 - 337662972*i^2*n^2 - 45594920577*j*n^2 + 3001420746*i*j*n^2 - 5756908428*j^2*n^2 - 407146398*i*n^3 - 2178362602*j*n^3)* f[i, 1 + j, 4 + n] + 36*(7834259979*i - 8211061557*i^2 - 4042349490*i^3 + 548815242*i^4 + 92076876306*j + 941016798*i*j + 10023460834*i^2*j - 2662749358*i^3*j + 56303580222*j^2 - 2527334818*i*j^2 + 3319038204*i^2*j^2 + 7988016910*j^3 - 628088760*i*j^3 + 225479306*j^4 + 2994620823*i*n - 1231144188*i^2*n - 976094814*i^3*n + 65674109148*j*n - 7420484152*i*j*n + 2760792700*i^2*j*n + 28278373679*j^2*n - 1547653732*i*j^2*n + 2166578212*j^3*n + 627708555*i*n^2 + 397629918*i^2*n^2 + 14612744025*j*n^2 - 2359503360*i*j*n^2 + 3719079837*j^2*n^2 + 254684835*i*n^3 + 831733113*j*n^3)* f[i, 2 + j, 2 + n] - (-71660872692*i + 44271304920*i^2 - 10699491042*i^3 + 474027420*i^4 + 581111421372*j - 135733082994*i*j + 35381671380*i^2*j - 2791603876*i^3*j + 195726005532*j^2 + 575052462*i*j^2 + 2552696880*i^2*j^2 - 15947928216*j^3 + 4428790272*i*j^3 - 4448956288*j^4 - 599519961*i*n + 7420759002*i^2*n - 1343780424*i^3*n + 227650414572*j*n - 43703039358*i*j*n + 3329378220*i^2*j*n + 70824697650*j^2*n - 2771477760*i*j^2*n + 1895218968*j^3*n + 3383793090*i*n^2 + 530173224*i^2*n^2 + 27800989830*j*n^2 - 3146004480*i*j*n^2 + 4958773116*j^2*n^2 + 339579780*i*n^3 + 1108977484*j*n^3)* f[i, 2 + j, 5 + n] - 324*(1 + n)*(2 + n)*(-2435759208*i + 261257214*i^2 + 6143120856*j - 1300275820*i*j + 1504504934*j^2 + 62433849*i*n - 281874088*j*n)*f[i, 3 + j, n] - 6*(142241424003*i - 55941068772*i^2 - 4285629864*i^3 + 590475456*i^4 - 571502357892*j + 320905048338*i*j - 24371928378*i^2*j - 1306820478*i^3*j - 350601102252*j^2 + 117914169366*i*j^2 - 4857385194*i^2*j^2 - 75686061582*j^3 + 13033447128*i*j^3 - 6107924028*j^4 + 32175245925*i*n + 4060071900*i^2*n - 1275217386*i^3*n - 109731184848*j*n + 19641770430*i*j*n + 2228164622*i^2*j*n - 46103657754*j^2*n + 2604790534*i*j^2*n - 3830114044*j^3*n + 5967273501*i*n^2 + 51241134*i^2*n^2 + 392083806*j*n^2 + 942800780*i*j*n^2 - 1474270468*j^2*n^2 + 95028348*i*n^3 + 835168484*j*n^3)* f[i, 3 + j, 3 + n] + 27*(-612624132*i + 288214227*i^2 - 148997740*i^3 + 8341956*i^4 + 2690738280*j - 1123678080*i*j + 75381552*i^2*j - 16106148*i^3*j + 868196700*j^2 + 40293048*i*j^2 - 14422044*i^2*j^2 - 34889320*j^3 + 30775944*i*j^3 - 12967392*j^4 + 19017765*i*n + 115614314*i^2*n - 14874068*i^3*n + 825156738*j*n - 340402460*i*j*n + 27516276*i^2*j*n + 262342832*j^2*n - 29438460*i*j^2*n + 12084640*j^3*n + 33383426*i*n^2 + 4722268*i^2*n^2 + 72383720*j*n^2 - 13644040*i*j*n^2 + 12631600*j^2*n^2 + 1809844*i*n^3 + 2233912*j*n^3)*f[i, 3 + j, 6 + n] - 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)*f[i, 4 + j, 1 + n] - (-350813646594*i + 58253431338*i^2 - 5593458150*i^3 + 203436888*i^4 + 1924693057080*j - 811652447862*i*j + 88354144194*i^2*j - 3196812512*i^3*j + 1401641874576*j^2 - 245706310842*i*j^2 + 11256946968*i^2*j^2 + 246568373772*j^3 - 17744449392*i*j^3 + 12633689392*j^4 - 78171066549*i*n + 21151184166*i^2*n - 1180257264*i^3*n + 129927275442*j*n - 129401379624*i*j*n + 9913853520*i^2*j*n + 165432428556*j^2*n - 21963993768*i*j^2*n + 17989200000*j^3*n + 2353262094*i*n^2 + 615238668*i^2*n^2 - 24051369072*j*n^2 - 2821265544*i*j*n^2 + 2634665064*j^2*n^2 + 361581708*i*n^3 - 1538934664*j*n^3)*f[i, 4 + j, 4 + n] - 18*(-94091785380*i + 24380245872*i^2 - 2365543356*i^3 + 77656848*i^4 + 220570246368*j - 159714614820*i*j + 21912360716*i^2*j - 866893664*i^3*j + 189975153480*j^2 - 55573311680*i*j^2 + 3235561932*i^2*j^2 + 42421527344*j^3 - 5024542896*i*j^3 + 2799477808*j^4 + 6638178231*i*n - 731185284*i^2*n - 10206582*i^3*n - 51635213082*j*n + 1926806188*i*j*n + 274226948*i^2*j*n - 5557210592*j^2*n - 717298844*i*j^2*n + 419342552*j^3*n + 1843424973*i*n^2 - 138688524*i^2*n^2 - 7800929370*j*n^2 + 664952652*i*j*n^2 - 946571184*j^2*n^2 + 69344262*i*n^3 - 232561368*j*n^3)*f[i, 5 + j, 2 + n] + 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)* 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)* (-1320 + 137*i - 274*j + 177*n + 4*i*n - 8*j*n + 34*n^2)* f[i, 6 + j, 3 + n] + 323614764*(2 + n)*(3 + n)* (64*i + 40*i^2 - 71*j - 59*i*j + 6*i*n - 3*j*n)*f[1 + i, j, 1 + n] - 5992866*(5176*i + 4320*i^2 + 1088*i^3 + 96*i^4 - 7725*j - 9899*i*j - 3862*i^2*j - 440*i^3*j + 1301*j^2 + 1855*i*j^2 + 392*i^2*j^2 - 98*j^3 - 110*i*j^3 + 6*j^4 + 2098*i*n + 1180*i^2*n + 144*i^3*n - 2336*j*n - 2207*i*j*n - 456*i^2*j*n + 165*j^2*n + 192*i*j^2*n + 278*i*n^2 + 80*i^2*n^2 - 217*j*n^2 - 118*i*j*n^2 + 12*i*n^3 - 6*j*n^3)* f[1 + i, j, 4 + n] - 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)* f[1 + i, 1 + j, 2 + n] - 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)*f[1 + i, 1 + j, 5 + n]: # no further changes needed below. print(`Lattice Walks in the Quarter-Plane`): print(): print(`By Shalosh B. Ekhad (c/o D. Zeilberger), and Manuel Kauers' computer`): print(): print(`Theorem`): print(`Let f[i,j,n] be the number of walks from the origin,`): print(`to the point (i,j), with exactly n steps, staying in the`): print(`first quarter-plane i>=0, j>=0, using the steps`): print({op(steps)}): print(`Then `): print(f[0,0,offset*n]= closedform ): print(): print(`Proof: By using the obvious recurrence `): print(obviousrec): print(`For n>=1, i>=0, j>=0 `): print(`subject to the initial conditions `): print(`f[0,0,0]=1, f[i,j,0]=0 if`, (i,j)<>(0,0) ): print(`and boundary conditions: `): print(f[-1,j,n]=0, f[i,-1,n]=0 ): print(`the computer first generates lots of data`): print(`and then using the quasi-holonomic ANSATZ `): print(`as described in Manuel Kauers and Doron Zeilberger's `): print(`seminal paper : The quasi-holonomic ansatz and restricted `): print(`lattice paths `): print(`finds the following partial recurrence equation `): print(gu=0): Gu:=gu: for i0 from 0 to 20 do for j0 from 0 to 20 do for n0 from 0 to 20 do Gu:=subs(f[i+i0,j+j0,n+n0]=Si^i0*Sj^j0*Sn^n0,Gu): od: od: od: print(`Let Si, Sj, Sn be the fundamental shift operators in the`): print(` i, j, and n , directions, respectively `): print(`The above lemma means that f[i,j,n] is annihilated by the operator`): lprint(Gu); print(`The proof that this opeator indeed annihilates f[i,j,n] `): print(`is routine.`): print(`Indeed, f[i,j,n] is annihilated by the operator `): print(operator): print(): print(`taking successive commatators we eventually get the 0 operator `): print(`and all we have to do is check that the inital conditions `): print(` for the intermediate operators also hold, that is a (fast!)`): print(`routine verification . `): printf("Plugging-in i=0,j=0,n->%g n, we get that f[0,0,%g n] satisfies\n", offset, offset): gu00:=subs({i=0,j=0,n=offset*n},gu): print(gu00=0): printf("But the very same recurrence is also satisfied by h(%g n):=\n", offset): print(closedform): print(`since plugging this last expression indeed gives`): mu00:=subs({f[0,0,offset*n]=closedform, f[0,0,offset*n+offset]=subs(n=n+1,closedform), f[0,0,offset*n+2*offset]=subs(n=n+2,closedform), f[0,0,offset*n+3*offset]=subs(n=n+3,closedform), f[0,0,offset*n+4*offset]=subs(n=n+4,closedform)},gu00): mu00:=normal(simplify(mu00/closedform)): print(mu00): print(`Since the theorem is true for n=0,1,2,3 (check!) `): print(`It is true in general. QED `):