#inMishna7 steps := [[0,1],[-1,0],[1,-1]]: # must have length 3. offset := 3: closedform := (27^(-1 + n)*pochhammer(4/3, -1 + n)*pochhammer(5/3, -1 + n))/(pochhammer(3, -1 + n)*pochhammer(4, -1 + n)): 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 := 27*(1 + n)*(2 + n)*(3 + n)*f[i, j, n] + (-3 + 2*i + j - n)*(6 + i - j + n)* (9 + i + 2*j + n)*f[i, j, 3 + 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 `):