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 {[2, 2], [0, 1], [1, 0], [1, 1]} 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 2 2 - (n - 2 - 2 m) (n - 3 - 2 m) (4 n - 9 m n - 22 n + 19 m + 22 + 4 m ) F(m, n)/ 2 3 4 ((m + 4) (2 n - 2 - m) %1) + (344 - 806 n + 588 n - 166 n + 16 n + 842 m 2 3 2 2 2 2 3 - 1374 m n + 640 m n - 88 m n + 733 m - 754 m n + 169 m n + 271 m 3 4 - 133 m n + 36 m ) F(m + 1, n)/((m + 4) (2 n - 2 - m) %1) - (104 - 332 n 2 3 4 2 3 2 + 344 n - 156 n + 24 n + 262 m - 585 m n + 395 m n - 86 m n + 235 m 2 2 2 3 3 4 - 329 m n + 108 m n + 89 m - 59 m n + 12 m ) F(m + 2, n)/((m + 4) 2 3 4 (2 n - 2 - m) %1) - (52 - 120 n + 124 n - 72 n + 16 n + 116 m - 199 m n 2 3 2 2 2 2 3 3 + 149 m n - 48 m n + 91 m - 110 m n + 47 m n + 31 m - 21 m n 4 + 4 m ) F(m + 3, n)/((m + 4) (2 n - 2 - m) %1) + F(m + 4, n) = 0 2 2 %1 := 4 n - 9 m n - 13 n + 4 m + 11 m + 7 2 2 (-m + 2 + 2 n) (-m + 3 + 2 n) (4 n + 19 n - 9 m n + 22 - 22 m + 4 m ) F(m, n)/ 2 3 4 ((n + 4) (n + 2 - 2 m) %1) - (344 - 806 m + 588 m - 166 m + 16 m + 842 n 2 3 2 2 2 2 3 - 1374 m n + 640 m n - 88 m n + 733 n - 754 m n + 169 m n + 271 n 3 4 - 133 m n + 36 n ) F(m, n + 1)/((n + 4) (n + 2 - 2 m) %1) + (104 - 332 m 2 3 4 2 3 2 + 344 m - 156 m + 24 m + 262 n - 585 m n + 395 m n - 86 m n + 235 n 2 2 2 3 3 4 - 329 m n + 108 m n + 89 n - 59 m n + 12 n ) F(m, n + 2)/((n + 4) 2 3 4 (n + 2 - 2 m) %1) + (52 - 120 m + 124 m - 72 m + 16 m + 116 n - 199 m n 2 3 2 2 2 2 3 3 + 149 m n - 48 m n + 91 n - 110 m n + 47 m n + 31 n - 21 m n 4 + 4 n ) F(m, n + 3)/((n + 4) (n + 2 - 2 m) %1) + F(m, n + 4) = 0 2 2 %1 := 4 n + 11 n - 9 m n + 4 m - 13 m + 7 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 2 (n - 2 - 2 m) (n - 3 - 2 m) (4 n - 9 m n - 22 n + 19 m + 22 + 4 m ) - -------------------------------------------------------------------- + (344 (m + 4) (2 n - 2 - m) %1 2 3 4 2 3 - 806 n + 588 n - 166 n + 16 n + 842 m - 1374 m n + 640 m n - 88 m n 2 2 2 2 3 3 4 + 733 m - 754 m n + 169 m n + 271 m - 133 m n + 36 m ) M/((m + 4) 2 3 4 (2 n - 2 - m) %1) - (104 - 332 n + 344 n - 156 n + 24 n + 262 m 2 3 2 2 2 2 3 - 585 m n + 395 m n - 86 m n + 235 m - 329 m n + 108 m n + 89 m 3 4 2 2 - 59 m n + 12 m ) M /((m + 4) (2 n - 2 - m) %1) - (52 - 120 n + 124 n 3 4 2 3 2 2 - 72 n + 16 n + 116 m - 199 m n + 149 m n - 48 m n + 91 m - 110 m n 2 2 3 3 4 3 4 + 47 m n + 31 m - 21 m n + 4 m ) M /((m + 4) (2 n - 2 - m) %1) + M 2 2 %1 := 4 n - 9 m n - 13 n + 4 m + 11 m + 7 or equivalenty 4 3 2 2 2 2 3 -132 + 344 M + 242 n - 334 m - 16 m - 52 M + 332 M n - 344 M n + 156 M n 2 4 3 3 2 3 3 3 4 2 2 - 24 M n + 120 M n - 124 M n + 72 M n - 16 M n - 156 n - 104 M 4 4 3 4 2 4 2 4 3 + 252 M m n + 8 M m n + 121 M m n - 122 M m n + 32 M n 4 2 4 2 4 3 - 136 M n + 160 M n + 588 M n + 16 M n - 166 M n + 457 m n 2 4 3 3 2 2 2 3 - 192 m n - 4 n + 52 m n + 25 m n + 274 m n - 56 m n - 116 m 2 4 4 2 2 4 3 2 3 - 302 m - 56 M - 22 M m n + 17 M m n - 806 M n - 91 m M 4 2 2 2 2 3 4 2 4 4 4 - 12 m M - 235 m M - 262 m M - 35 m M - 105 m M - 4 m M 3 4 3 3 4 3 3 + 271 m M + 36 m M - 31 m M - 4 m M + 42 n - 1374 M m n 2 3 2 2 2 3 + 640 M m n - 88 M m n - 754 M m n + 169 M m n - 133 M m n 2 2 2 2 3 2 2 2 2 2 + 585 M m n - 395 M m n + 86 M m n + 329 M m n - 108 M m n 2 3 3 3 2 3 3 3 2 + 59 M m n + 199 M m n - 149 M m n + 48 M m n + 110 M m n 3 2 2 3 3 2 4 3 2 - 47 M m n + 21 M m n + 733 m M + 842 m M - 130 m M - 89 m M 3 - 116 m M We know, by the obvious combinatorics, that F(m,n) is annihilated by 2 2 2 2 M N - 1 - M N - M N - M N The sequence of successive commutators is 2 2 [-(n - 3 - 2 m) (9 n - 19 m n - 44 n + 28 + 6 m + 26 m) M N 2 + (n - 2 - 2 m) (n - 3 - 2 m) (7 n - 23 - 10 m) M N + (1094 - 993 n 2 2 2 3 2 3 + 1294 m + 213 n - 748 m n + 75 m n - 139 m n + 65 m + 505 m - 10 n ) 2 2 2 2 M N + (332 - 445 n + 709 m + 179 n - 593 m n + 116 m n - 189 m n 3 2 3 2 2 2 + 98 m + 469 m - 22 n ) M N + (-2022 + 2793 n - 2688 m - 1105 n 2 2 3 2 3 3 + 2373 m n - 454 m n + 499 m n - 166 m - 1166 m + 122 n ) M N + (-388 2 2 2 3 2 + 35 n - 375 m - 85 n + 173 m n - 152 m n + 133 m n - 48 m - 179 m 3 3 2 2 2 + 58 n ) M N + (348 - 700 n + 528 m + 314 n - 569 m n + 124 m n 2 3 2 3 4 2 - 107 m n + 32 m + 238 m - 60 n ) M N + (106 - 116 n + 121 m + 30 n 2 2 3 2 3 4 2 - 139 m n - 110 m n + 47 m n - 4 m + 71 m + 60 n ) M N + (204 2 2 2 3 2 - 176 n + 206 m + 102 n - 147 m n + 64 m n - 39 m n + 10 m + 72 m 3 5 2 2 2 - 40 n ) M N + (-34 + 320 n - 205 m + 42 n + 195 m n + 96 m n - 25 m n 3 2 3 5 2 - 8 m - 125 m - 40 n ) M N 2 2 6 - (2 n - 2 - m) (8 n - 28 m n - 86 n + 80 + 15 m + 75 m) M N + (56 2 2 2 3 2 - 172 n + 136 m - 44 n - 56 m n - 40 m n + 14 m n + 2 m + 52 m 3 6 2 2 2 2 2 + 16 n ) M N , (14 m n + 46 m + 8 m - 10 n + 26 n + 60) M N 2 3 + 2 (17 n - 58 - 26 m) (n - 3 - 2 m) M N 2 4 - 4 (n - 2 - 2 m) (n - 3 - 2 m) M N 2 2 3 2 + (230 m n - 368 m - 84 m - 92 n + 596 n - 364) M N 2 2 3 3 + (10 n - 382 n + 1240 + 134 m - 100 m n + 850 m) M N 2 2 3 4 + (-186 m + 110 n - 18 n - 268 - 20 m + 34 m n) M N 2 2 4 2 + (316 m n - 1658 m - 252 m - 32 n + 1236 n - 2644) M N 2 2 4 3 + (-376 n + 2360 n - 3280 - 776 m + 1124 m n - 3208 m) M N 2 2 4 4 + (1050 m - 616 n - 96 n + 1176 + 88 m + 50 m n) M N 2 2 5 2 + (-1122 m n + 2828 m + 508 m + 598 n - 3102 n + 3924) M N 2 2 5 3 + (120 n - 404 n + 2616 + 240 m - 204 m n + 1528 m) M N 2 2 5 4 + (-90 m - 290 n - 206 n - 1048 - 104 m + 270 m n) M N 2 2 6 2 + (130 m n - 476 m - 76 m - 12 n + 596 n - 552) M N 2 2 6 3 + (128 n - 72 n - 816 + 52 m - 220 m n - 284 m) M N 2 2 6 4 + (-506 m - 372 n + 284 n - 1072 + 144 m - 586 m n) M N 2 2 7 2 + (16 m n - 80 m - 8 m - 24 n + 4 n - 248) M N 2 2 7 3 + (-160 n - 952 n + 524 + 106 m - 80 m n + 726 m) M N 2 2 7 4 + (84 m + 932 n - 104 n + 1308 - 132 m + 416 m n) M N 8 2 - 4 (2 n - 2 - m) (10 n - 8 m - 19) M N 2 2 8 3 + (64 n + 512 n - 320 - 52 m + 48 m n - 384 m) M N 2 2 8 4 + (-328 - 360 n + 72 m + 16 n - 104 m n + 40 m ) M N , 9 5 3 5 (-2892 - 1656 n + 408 m) M N + (-24 n + 72 + 48 m) M N 7 6 10 5 + (1008 m - 834 n + 222) M N + (-168 m + 744 + 528 n) M N 5 3 9 3 + (-528 n + 498 + 294 m) M N + (-24 m + 72 n + 96) M N 5 4 5 5 + (-12 m - 288 n - 1182) M N + (330 n - 552 - 540 m) M N 3 3 7 3 + (6 n - 84 - 30 m) M N + (942 n - 3102 - 888 m) M N 9 6 4 4 + (3504 + 456 n + 432 m) M N + (-696 m + 378 n - 1920) M N 8 4 8 5 + (-180 m + 876 n + 1656) M N + (1188 n + 1500 - 426 m) M N 7 4 6 6 + (-960 m + 198 n - 4392) M N + (120 m + 270 n + 2094) M N 4 6 6 3 + (-60 m + 54 n - 66) M N + (-642 n + 2778 + 798 m) M N 8 6 4 5 + (-1164 m - 36 n - 4620) M N + (-66 n + 528 + 162 m) M N 8 3 10 3 + (-204 n + 504 + 174 m) M N + (24 m - 48 n + 48) M N 10 6 4 3 + (-768 - 144 n - 48 m) M N + (-54 n - 450 - 108 m) M N 6 4 10 4 + (2556 m - 2298 n + 6012) M N + (456 - 336 n + 240 m) M N 6 5 7 5 + (702 n - 4260 - 1392 m) M N + (4764 + 1332 m - 330 n) M N 3 4 5 6 + (-132 m + 78 n - 282) M N + (-288 m + 330 n + 210) M N 9 4 4 4 2 3 + (456 n - 432 m - 1188) M N , -24 M N (2 M - 3 M - 1) 2 2 2 2 2 (-3 N + 2 N - 1) (M N - 1 - M N - M N - M N)] 4 4 2 3 2 As you can see, the last entry, -24 M N (2 M - 3 M - 1) (-3 N + 2 N - 1) 2 2 2 2 (M N - 1 - M N - M N - M N), is a multiple of , 2 2 2 2 M N - 1 - M N - M N - M N The proof follows by backwards induction, after checking the boundary condit\ ions QED . ------------------------------------------------------ The whole thing took , 26.867, seconds of CPU time