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, 1], [0, 1], [1, 0], [1, 2]} 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 (n + 3 + m) (337 n + 79 m n - 695 - 161 m) (n - 1 - m) F(m, n) - ---------------------------------------------------------------- - (m + 6) %1 (n - m - 5) 3 2 2 2 (m + 4 + n) (79 n - 553 m n - 2387 n + 3002 m n + 316 m n + 6633 n 2 - 3453 m - 572 m - 4245) F(m + 1, n)/((m + 6) %1 (n - m - 5)) + (1830 2 3 4 2 + 8440 n - 5900 n - 256 n + 158 n + 5553 m + 1937 m n - 2289 m n 3 2 2 2 2 3 3 + 79 m n + 2937 m - 612 m n - 237 m n + 394 m - 158 m n) 2 F(m + 2, n)/((m + 6) %1 (n - m - 5)) + 2 (-45660 + 34374 n - 3477 n 3 4 2 3 2 - 1160 n + 79 n - 42363 m + 26992 m n - 1761 m n - 316 m n - 12635 m 2 2 2 3 3 + 7096 m n - 237 m n - 1216 m + 632 m n) F(m + 3, n)/((m + 6) %1 2 3 4 (n - m - 5)) - 2 (-77880 + 67519 n - 12491 n + 109 n + 79 n - 59329 m 2 3 2 2 2 2 + 45441 m n - 5935 m n + 79 m n - 14850 m + 9999 m n - 711 m n 3 3 - 1233 m + 711 m n) F(m + 4, n)/((m + 6) %1 (n - m - 5)) - (54690 2 3 4 2 - 59280 n + 19036 n - 2868 n + 158 n + 34573 m - 33386 m n + 7537 m n 3 2 2 2 2 3 3 - 632 m n + 6867 m - 5886 m n + 711 m n + 428 m - 316 m n) F(m + 5, n)/((m + 6) %1 (n - m - 5)) + F(m + 6, n) = 0 2 %1 := 250 m - 158 m n + 813 - 644 n + 79 n 2 (n + 1 - m) (n + 3 + m) (-161 n + 79 m n - 695 + 337 m) F(m, n) ----------------------------------------------------------------- - (m + 4 + n) (n + 6) %1 (-m + n + 5) 2 2 2 3 2 (-572 n + 316 m n - 3453 n + 3002 m n - 553 m n + 79 m - 2387 m + 6633 m - 4245) F(m, n + 1)/((n + 6) %1 (-m + n + 5)) - (-1830 - 8440 m 2 3 4 2 3 + 5900 m + 256 m - 158 m - 5553 n - 1937 m n + 2289 m n - 79 m n 2 2 2 2 3 3 - 2937 n + 612 m n + 237 m n - 394 n + 158 m n ) F(m, n + 2)/((n + 6) 2 3 4 %1 (-m + n + 5)) + 2 (-45660 + 34374 m - 3477 m - 1160 m + 79 m 2 3 2 2 - 42363 n + 26992 m n - 1761 m n - 316 m n - 12635 n + 7096 m n 2 2 3 3 - 237 m n - 1216 n + 632 m n ) F(m, n + 3)/((n + 6) %1 (-m + n + 5)) - 2 3 4 2 (-77880 + 67519 m - 12491 m + 109 m + 79 m - 59329 n + 45441 m n 2 3 2 2 2 2 3 - 5935 m n + 79 m n - 14850 n + 9999 m n - 711 m n - 1233 n 3 + 711 m n ) F(m, n + 4)/((n + 6) %1 (-m + n + 5)) + (-54690 + 59280 m 2 3 4 2 3 - 19036 m + 2868 m - 158 m - 34573 n + 33386 m n - 7537 m n + 632 m n 2 2 2 2 3 3 - 6867 n + 5886 m n - 711 m n - 428 n + 316 m n ) F(m, n + 5)/( (n + 6) %1 (-m + n + 5)) + F(m, n + 6) = 0 2 %1 := -250 n + 158 m n - 813 + 644 m - 79 m 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 (n + 3 + m) (337 n + 79 m n - 695 - 161 m) (n - 1 - m) 3 - -------------------------------------------------------- - (m + 4 + n) (79 n (m + 6) %1 (n - m - 5) 2 2 2 2 - 553 m n - 2387 n + 3002 m n + 316 m n + 6633 n - 3453 m - 572 m 2 3 - 4245) M/((m + 6) %1 (n - m - 5)) + (1830 + 8440 n - 5900 n - 256 n 4 2 3 2 2 + 158 n + 5553 m + 1937 m n - 2289 m n + 79 m n + 2937 m - 612 m n 2 2 3 3 2 - 237 m n + 394 m - 158 m n) M /((m + 6) %1 (n - m - 5)) + 2 (-45660 2 3 4 2 + 34374 n - 3477 n - 1160 n + 79 n - 42363 m + 26992 m n - 1761 m n 3 2 2 2 2 3 3 3 - 316 m n - 12635 m + 7096 m n - 237 m n - 1216 m + 632 m n) M /( 2 3 4 (m + 6) %1 (n - m - 5)) - 2 (-77880 + 67519 n - 12491 n + 109 n + 79 n 2 3 2 2 - 59329 m + 45441 m n - 5935 m n + 79 m n - 14850 m + 9999 m n 2 2 3 3 4 - 711 m n - 1233 m + 711 m n) M /((m + 6) %1 (n - m - 5)) - (54690 2 3 4 2 - 59280 n + 19036 n - 2868 n + 158 n + 34573 m - 33386 m n + 7537 m n 3 2 2 2 2 3 3 5 - 632 m n + 6867 m - 5886 m n + 711 m n + 428 m - 316 m n) M /( 6 (m + 6) %1 (n - m - 5)) + M 2 %1 := 250 m - 158 m n + 813 - 644 n + 79 n or equivalenty 3 5 3 3 4 3 3 3 4 -4170 - 428 m M + 2071 M n + 2466 m M - 2432 m M - 674 n + 155760 M 2 6 5 3 - 2678 m - 24390 M - 34573 m M + 474 M m n + 16980 M + 4802 n - 6526 m 4 2 2 2 2 3 2 4 2 - 79 M n + 8440 M n - 5900 M n - 256 M n + 158 M n + 2915 M n 2 4 2 5 3 5 5 2 + 29700 m M - 6867 m M - 22287 M n - 322 m + 59280 M n - 19036 M n 5 3 5 4 4 4 2 4 3 + 2868 M n - 158 M n - 135038 M n + 24982 M n - 218 M n 4 4 3 3 3 4 3 3 2 6 3 - 158 M n - 2320 M n + 158 M n + 68748 M n - 6954 M n + 474 M n 6 2 2 3 2 2 2 - 6234 M n + 79 M m n - 2289 M m n + 1937 M m n - 15188 M m n 2 2 3 2 2 3 2 - 3694 M m n + 1597 M m n - 316 M m n + 237 M m n + 14192 M m n 3 3 6 3 2 3 2 3 - 632 M m n + 24198 M n - 3522 M m n + 53984 M m n - 158 M m n 2 2 2 2 2 5 4 3 4 2 2 - 237 M m n - 612 M m n + 33386 M m n - 1422 M m n + 1422 M m n 4 2 4 3 4 2 4 - 19998 M m n - 158 M m n + 11870 M m n - 90882 M m n 3 3 3 2 2 5 3 2 3 5 + 1264 M m n - 474 M m n + 632 M m n - 25270 m M - 54690 M 5 2 5 3 5 2 2 5 2 6 3 - 7537 M m n + 316 M m n - 711 M m n + 5886 M m n + 158 M m n 6 2 2 6 2 6 3 6 2 6 - 237 M m n + 2632 M m n + 79 M m n - 2461 M m n + 14137 M m n 3 2 3 3 4 3 6 - 91320 M + 1830 M - 158 m n + 158 m n + 118658 m M - 250 m M 2 2 3 2 2 6 + 6 m n + 1306 m n + 394 m M + 42 n - 16443 m M + 3814 m n 3 3 2 2 2 2 + 572 m M - 84726 m M + 18057 m M + 5553 m M + 5741 m M + 2937 m M 2 6 - 3563 m M We know, by the obvious combinatorics, that F(m,n) is annihilated by 2 2 2 2 M N - N - M N - M N - M The sequence of successive commutators is 2 2 2 3 [(2022 n + 474 m n + 1938 n + 462 m n - 4170 - 3662 m - 1306 m - 158 m ) N + 3 2 2 2 (158 n - 6 n - 5278 n - 3086 m n - 474 m n + 9526 + 6322 m + 966 m ) M 3 2 3 2 + (17380 + 316 n + 3457 m - 11727 n + 13117 m + 316 m - 1422 m n 2 2 3 2 2 - 474 m n - 5739 n - 4616 m n) M N + (-316 m - 2594 m - 474 m n 2 2 3 2 - 1214 m n + 948 m n - 6238 m + 4514 n + 4986 n + 158 n - 4170) M N + 3 2 2 2 (-24370 - 474 n - 1716 m + 19198 n - 13198 m - 474 m n + 948 m n 2 2 3 2 - 1834 n + 8336 m n) M + (5916 - 316 n + 527 m + 682 n + 4067 m 2 2 2 2 3 + 237 m n - 474 m n + 2778 n - 2317 m n) M N + (24300 - 158 n 2 3 2 2 2 + 9196 m - 25358 n + 27826 m + 948 m - 4266 m n + 948 m n - 21136 n 2 2 3 2 2 - 388 m n) M N + (-8884 - 79 n - 1182 m - 1167 n - 7056 m + 474 m n 2 2 3 3 2 + 474 m n + 2526 n + 1698 m n) M + (-63316 - 1264 n - 11797 m 3 2 2 2 + 45061 n - 48921 m - 948 m - 474 m n + 2370 m n - 6713 n + 20996 m n) 3 3 2 3 2 M N + (-20670 - 1027 n - 4862 m + 43853 n - 20826 m - 316 m + 3792 m n 2 2 3 2 3 2 + 474 m n + 20156 n + 9102 m n) M N + (112428 + 632 n + 7296 m 2 2 2 4 - 69440 n + 57836 m + 948 m n - 3792 m n + 3996 n - 32176 m n) M + ( 3 2 3 2 87190 - 158 n + 18009 m - 26326 n + 68259 m + 1580 m + 1185 m n 2 2 4 3 2 - 1422 m n + 6474 n - 12685 m n) M N + (-99810 + 790 n - 28480 m 3 2 2 2 - 36934 n - 92202 m - 2844 m + 4266 m n - 3792 m n + 15594 n 4 2 3 2 - 23056 m n) M N + (-150824 + 158 n - 7398 m + 112302 n - 66798 m 2 2 2 5 3 2 - 2844 m n + 4266 m n - 13292 n + 44262 m n) M + (1264 n + 11088 n 2 3 2 - 102840 n + 22758 - 16087 m - 11885 m - 1580 m - 5214 m n - 46026 m n 2 5 3 2 + 1896 m n ) M N + (303780 + 1422 n + 62506 m + 42094 n + 240746 m 3 2 2 2 5 2 + 5372 m - 7584 m n + 4266 m n - 33896 n + 29982 m n) M N + (41868 3 2 2 2 2 - 632 n + 1284 m - 39588 n + 15018 m + 1422 m n - 948 m n + 8248 n 6 3 2 - 12720 m n) M + (-39830 + 948 n + 9917 m + 177592 n + 10391 m 3 2 2 2 6 + 1264 m - 5451 m n + 6162 m n - 28300 n + 67099 m n) M N + (-301860 3 2 3 2 2 - 948 n - 46116 m - 34352 n - 204930 m - 3476 m + 2370 m n - 948 m n 2 6 2 3 2 + 13472 n - 13188 m n) M N + (20256 - 79 n + 750 m - 16927 n + 7876 m 2 2 2 7 3 + 474 m n - 474 m n + 2698 n - 5738 m n) M + (-19106 - 632 n 2 3 2 2 2 - 4503 m - 30700 n - 18369 m - 316 m + 948 m n - 474 m n + 6470 n 7 3 2 3 - 8470 m n) M N + (56232 - 79 n + 5638 m + 1721 n + 31606 m + 316 m 2 2 2 7 2 3 + 948 m n - 474 m n + 2462 n - 1550 m n) M N + (-3654 - 158 n 2 3 2 2 2 - 1843 m - 17754 n - 5979 m - 158 m + 711 m n - 474 m n + 3974 n 8 - 5843 m n) M N 2 2 8 2 + 2 (n - m - 5) (79 n - 158 m n - 644 n - 3603 - 1566 m - 158 m ) M N , 2 2 8 2 (-86712 n + 6636 n - 429928 - 15168 m - 13272 m n - 160448 m) M N 10 4 - 8 (1342 + 237 m) (n - m - 5) M N 2 6 + (74196 - 48528 n + 14796 m + 2844 n - 8532 m n) M 2 2 6 4 + (23700 m n - 721444 - 49296 m + 159312 n + 12324 n - 395252 m) M N 2 2 10 3 + (-43804 m - 3792 m + 948 n + 12212 n - 125892 + 1896 m n) M N 2 2 5 + (-2370 n + 28214 n - 175696 - 81516 m - 9480 m + 5688 m n) M N 2 2 5 3 + (-27896 m - 5688 m - 17538 n - 17946 n - 73316 + 11376 m n) M N 2 2 8 4 + (2844 m n - 735870 - 22752 m + 20636 n - 1422 n - 261676 m) M N 2 + (-4044 n - 3960 - 948 m n - 936 m) N 2 2 4 + (948 n - 46732 n + 123332 + 52876 m + 5688 m - 9480 m n) M N 2 2 4 2 + (-30652 n - 6636 n + 64688 + 3792 m - 2844 m n + 34712 m) M N 2 2 2 + (10530 n - 948 n + 17150 + 474 m + 2844 m n + 6038 m) M N 2 2 2 + (2844 n + 10180 n - 33780 - 15724 m - 1896 m + 1896 m n) M N 2 2 2 4 + (-2844 m n - 21504 + 1896 m - 23944 n - 1896 n + 6668 m) M N 2 2 4 3 + (-57016 m - 5688 m + 13272 n + 46472 n - 54604 - 7584 m n) M N 2 + (-7288 + 3560 n - 1932 m + 948 m n) M 2 2 10 2 + (3264 n - 948 n + 46692 + 1422 m + 474 m n + 16296 m) M N 2 2 8 + (-1896 n + 17888 n + 46376 + 19908 m + 1896 m + 1896 m n) M N 2 3 + (-474 n + 5582 n - 9188 - 2108 m + 1896 m n) M N 2 2 3 3 + (6872 m + 3792 m + 1422 n - 94290 n - 89664 - 15168 m n) M N 2 8 + (-8626 + 6212 n - 1500 m - 474 n + 948 m n) M 2 2 + (-948 n - 924 n + 10252 + 6172 m + 948 m ) M N 2 4 + (8238 - 2172 n + 2364 m - 474 n - 948 m n) M 2 9 4 + (3792 m n + 81652 + 20064 n + 948 n + 15296 m) M N 2 2 7 4 + (-20856 m n + 1123570 + 53088 m - 140020 n - 3318 n + 501592 m) M N 2 2 9 2 + (4528 n + 948 n + 43292 + 474 m + 10478 m) M N 2 2 9 3 + (-47692 m - 2844 m - 3318 n - 6966 n - 178592) M N 2 2 5 4 + (7584 m n + 332352 + 15168 m + 56664 n - 7584 n + 123632 m) M N 2 2 6 3 + (385648 m + 43608 m - 16116 n - 26884 n + 832404 + 3792 m n) M N 2 2 8 3 + (483048 m + 43608 m - 4740 n + 540 n + 1344148) M N 2 2 3 2 + (43444 n + 14220 n - 124492 - 9480 m + 1896 m n - 72680 m) M N 2 2 6 2 + (-896 n + 10428 n - 939984 - 46452 m - 2844 m n - 417712 m) M N 2 2 5 2 + (-4630 n - 7584 n + 402546 + 25596 m + 2844 m n + 203676 m) M N 2 2 7 3 + (-706696 m - 72048 m + 22278 n + 24294 n - 1700152 - 7584 m n) M N 2 3 + (14914 - 9284 n + 3432 m + 474 n - 1896 m n) M 2 2 3 + (532 m + 948 m - 948 n - 20892 n - 19316 - 3792 m n) M N 2 5 + (-65132 + 35968 n - 14592 m - 948 n + 7584 m n) M 2 2 4 4 + (-29388 m n - 233030 + 7584 m - 210596 n - 7110 n + 13308 m) M N 2 7 + (-16302 + 13668 n - 2568 m - 1422 n + 1896 m n) M 2 2 7 + (10902 n - 146522 n - 43144 - 47252 m - 7584 m - 24648 m n) M N 2 2 9 + (-1422 n + 12634 n + 15960 + 8320 m + 948 m + 1896 m n) M N 2 2 3 4 + (17064 m n + 118290 - 7584 m + 128044 n + 8058 n - 23784 m) M N 2 2 2 2 + (-8096 n - 1896 n + 23132 + 3318 m + 474 m n + 20536 m) M N 2 2 2 3 + (9308 m - 1896 m + 948 n + 85492 n + 93304 + 17064 m n) M N 2 2 7 2 + (96584 n - 10428 n + 825864 + 36024 m + 18960 m n + 344328 m) M N 2 2 6 + (-3792 n + 102480 n + 59104 + 57020 m + 9480 m + 20856 m n) M N, 5 5 (14220 n - 87846 - 17064 m) M N + (-2364 + 948 n) M 5 3 10 + (55932 m - 1896 n + 259446) M N + (-2844 n - 13902 - 2844 m) M N 12 6 4 5 + (-3792 n + 3792 m + 18960) M N + (684942 + 71100 n + 73944 m) M N 12 3 5 2 + (-41544 + 948 n - 6162 m) M N + (5688 n - 80652 - 17064 m) M N 8 3 8 + (490116 m - 13272 n + 2654952) M N + (36972 n + 82254 + 22752 m) M N 11 6 11 2 + (92832 + 7584 m + 13272 n) M N + (-1422 n - 53154 - 8532 m) M N 7 4 3 + (-14796 + 8532 n) M + (-26070 m + 46452 n - 29340) M N 4 4 7 + (-192912 - 145044 n + 42660 m) M N + (-31284 n - 99750 - 28440 m) M N 6 3 12 4 + (13272 m - 24648 n + 16020) M N + (128736 - 8532 n + 19908 m) M N 11 3 4 2 + (13272 m - 5688 n + 66864) M N + (-11376 n + 174240 + 39816 m) M N 9 6 + (1081956 + 210456 m - 52140 n) M N 10 5 2 2 + (1800582 - 8532 n + 270180 m) M N + (-8532 n - 19536 - 2844 m) M N 2 5 4 + (-10680 - 2844 m) M N + (131988 + 182016 n - 62568 m) M N 9 5 3 + (-3154494 + 139356 n - 585864 m) M N + (948 m + 4044) N 2 4 6 6 + (-129660 - 2844 n - 25596 m) M N + (-747192 - 73944 m - 64464 n) M N 11 4 3 + (109230 + 15642 n + 5688 m) M N + (-2844 n + 26430 + 5688 m) M N 3 2 12 5 + (1422 n - 50310 - 14220 m) M N + (-100464 + 11376 n - 17064 m) M N 8 6 + (-744624 - 214248 m + 130824 n) M N 4 6 + (-337008 - 17064 m - 62568 n) M N 6 5 + (143682 + 145044 n - 73944 m) M N 3 5 + (-408306 - 48348 n - 51192 m) M N 9 4 2 + (3373980 - 42660 n + 580176 m) M N + (2808 + 2844 n) M N 8 5 + (2248314 - 207612 n + 511920 m) M N 6 4 4 + (-213588 + 8532 n - 51192 m) M N + (-2844 n + 3162) M N 8 4 + (-3023208 + 113760 n - 585864 m) M N 9 3 3 + (-337488 m - 18960 n - 2015616) M N + (1932 - 948 n) M 6 2 2 5 + (14220 n - 465744 - 102384 m) M N + (77520 + 11376 n + 8532 m) M N 3 3 8 2 + (948 m - 66360 n - 101730) M N + (-51192 n - 801792 - 153576 m) M N 10 6 9 2 + (-634200 - 92904 m - 7584 n) M N + (42660 n + 487332 + 85320 m) M N 10 2 6 + (-66816 - 8532 m) M N + (-8532 n + 136494 + 28440 m) M N 11 5 8 + (-177564 - 28440 n - 11376 m) M N + (2568 - 1896 n) M 3 4 7 6 + (150462 + 18486 n + 11376 m) M N + (450492 + 127032 m - 88164 n) M N 6 9 + (14592 - 7584 n) M + (-2844 n - 32706 - 5688 m) M N 3 6 4 + (52596 + 1896 m + 10428 n) M N + (-3432 + 1896 n) M 10 4 7 4 + (-1770120 - 264492 m) M N + (1400700 - 119448 n + 324216 m) M N 5 6 + (766188 + 47400 m + 124188 n) M N 7 5 + (-686538 + 19908 n - 142200 m) M N 5 5 + (-424218 - 105228 n + 17064 m) M N 7 3 3 + (-298620 m + 22752 n - 1447878) M N + (-9582 + 1896 n - 2844 m) M N 4 7 2 + (5688 m + 2844 n + 32760) M N + (-17064 n + 920760 + 182016 m) M N 10 3 2 3 + (84846 m + 15168 n + 586944) M N + (-3318 m + 13272 n + 14844) M N 9 2 2 + (1500 - 948 n) M , 1896 N M (2 M N - 2 N M - 1 - M ) 2 2 2 2 2 6 2 5 2 (2 M N - 4 M N + 2 N + N + 2 + 4 N M - 2 M - 3 M N) (6 M N - 7 M N 4 2 3 2 2 2 2 7 6 5 4 - 8 M N - 2 M N + 10 M N - 3 M N - 2 M N - 5 N M + 18 N M + N M 3 2 6 5 4 3 2 - 10 N M + 5 M N + 2 N M - N - M - 3 M + 6 M - 2 M - M + M) 2 2 2 2 (M N - N - M N - M N - M)] 2 2 As you can see, the last entry, 1896 N M (2 M N - 2 N M - 1 - M ) 2 2 2 2 2 6 2 5 2 (2 M N - 4 M N + 2 N + N + 2 + 4 N M - 2 M - 3 M N) (6 M N - 7 M N 4 2 3 2 2 2 2 7 6 5 4 - 8 M N - 2 M N + 10 M N - 3 M N - 2 M N - 5 N M + 18 N M + N M 3 2 6 5 4 3 2 - 10 N M + 5 M N + 2 N M - N - M - 3 M + 6 M - 2 M - M + M) 2 2 2 2 (M N - N - M N - M N - M), is a multiple of , 2 2 2 2 M N - N - M N - M N - M The proof follows by backwards induction, after checking the boundary condit\ ions QED . ------------------------------------------------------ The whole thing took , 39.684, seconds of CPU time