First Written: April 15, 2005: tested for Maple 8 and 9 Version of April 15, 2005: This is GuessHolo3, A Maple package accompanying Doron Zeilberger's article: The Holonomic Ansatz: I. Foundations It guesses recurrence equations for discrete variables of TWO variables The most current version is available on WWW at: http://www.math.rutgers.edu/~zeilberg . Please report all bugs to: zeilberg at math dot rutgers dot edu . For general help, and a list of the MAIN functions, type "ezra();". For specific help type "ezra(procedure_name);" For a list of the supporting functions type: ezra1(); Warning, the protected names norm and trace have been redefined and unprotected Couldn't do it with patience, 10, and Starting place, 15 Couldn't do it with patience, 10, and Starting place, 15 Couldn't do it with patience, 10, and Starting place, 15 Theorem: Let F(m,n,k) be the number of lattice paths from (0,0,0) to (m,n,k) in the positive quadrant of the three-dimensional cubic lattice where the Fundamental Steps are {[0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 1, 0], [1, 0, 1], [0, 1, 1]} Let M, N and K be the shift operators in the m, n and k directions, respecti\ vely (M f(m,n,k):=f(m+1,n,k), Nf(m,n,k):=f(m,n+1,k) , Kf(m,n,k):=f(m,n,k+1) .) Then F(m,n,k) satisfies the following pure recurrences (m + 1) (3 k + 13 + 4 m + 3 n) (k + 2 + m + n) F(m, n, k) -1/2 --------------------------------------------------------- - 1/2 (150 (m + 5) (m + 4) %1 2 3 2 2 2 3 + 133 n + 47 n + 6 n + 133 k + 81 k n + 15 k n + 47 k + 15 k n + 6 k 2 2 2 + 175 m + 100 m n + 17 m n + 100 m k + 30 m k n + 17 m k + 66 m 2 2 3 + 18 m n + 18 m k + 8 m ) F(m + 1, n, k)/((m + 5) (m + 4) %1) - 1/2 (274 2 3 2 2 2 + 267 n + 77 n + 6 n + 267 k + 220 k n + 36 k n + 77 k + 36 k n 3 2 2 2 + 6 k + 267 m + 170 m n + 23 m n + 170 m k + 70 m k n + 23 m k + 82 m 2 2 3 + 26 m n + 26 m k + 8 m ) F(m + 2, n, k)/((m + 5) (m + 4) %1) - 1/2 ( 3 2 2 2 2 12 n + 97 n + 229 n + 190 + 9 k n + 113 k n + 229 k + 9 k n + 97 k 3 2 2 + 12 k + 31 m n + 138 m n + 139 m + 26 m k n + 138 m k + 31 m k 2 2 2 + 20 m n + 24 m + 20 m k) F(m + 3, n, k)/((m + 5) (m + 4) %1) - 1/2 2 2 2 (-8 n + 6 n - 70 - 8 k + 12 k n + 6 k - 59 m - m n - m k - 12 m ) F(m + 4, n, k)/((m + 5) %1) + F(m + 5, n, k) = 0 %1 := 4 m + 9 + 3 n + 3 k (n + 1) (3 k + 13 + 4 n + 3 m) (k + 2 + m + n) F(m, n, k) -1/2 --------------------------------------------------------- - 1/2 (150 (n + 5) (n + 4) %1 2 3 2 2 2 3 + 133 m + 47 m + 6 m + 133 k + 81 m k + 15 m k + 47 k + 15 m k + 6 k 2 2 2 + 175 n + 100 m n + 17 m n + 100 k n + 30 m k n + 17 k n + 66 n 2 2 3 + 18 m n + 18 k n + 8 n ) F(m, n + 1, k)/((n + 5) (n + 4) %1) - 1/2 ( 3 2 2 2 2 267 m + 274 + 6 m + 77 m + 267 k + 220 m k + 36 m k + 77 k + 36 m k 3 2 2 2 + 6 k + 267 n + 170 m n + 23 m n + 170 k n + 70 m k n + 23 k n + 82 n 2 2 3 + 26 m n + 26 k n + 8 n ) F(m, n + 2, k)/((n + 5) (n + 4) %1) - 1/2 ( 3 2 2 2 2 12 m + 97 m + 229 m + 190 + 9 m k + 113 m k + 229 k + 9 m k + 97 k 3 2 2 + 12 k + 31 m n + 138 m n + 139 n + 26 m k n + 138 k n + 31 k n 2 2 2 + 20 m n + 24 n + 20 k n ) F(m, n + 3, k)/((n + 5) (n + 4) %1) - 1/2 2 2 2 (-70 - 8 m + 6 m - 8 k + 12 m k + 6 k - 59 n - m n - k n - 12 n ) F(m, n + 4, k)/((n + 5) %1) + F(m, n + 5, k) = 0 %1 := 4 n + 9 + 3 m + 3 k (k + 1) (4 k + 13 + 3 n + 3 m) (k + 2 + m + n) F(m, n, k) -1/2 --------------------------------------------------------- - 1/2 (133 n (k + 5) (k + 4) %1 3 2 2 2 2 3 + 150 + 6 n + 47 n + 133 m + 81 m n + 15 m n + 15 m n + 47 m + 6 m 2 2 2 + 175 k + 100 k n + 17 k n + 100 m k + 30 m k n + 17 m k + 66 k 2 2 3 + 18 k n + 18 m k + 8 k ) F(m, n, k + 1)/((k + 5) (k + 4) %1) - 1/2 (274 2 3 2 2 2 + 267 n + 77 n + 6 n + 267 m + 220 m n + 36 m n + 77 m + 36 m n 3 2 2 2 + 6 m + 170 k n + 267 k + 23 k n + 70 m k n + 170 m k + 23 m k + 82 k 2 2 3 + 26 k n + 26 m k + 8 k ) F(m, n, k + 2)/((k + 5) (k + 4) %1) - 1/2 ( 3 2 2 2 2 12 n + 97 n + 229 n + 190 + 9 m n + 113 m n + 229 m + 9 m n + 97 m 3 2 2 + 12 m + 31 k n + 138 k n + 139 k + 26 m k n + 138 m k + 31 m k 2 2 2 + 20 k n + 24 k + 20 m k ) F(m, n, k + 3)/((k + 5) (k + 4) %1) + 1/2 2 2 2 (70 + 8 n - 6 n + 8 m - 12 m n - 6 m + 59 k + k n + m k + 12 k ) F(m, n, k + 4)/((k + 5) %1) + F(m, n, k + 5) = 0 %1 := 4 k + 9 + 3 n + 3 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\ := (m + 1) (3 k + 13 + 4 m + 3 n) (k + 2 + m + n) 2 3 - ---------------------------------------------- - (150 + 133 n + 47 n + 6 n 2 (m + 5) (m + 4) %1 2 2 2 3 + 133 k + 81 k n + 15 k n + 47 k + 15 k n + 6 k + 175 m + 100 m n 2 2 2 2 2 + 17 m n + 100 m k + 30 m k n + 17 m k + 66 m + 18 m n + 18 m k 3 2 3 + 8 m ) M/(2 (m + 5) (m + 4) %1) - (274 + 267 n + 77 n + 6 n + 267 k 2 2 2 3 2 + 220 k n + 36 k n + 77 k + 36 k n + 6 k + 267 m + 170 m n + 23 m n 2 2 2 2 3 2 + 170 m k + 70 m k n + 23 m k + 82 m + 26 m n + 26 m k + 8 m ) M /(2 3 2 2 (m + 5) (m + 4) %1) - (12 n + 97 n + 229 n + 190 + 9 k n + 113 k n 2 2 3 2 + 229 k + 9 k n + 97 k + 12 k + 31 m n + 138 m n + 139 m + 26 m k n 2 2 2 2 3 + 138 m k + 31 m k + 20 m n + 24 m + 20 m k) M /(2 (m + 5) (m + 4) %1) 2 2 2 4 (-8 n + 6 n - 70 - 8 k + 12 k n + 6 k - 59 m - m n - m k - 12 m ) M - ---------------------------------------------------------------------- 2 (m + 5) %1 5 + M %1 := 4 m + 9 + 3 n + 3 k or equivalenty 3 5 2 5 5 3 4 2 4 4 -26 - 133 M n + 8 m M + 90 m M + 322 m M + 12 m M + 107 m M + 306 m M 2 3 3 3 2 2 2 2 3 - 24 m M - 139 m M - 8 m M - 82 m M - 267 m M - 8 m M - 6 k n 3 2 4 2 3 4 - 6 m k n - 190 M - 274 M + 280 M - 25 m - 4 m - 12 M m k n 3 2 2 2 - 26 M m k n - 70 M m k n - 30 M m k n - 15 M k n - 15 M k n 5 5 2 4 2 - 81 M k n - 19 k - 150 M - 19 n - 47 m + 54 M m k + 6 M m k + M m k 4 2 4 4 3 2 3 2 3 - 6 M m k - 48 M k n + 12 M m k - 20 M m k - 31 M m k - 138 M m k 3 2 3 3 2 2 2 2 2 - 9 M k n - 113 M k n - 9 M k n - 26 M m k - 23 M m k 2 2 2 2 2 2 2 - 170 M m k - 36 M k n - 36 M k n - 220 M k n - 18 M m k 2 2 2 2 2 - 17 M m k - 100 M m k - 3 n - 7 m n - 3 m n - 26 m n - 66 m M 5 3 2 5 4 2 + 360 M - 175 m M - 6 M k - 47 M k - 133 M k + 120 M k - 24 M k 4 3 3 3 2 3 2 3 2 2 2 + 32 M k - 12 M k - 97 M k - 229 M k - 6 M k - 77 M k - 267 M k 2 3 2 2 2 3 2 4 3 3 - 47 M n - 6 M n - 77 M n - 6 M n - 267 M n + 32 M n - 12 M n 3 3 2 5 4 2 5 2 5 - 229 M n - 97 M n + 120 M n - 24 M n + 6 M m n + 54 M m n 4 2 3 2 4 4 2 2 2 3 + M m n - 20 M m n + 12 M m n - 6 M m n - 26 M m n - 138 M m n 3 2 2 2 2 2 2 - 31 M m n - 100 M m n - 17 M m n - 18 M m n - 170 M m n - 23 M m n 2 2 2 - 3 m k - 7 m k - 26 m k - 3 k We know, by the obvious combinatorics, that F(m,n,k) is annihilated by K N M - M N - M K - N K - K - N - M The sequence of successive commutators is [K (m + 1) (7 m + 6 k + 22 + 6 n) + (m + 1) (14 K m + 7 m + 6 n + 22 + 12 k K + 12 K n + 6 k + 50 K) N + (76 2 2 2 + 21 k K + 157 k K + 6 k n + 12 m + 33 k + 320 K + 33 n + 62 m + 3 n 2 2 + 14 m n + 54 K m k + 50 K m n + 37 K m + 222 K m + 141 K n + 18 K n 2 2 + 36 K k n + 14 m k + 3 k ) M + (21 n + 157 n + 320 + 38 K m k + 38 K m n 2 2 2 + 54 K k n + 54 m n + 10 K m + 36 k n + 30 K n + 30 k K + 181 k K 2 2 + 181 K n + 110 K m + 141 k + 18 k + 50 m k + 222 m + 37 m + 279 K) M N 2 2 + (249 + 53 k K + 436 k K + 30 k n + 24 m + 118 k + 920 K + 118 n 2 2 + 156 m + 17 n + 36 m n + 116 K m k + 136 K m n + 68 K m + 502 K m 2 2 2 2 + 500 K n + 68 K n + 132 K k n + 36 m k + 17 k ) M + (53 n + 436 n 2 + 920 + 16 K m k + 16 K m n + 54 K k n + 116 m n - 8 K m + 132 k n 2 2 2 + 4 K n + 4 k K + 80 k K + 80 K n - 36 K m + 500 k + 68 k + 136 m k 2 2 2 2 + 502 m + 68 m - 40 K) M N + (357 + 77 k K + 644 k K + 70 k n + 24 m 2 + 196 k + 1264 K + 196 n + 188 m + 23 n + 52 m n + 160 K m k + 148 K m n 2 2 2 3 + 70 K m + 602 K m + 644 K n + 68 K n + 160 K k n + 52 m k + 23 k ) M 2 + (77 n + 644 n + 1264 - 80 K m k - 80 K m n - 178 K k n + 160 m n 2 2 2 - 36 K m + 160 k n - 32 K n - 32 k K - 442 k K - 442 K n - 384 K m 2 2 3 2 + 644 k + 68 k + 148 m k + 602 m + 70 m - 1050 K) M N + (163 + 67 k K 2 + 498 k K + 26 k n + 158 k + 682 K + 158 n + 48 m + 31 n + 40 m n 2 2 + 114 K m k + 78 K m n + 19 K m + 251 K m + 354 K n + 40 K n + 44 K k n 2 4 2 + 40 m k + 31 k ) M + (67 n + 498 n + 682 - 104 K m k - 104 K m n 2 2 2 - 62 K k n + 114 m n - 42 K m + 44 k n - 76 K n - 76 k K - 520 k K 2 2 4 - 520 K n - 492 K m + 354 k + 40 k + 78 m k + 251 m + 19 m - 1342 K) M 2 2 N + (-425 + 6 k K + 47 k K + 12 k n - 36 m - 13 k - 560 K - 13 n - 250 m 2 2 2 + 6 n - 2 m n + 10 K m k + 10 K m n - 43 K m - 312 K m + 47 K n + 6 K n 2 5 2 + 12 K k n - 2 m k + 6 k ) M + (6 n + 47 n - 560 - 22 K m k - 22 K m n 2 2 2 - 12 K k n + 10 m n + 26 K m + 12 k n - 6 K n - 6 k K - 107 k K 2 2 5 - 107 K n + 146 K m + 47 k + 6 k + 10 m k - 312 m - 43 m + 155 K) M N 6 - 6 (m + 5) (4 m + 5 K m + 14 + 2 n + 2 K n + 20 K + 2 k K + 2 k) M 6 + 6 (m + 5) (6 K m - 5 m - 2 n + 2 k K + 2 K n + 26 K - 2 k - 20) M N, 2 2 2 -6 K (m + 1) - 12 K (m + 1) (2 K + 1) N - 6 (2 K + 1) (m + 1) N - 2 K (113 K + 24 k K + 21 K n + 37 K m + 6 k + 36 + 14 m + 6 n) M + ( 2 2 2 -12 n - 72 - 156 K m - 132 K n - 144 k K - 108 k K - 108 K n - 196 K m 2 - 626 K - 12 k - 28 m - 570 K) M N + (-156 K m - 144 K n - 132 k K 2 2 2 - 24 K m - 102 K n - 102 k K - 626 K - 74 m - 42 k - 226 - 48 n 2 2 - 350 K ) M N + (-74 - 108 k K - 14 k - 518 K - 14 n - 24 m - 148 K m 2 2 2 2 2 - 100 K n - 980 K - 202 k K - 218 K n - 244 K m) M + (-108 n - 518 2 2 2 2 - 148 K m - 292 K n - 212 k K - 520 k K - 520 K n - 560 K m - 906 K 2 2 - 100 k - 148 m - 2312 K) M N + (-148 K m - 212 K n - 292 k K + 64 K m 2 2 2 2 2 + 90 K n + 90 k K - 906 K - 244 m - 218 k - 980 - 202 n + 450 K ) M N + (-180 - 232 k K - 36 k - 1140 K - 36 n - 48 m - 272 K m - 272 K n 2 2 2 2 3 2 - 1896 K - 376 k K - 428 K n - 412 K m) M + (-232 n - 1140 + 160 K m 2 2 2 + 216 K n + 80 k K - 848 k K - 848 K n - 808 K m + 836 K - 272 k 3 2 2 - 272 m - 3884 K) M N + (160 K m + 80 K n + 216 k K + 176 K m + 320 K n 2 2 3 2 + 320 k K + 836 K - 412 m - 428 k - 1896 - 376 n + 1336 K ) M N + (-212 2 - 320 k K - 52 k - 1344 K - 52 n - 48 m - 280 K m - 296 K n - 2118 K 2 2 2 4 2 - 448 k K - 352 K n - 414 K m) M + (-320 n - 1344 + 512 K m 2 2 2 + 640 K n + 592 k K - 568 k K - 568 K n - 588 K m + 3140 K - 296 k 4 2 2 - 280 m - 3012 K) M N + (512 K m + 592 K n + 640 k K - 24 K m - 108 K n 2 2 4 2 - 108 k K + 3140 K - 414 m - 352 k - 2118 - 448 n - 452 K ) M N + (-48 2 2 - 228 k K - 40 k - 540 K - 40 n - 76 K m - 156 K n - 1002 K - 260 k K 2 2 5 2 2 2 - 134 K n - 162 K m) M + (-228 n - 540 + 420 K m + 356 K n + 536 k K 2 5 - 132 k K - 132 K n - 84 K m + 2694 K - 156 k - 76 m - 522 K) M N + ( 2 2 2 420 K m + 536 K n + 356 k K - 248 K m - 294 K n - 294 k K + 2694 K 2 5 2 - 162 m - 134 k - 1002 - 260 n - 1758 K ) M N + (286 - 20 k K + 2 k 2 2 2 + 710 K + 2 n + 72 m + 172 K m - 20 K n + 352 K - 22 k K - 22 K n 2 6 2 2 2 + 88 K m) M + (-20 n + 710 - 84 K m + 68 K n + 68 k K + 72 K m 2 6 - 194 K - 20 k + 172 m + 360 K) M N + (-84 K m + 68 K n + 68 k K 2 2 2 2 - 16 K m - 46 K n - 46 k K - 194 K + 88 m - 22 k + 352 - 22 n - 230 K ) 6 2 7 M N + 12 (K + 1) (31 K + k K + K n + 6 K m + 19 + 4 m + k + n) M 2 2 2 2 7 + (24 n + 600 - 168 K m - 24 K n - 24 k K - 888 K + 24 k + 120 m) M N 7 2 + 12 (K - 1) (8 K m + K n + k K + 43 K - 31 - k - n - 6 m) M N , 6 M 2 (M + 1) (K N M - M N - M K - N K - K - N - M) 3 2 (10 K N M - 6 N K - 3 K - 7 M K - 3 N - 7 M N - 4 M) (2 N K M - 3 N K M 3 2 3 2 - 8 K N M + 5 N K - 2 K M + 5 K M + 2 M K + 3 K - 2 N M + 5 N M 3 2 + 2 M N + 3 N - 2 M + M + 1)] 2 As you can see, the last entry, 6 M (M + 1) (K N M - M N - M K - N K - K - N - M) 3 2 (10 K N M - 6 N K - 3 K - 7 M K - 3 N - 7 M N - 4 M) (2 N K M - 3 N K M 3 2 3 2 - 8 K N M + 5 N K - 2 K M + 5 K M + 2 M K + 3 K - 2 N M + 5 N M 3 2 + 2 M N + 3 N - 2 M + M + 1), is a multiple of , K N M - M N - M K - N K - K - N - M The proof follows by backwards induction, after checking the boundary condit\ ions QED . ------------------------------------------------------ The whole thing took , 581.671, seconds of CPU time