Theorem: Let F(m,n) be the number of lattice paths from (0,0) to (m,n) in the positive quadrant of the two-dimensional square lattice where the Fundamental Steps are {[0, 1], [1, 0], [0, 2], [2, 0]} Let M and N be the shift operators in the m and n directions, respectively (M f(m,n):=f(m+1,n), Nf(m,n):=f(m,n+1) ) Then F(m,n) satisfies the following pure recurrences (n + m + 3) (n + m + 2) F(m, n) 4/5 ------------------------------- (m + 4) (m + 2) 2 (2 m n + 5 n + 26 + 4 m + 21 m) (n + m + 3) F(m + 1, n) + 2/5 -------------------------------------------------------- (m + 4) (m + 3) (m + 2) 2 2 (-54 - 17 n + n - 33 m - 6 m n - 5 m ) F(m + 2, n) + 1/5 --------------------------------------------------- (m + 3) (m + 4) (34 + 5 n + 9 m) F(m + 3, n) - 1/5 ---------------------------- + F(m + 4, n) = 0 m + 4 (n + m + 3) (n + m + 2) F(m, n) 4/5 ------------------------------- (n + 4) (n + 2) 2 (5 m + 2 m n + 26 + 4 n + 21 n) (n + m + 3) F(m, n + 1) + 2/5 -------------------------------------------------------- (n + 4) (n + 3) (n + 2) 2 2 (54 + 17 m - m + 33 n + 6 m n + 5 n ) F(m, n + 2) - 1/5 -------------------------------------------------- (n + 3) (n + 4) (34 + 5 m + 9 n) F(m, n + 3) - 1/5 ---------------------------- + F(m, n + 4) = 0 n + 4 Proof: We will only do the first recurrence We have to prove that F(m,n) is annihilated by the operator, let's call it Q\ := 2 4 (n + m + 3) (n + m + 2) 2 (2 m n + 5 n + 26 + 4 m + 21 m) (n + m + 3) M ------------------------- + ------------------------------------------------ 5 (m + 4) (m + 2) 5 (m + 4) (m + 3) (m + 2) 2 2 2 3 (-54 - 17 n + n - 33 m - 6 m n - 5 m ) M (34 + 5 n + 9 m) M 4 + ------------------------------------------ - ------------------- + M 5 (m + 3) (m + 4) 5 (m + 4) or equivalenty 3 3 4 2 4 4 2 72 + 44 m n + 4 m + 5 m M + 45 m M + 120 M + 32 m + 156 M + 60 n + 84 m 2 2 2 2 2 2 2 + 12 n + 4 m n + 8 m n + 4 M m n + 12 M m n - 29 M m n - 108 M 3 4 3 3 2 3 2 2 3 2 - 204 M + 130 m M - 9 m M - 79 m M + 66 m M - 120 m M - 5 m M 3 3 2 2 2 2 2 + 8 m M + 178 m M - 224 m M - 43 m M + 82 M n + 10 M n + 2 M n 2 2 2 2 2 3 2 3 + 64 M m n - 34 M n + M m n - 6 M m n - 5 M m n - 25 M m n 3 - 30 M n We know, by the obvious combinatorics, that F(m,n) is annihilated by 2 2 2 2 2 2 N M - N M - N M - M - N The sequence of successive commutators is 2 [-8 (m + 3) (2 m + 2 n + 7) N 2 2 2 + (-48 m n - 4 n - 156 n - 52 m - 356 m - 612) M N 2 2 2 + (-32 m n - 24 m - 176 m - 8 n - 120 n - 328) M 2 2 2 + (-256 m - 528 - 32 m - 40 m n - 160 n - 8 n ) M N 2 2 2 2 + (204 + 4 m n + 50 m + 4 m + 60 n + 4 n ) M N 2 2 3 + (-48 m n - 8 n - 176 n - 360 m - 684 - 48 m ) M 2 2 3 + (-56 m n - 8 n - 212 n - 476 m - 960 - 60 m ) M N 2 2 3 2 + (1626 + 72 m n + 829 m + 109 m + 271 n + 7 n ) M N 2 2 4 + (30 m + 24 m n + 232 m + 82 n - 2 n + 452) M 2 2 4 + (36 m + 284 m + 22 m n + 564 + 74 n - 2 n ) M N 2 2 4 2 + (-236 - 10 m n - 79 m - 5 m - 36 n + 2 n ) M N 2 5 + (54 m + 424 m + 836 + 20 m n + 70 n) M 2 5 + (70 n + 469 m + 59 m + 936 + 20 m n) M N 2 5 2 2 6 + (-79 m - 20 m n - 619 m - 70 n - 1216) M N - 30 (m + 4) M 2 6 2 6 2 7 3 - 30 (m + 4) M N + 30 (m + 4) M N , (3328 + 672 m + 80 n) M N 4 3 7 + (-376 - 40 m - 32 n) M N + (-1064 - 40 n - 216 m) M 5 2 5 + (-2664 - 576 m - 160 n) M N + (2384 + 480 m + 224 n) M N 6 3 4 + (-1424 - 288 m - 88 n) M N + (-464 m - 160 n - 2208) M N 5 4 3 3 + (174 n + 3260 + 650 m) M N + (208 n + 512 m + 2352) M N 2 3 8 8 4 + (64 n + 160 m + 704) M N + (120 m + 600) M + (120 m + 600) M N 5 3 3 2 + (-5032 - 1016 m - 316 n) M N + (1840 + 416 m + 192 n) M N 2 4 8 + (96 m + 16 n + 264) M N + (240 m + 1200) M N 7 4 + (-2348 - 472 m - 80 n) M N + (448 + 64 n + 96 m) M 8 3 6 2 + (-240 m - 1200) M N + (-472 - 126 m) M N 2 2 7 4 + (128 m + 64 n + 544) M N + (-40 n - 2044 - 416 m) M N 4 6 3 + (1280 + 256 m + 160 n) M N + (464 + 60 m + 32 n) M N 4 4 6 + (-84 n - 1320 - 318 m) M N + (-584 - 48 n - 120 m) M 4 6 4 + (160 m + 32 n + 576) M N + (8 n + 596 + 158 m) M N 4 2 8 2 + (656 + 136 m + 80 n) M N + (-120 m - 600) M N 5 4 7 2 + (912 + 96 n + 192 m) M + (32 m + 96) N + (1824 + 376 m + 40 n) M N , 2 2 2 2 2 2 2 2 2 6 6 M (N M - N M - N M - M - N ) (2 N M - N - 2 N M - 2 M) (20 N M 2 5 2 4 2 3 2 2 6 5 - 56 N M - 5 N M + 84 N M - 48 N M - 16 N - 20 N M + 46 N M 4 3 2 6 5 4 3 2 + 32 N M - 56 N M - 32 N M - 20 M + 36 M + 20 M - 32 M - 16 M )] 2 2 2 2 2 2 As you can see, the last entry, 6 M (N M - N M - N M - M - N ) 2 2 2 6 2 5 2 4 2 3 (2 N M - N - 2 N M - 2 M) (20 N M - 56 N M - 5 N M + 84 N M 2 2 6 5 4 3 2 - 48 N M - 16 N - 20 N M + 46 N M + 32 N M - 56 N M - 32 N M 6 5 4 3 2 - 20 M + 36 M + 20 M - 32 M - 16 M ), is a multiple of , 2 2 2 2 2 2 N M - N M - N M - M - N The proof follows by backwards induction, after checking the boundary condit\ ions QED . ------------------------------------------------------ The whole thing took , 12.163, seconds of CPU time