Version of Oct. 17, 1995 This is EKHAD, One of the Maple packages accompanying the forthcoming book "A=B" (soon to be published by A.K. Peters, Ltd.) by Marko Petkovsek, Herb Wilf, and Doron Zeilberger. The most current version of EKHAD is always available by anon. ftp to ftp.math.temple.edu/pub/zeilberg/programs/EKHAD or on the www: http://www.math.temple.edu/~zeilberg For general help, and a list of the available functions, type "ezra();". For specific help type "ezra(procedure_name)" Warning, `N` is implicitly declared local Warning, `N` is implicitly declared local Warning, `n` is implicitly declared local Warning, `N` is implicitly declared local This is file outDone, proving Identity (Done) of the paper It was obtained by running file inDone Proof of the Refined Alternating Sign Matrix Conjecture by Doron Zeilberger, available as file refined.tex (or refined.ps) from htpp://www.math.temple.edu/~zeilberg The identity (Done) is trivial when n=0 Let's first prove it when n=1 The difference of the left and right sides of (Done) when n=1 is: 0 This completes the proof when n=0,1 Now let Shalosh find recurrences The summand of the right side of (Done) is (- r - n) r 2 (n - r) w binomial(n + r, n) binomial(2 n - r, n) (1 + w X) (1 - w X) n (w - 1/w) Using the program zeil we get the following operator, where w is arbitrary 2 2 2 2 2 - 3 (w - 1) (w + 1) (1 + w X) (- 1 + w X) (3 n + 4) (3 n + 2) + w (w - 1) 2 3 3 2 (w + 1) (w X + 2 w X - w + 2) (2 w X + w X + 1 - 2 w) (- w X + w X - 1) 4 3 2 2 (2 n + 3) (n + 1) N + w (1 + w X - w + w X) (n + 2) (n + 1) N The proof, using zeilpap(F,r,n) will be reproduced below Substituting w=exp(Pi*I/3), we get the operator 2 (X + 1) (X - X + 1) (2 n + 3) (n + 1) N 1 - ---------------------------------------- 2 2 (X + X + 1) (3 n + 4) (3 n + 2) 2 2 (- 1 + X) (n + 2) (n + 1) N + 1/9 --------------------------------- 2 2 (X + X + 1) (3 n + 4) (3 n + 2) The summand of the first sum on the left is / 3\(2 n + 1) |1 - X | (3 k) n |------| (k + n)! (k - 1/3 + n)! X (-1) (- n - 2/3)! (3 n + 1)! \ 1 - X/ ------------------------------------------------------------------------------ (n + 1) 3 k! (k - 1/3)! 3 (n!) (n + 1/3)! Using zeil(G1,k,n) we get the following operator annihilating the first sum on the left 2 (X + 1) (X - X + 1) (2 n + 3) (n + 1) N 1 - ---------------------------------------- 2 2 (X + X + 1) (3 n + 4) (3 n + 2) 2 2 (- 1 + X) (n + 2) (n + 1) N + 1/9 --------------------------------- 2 2 (X + X + 1) (3 n + 4) (3 n + 2) The verbose proof will follow soon The summand of the second sum on the left is / 3\(2 n + 1) |1 - X | (3 k + 1) n |------| (k + n)! (k + 1/3 + n)! X (-1) (- n - 2/3)! \ 1 - X/ / (n + 1) 3 (3 n + 1)! / (k! (k + 1/3)! 3 (n!) (n + 1/3)!) / Using zeil(G2,k,n) we get the following operator annihilating the second sum 2 (X + 1) (X - X + 1) (2 n + 3) (n + 1) N 1 - ---------------------------------------- 2 2 (X + X + 1) (3 n + 4) (3 n + 2) 2 2 (- 1 + X) (n + 2) (n + 1) N + 1/9 --------------------------------- 2 2 (X + X + 1) (3 n + 4) (3 n + 2) To sum up, the three operators are 2 (X + 1) (X - X + 1) (2 n + 3) (n + 1) N 1 - ---------------------------------------- 2 2 (X + X + 1) (3 n + 4) (3 n + 2) 2 2 (- 1 + X) (n + 2) (n + 1) N + 1/9 --------------------------------- 2 2 (X + X + 1) (3 n + 4) (3 n + 2) 2 (X + 1) (X - X + 1) (2 n + 3) (n + 1) N 1 - ---------------------------------------- 2 2 (X + X + 1) (3 n + 4) (3 n + 2) 2 2 (- 1 + X) (n + 2) (n + 1) N + 1/9 --------------------------------- 2 2 (X + X + 1) (3 n + 4) (3 n + 2) 2 (X + 1) (X - X + 1) (2 n + 3) (n + 1) N 1 - ---------------------------------------- 2 2 (X + X + 1) (3 n + 4) (3 n + 2) 2 2 (- 1 + X) (n + 2) (n + 1) N + 1/9 --------------------------------- 2 2 (X + X + 1) (3 n + 4) (3 n + 2) While the outputs of zeil is completely proved, here are the the verbose proofs A PROOF OF THE Right of (Done) RECURRENCE by Shalosh B. Ekhad, Temple University, ekhad@math.temple.edu I will give a short proof of the following result( Paper refined.tex Doron Z.'s collection ). Theorem:Let F(n,r) be given by (- r - n) r 2 (n - r) w binomial(n + r, n) binomial(2 n - r, n) (1 + w X) (1 - w X) n (w - 1/w) and let SUM(n) be the sum of F(n,r) with respect to r . SUM(n) satisfies the following linear recurrence equation 2 2 2 2 2 (- 3 (w - 1) (w + 1) (1 + w X) (- 1 + w X) (3 n + 4) (3 n + 2) + w (w - 1) 2 3 3 (w + 1) (w X + 2 w X - w + 2) (2 w X + w X + 1 - 2 w) 2 (- w X + w X - 1) (2 n + 3) (n + 1) N 4 3 2 2 + w (1 + w X - w + w X) (n + 2) (n + 1) N ) SUM(n) =0. PROOF: We cleverly construct G(n,r) := 8 3 6 2 8 3 3 4 2 10 3 - (- 72 + 36 w X - 204 n - 20 w X + 4 w X n + 24 n w - 12 w X 3 4 3 2 2 2 10 3 3 6 12 3 3 - 12 n w + 150 n w + 344 n w - 17 w X n - 20 w + 42 w X n 2 6 3 4 4 2 4 2 - 144 w X + 100 w X + 60 r - 116 w X + 6 n w X + 28 w + 29 n w X 2 2 3 6 3 3 4 3 3 4 6 2 4 8 2 - 96 w X n - 125 w X n + 96 w X n + 12 n w X + 22 n w X 8 3 2 6 3 3 + 126 w n X - 408 n w X + 302 n w X - 107 w X n r - 12 n w r X 6 3 3 10 3 3 3 3 3 5 2 3 + 10 w X r - 2 w X r - 134 n w + 67 n w - 64 r w X + 232 w X 10 2 3 3 4 2 3 2 2 3 - 126 w X n + 58 n w X + 163 n w X - 424 n w X + 67 w n 4 4 4 6 7 2 3 8 3 3 3 4 - 34 n w X - 19 n w X + 58 w X n - 8 w n X r - 200 n w X 3 6 3 6 2 3 8 2 6 3 3 - 89 n w X + 46 n w X - 4 r w + 118 n w X + 6 w n X r 10 3 3 9 2 3 2 4 2 4 - 2 w n X r + 67 w X n + 342 n w - 140 w X - 432 n w X 4 6 3 10 2 3 8 3 8 3 3 - 406 n w X - 4 w n r - 18 w X r + 18 w X r - 14 w X r 12 3 3 2 8 3 3 7 + 6 w X r + 98 w n + 124 w + 12 w n r X - 134 n w X 5 2 3 3 3 5 3 3 2 4 - 317 w X n + 250 w X n + 76 w X n - 192 w X n - 52 n w 4 2 3 2 3 3 4 - 72 n w - 12 r + 192 w X n + 620 w n X - 16 n + 118 n r - 7 r w n 2 3 2 3 3 4 - 21 r w - 458 r w n X + 90 r w X - 232 r w X + 236 n w X r - 32 w 2 3 2 2 5 2 7 2 - 24 r w X - 96 n + 120 r w X - 212 n + 124 n w - 260 w X + 88 w X 5 3 4 2 4 3 12 2 3 10 2 2 - 32 w X - 196 w n + 88 w X + 72 w X + 80 w n X - 240 w n X 8 2 8 2 3 6 2 3 8 12 3 + 240 w n X + 44 w n X - 300 w n X + 60 w X + 20 w X 8 10 2 12 3 10 2 3 2 + 198 w X n - 198 w X n + 66 w X n - 60 w X + 408 w X n 4 4 2 4 4 2 2 5 5 2 3 - 2 w r + w r - r w + 336 n w X - 16 w n X - 718 w n X - 56 w 7 2 6 2 6 8 3 4 9 2 4 12 3 4 + 212 w n X - 80 w n - 66 w n + w X r - w X r - w X r 12 3 3 10 2 3 4 2 2 2 5 4 + 4 w n X r - 12 w n X r + 212 w X n - 72 w X - 4 w r X 7 4 10 4 2 8 4 5 2 4 7 2 4 6 3 4 + 2 w r X + 3 w r X - 3 w r X - w X r + 2 w X r - w X r 10 3 4 6 3 2 3 6 2 3 2 5 2 + w X r - 42 w n + 600 n w X - 10 w X n - 248 w n + 72 w X n 3 2 2 3 2 2 5 2 4 4 4 3 + 144 w X + 424 n w X - 724 n w X - w X r + 2 r w X 4 2 4 8 2 4 6 2 4 6 4 8 2 6 + 2 w X r - 4 w X r - w X r + 5 w X r + 64 w X - 20 w X 6 8 2 5 7 9 2 2 2 - 94 w X n + 200 w X n + 98 w n - 56 w X + 28 w X - 204 w X n 8 3 10 3 4 3 6 3 5 4 6 4 + 74 w X n - 34 w X n + 204 w X n - 310 w X n - w r + w r 3 4 9 2 7 5 3 2 4 + 2 w r + 98 w n X - 196 w n X + 28 w + 16 n r + 76 n r + 60 w r 2 10 3 3 4 2 7 7 2 2 - 120 w r - 4 w X r + 12 n w r + 12 n w X r - 140 w n X r 2 2 2 10 3 2 7 6 2 2 + 76 w X n r + 4 w X n r + 14 w n X r + 67 w X n r 4 2 2 8 2 2 2 5 8 3 10 3 - 140 w X n r - 18 w X n r - 6 n w r - 107 w X n r - w X n r 4 3 6 3 5 7 9 2 - 118 w X n r + 229 w X n r - 7 w n r + 8 w X r - 4 w X r 6 2 5 2 2 3 2 2 5 2 + 99 w X n r + 128 w X n r - 152 n w X r + 298 n w X r 2 3 8 2 2 2 9 2 - 292 n w X r - 4 w X n r + 118 w X n r - 7 w n X r 4 3 2 9 2 2 10 2 12 3 - 76 w X n r - 6 w X n r + 9 w X n r - 3 w X n r 3 2 2 2 5 5 2 - 236 w X n r - 82 n w X r + 208 w n X r + 465 w n X r 10 2 2 8 2 8 2 3 6 2 3 + 15 w n X r - 15 w n X r - 69 w n X r + 146 w n X r 6 2 12 2 3 8 7 2 6 + 5 w n r - 5 w n X r - 9 w X n r - 222 w n X r + 3 w n r 2 2 6 3 3 2 3 2 8 2 + 60 w X r + 2 w n r + 12 w n r - 120 w X r + 8 w X r 6 4 2 5 3 3 4 - 64 w X r - 222 w X n r + 24 w X n r + 32 w X n r + 112 n w r 2 9 2 3 2 4 4 3 7 - 6 n w r - 2 w X n r + 149 n w X r + 241 n w X r + 4 n w X r 5 2 3 2 7 2 3 3 4 + 62 w X n r + 152 n w X r - 28 w X n r + 30 n w X r 3 6 3 6 2 2 4 3 2 3 8 2 - 6 n w X r + 14 n w X r + 66 n w r - 18 n w X r - 8 n w X r 3 3 3 2 3 5 2 7 2 5 - 60 w X n r - 32 w X n r + 236 w X r - 112 w X r + 104 w X r 3 4 2 4 3 2 2 3 6 3 3 + 14 w n r - 112 w X r - 60 w X r + 16 w X n r + 30 w X n r 4 3 3 8 3 2 10 2 3 - 16 w X n r - 6 w n X r - 125 n w X r + 6 w X n r 3 4 2 3 2 2 2 8 3 3 10 3 3 - 28 n w X r - 30 n w r - 147 n w r - 14 w X n r + 2 w X n r 12 3 3 6 3 3 3 3 5 3 - 2 w X n r + 116 w X r + 4 n w r - 2 n w r - 2 w n r 2 4 5 8 3 3 6 2 - 233 n w r + 128 w X r - 4 w r - 52 w X r + 8 w r + 44 w X r 2 6 3 2 2 2 4 2 2 - 52 n w r X + 110 w n X r - 4 n r - 38 w r - 28 n w X r 8 3 2 6 2 2 10 3 2 2 2 2 2 2 + 41 w X r - 57 w X r + 5 w X r + 13 n w r - 9 w X r 6 3 2 2 2 4 2 2 2 4 2 - 45 w X r + 45 n w r - 21 w X r - 27 w n r - 14 n w r 4 2 2 6 2 6 2 2 4 2 2 - 48 n w r - 14 n r + 13 w r + 44 w X n + 176 w X n 2 6 8 2 2 2 7 2 9 2 2 2 - 144 n w X + 232 w X n + 16 n w X r - 8 w X n r 6 3 2 9 2 2 7 2 6 2 2 2 - 55 w X n r - 27 w n X r + 54 w n X r - 21 w X n r 4 2 2 2 2 6 2 8 2 2 2 8 3 2 + 24 w X n r + 26 n w X r - 14 w X n r + 51 w X n r 10 3 2 5 2 2 2 2 4 3 2 4 3 2 2 + 7 w X n r - 21 w r - 14 w X n r + 14 w X n r + 4 w X n r 7 2 2 2 2 2 2 2 10 3 2 2 2 3 2 2 + 24 w n X r - 4 w X n r + 2 w X n r + 8 n w X r 2 5 2 2 6 2 8 2 2 6 2 2 - 24 n w X r + 89 w X n r - 48 w X n r - 71 w X n r 5 2 2 3 2 2 8 2 2 6 2 5 2 - 40 w X n r + 24 w X r - 36 w X r + 69 w X r - 27 w n r 7 2 9 2 2 2 5 2 2 3 2 5 2 2 + 42 w X r - 21 w X r - 8 n w r + 32 n w X r - 83 w n X r 7 2 2 4 2 2 3 2 2 12 3 2 + 82 w n X r + 82 w X n r + 16 w n r - 17 w X n r 3 2 2 2 2 2 5 2 3 2 6 2 2 + 28 w X n r - 4 n w X r - 136 w n X r + 42 w r + 5 w n r 4 3 2 7 2 2 8 2 10 2 2 + 212 w X n + 176 w n X - 51 w X n r + 51 w X n r 2 2 2 12 2 3 2 10 2 2 2 8 2 2 - 212 w X n - 5 w n X r + 15 w n X r - 15 w n X r 8 2 3 2 6 2 3 2 3 2 10 3 2 2 2 + 15 w n X r - 16 w n X r + 54 w n r - 36 w X n - 8 n w r 5 2 2 7 2 2 5 2 4 2 2 4 3 2 - 69 w X r + 66 w X r - 108 w X r + 66 w X r + 12 w X r 8 2 12 3 2 10 2 2 6 2 2 2 2 - 39 w X r - 13 w X r + 39 w X r + 17 w n r - 12 w X r 4 3 4 6 3 4 4 3 4 5 2 2 4 + 16 w X n - 19 w X n - 26 n w + 13 n w - 16 w X n 12 3 4 4 3 4 5 10 3 4 8 3 4 + 8 w X n + 38 n w X + 20 n w X - 3 w X n - 2 w X n 9 2 2 2 5 2 7 4 4 3 2 + 124 w X n + 124 n w - 248 n w X + 13 w n + 32 n w X 4 7 4 5 2 4 8 4 7 2 4 9 2 - 26 n w X - 51 n w X + 24 n w X + 6 n w X + 13 n w X 7 2 3 6 3 2 4 4 6 4 10 2 6 2 3 - 20 w X r - 6 w r - w X r - 8 n w - 24 n w X + 22 w X r 2 3 2 2 2 2 2 4 2 4 2 + 10 w X r - 13 n w X r - 8 n w X r - 7 n w X r - 25 n w X r 2 2 3 3 2 3 4 3 3 8 2 3 + 37 w r - 20 w X r - 4 n w r - 2 w X r + 10 w r + 16 w X r 6 3 5 3 7 3 2 3 4 3 4 3 - 26 w X r + 6 w n r - 20 w X r - 6 w r + 12 w r + 8 n w r 5 2 3 5 3 3 3 4 2 3 2 3 + 10 w X r + 40 w X r - 12 w n r - 20 w X r + 6 n w X r 3 4 2 3 6 2 3 6 3 4 + 6 w n r - 12 w X n r + 12 w X n r - 18 w X n r - 32 w X n 7 2 3 8 2 3 9 2 3 3 3 5 3 - 12 w n X r + 12 w X n r + 10 w X r - 20 w r + 24 w n X r 5 2 3 7 3 5 3 9 2 3 + 6 w n X r - 12 w n X r + 10 w r + 6 w n X r ) r (2 n - r + 1) 2 (- r - n) r (- 1 + w X) w binomial(n + r, n) binomial(2 n - r, n) (1 + w X) 2 (n - r) n (1 - w X) (w - 1/w) /((n - r + 1) (n - r + 2) (n + 2) (n + 1)) with the motive that 2 2 2 2 2 (- 3 (w - 1) (w + 1) (1 + w X) (- 1 + w X) (3 n + 4) (3 n + 2) + w (w - 1) 2 3 3 (w + 1) (w X + 2 w X - w + 2) (2 w X + w X + 1 - 2 w) 2 (- w X + w X - 1) (2 n + 3) (n + 1) N 4 3 2 2 + w (1 + w X - w + w X) (n + 2) (n + 1) N ) F(n, r) = G(n,1+r)-G(n,r) (check!) and the theorem follows upon summing with respect to r . A PROOF OF THE Left1 of (Done) RECURRENCE by Shalosh B. Ekhad, Temple University, ekhad@math.temple.edu I will give a short proof of the following result( Paper refined.tex Doron Z.'s collection ). Theorem:Let F(n,k) be given by / 3\(2 n + 1) |1 - X | (3 k) n |------| (k + n)! (k - 1/3 + n)! X (-1) (- n - 2/3)! (3 n + 1)! \ 1 - X/ ------------------------------------------------------------------------------ (n + 1) 3 k! (k - 1/3)! 3 (n!) (n + 1/3)! and let SUM(n) be the sum of F(n,k) with respect to k . SUM(n) satisfies the following linear recurrence equation 2 2 (- 9 (X + X + 1) (3 n + 4) (3 n + 2) 2 + 9 (X + 1) (X - X + 1) (2 n + 3) (n + 1) N 2 2 - (- 1 + X) (n + 2) (n + 1) N ) SUM(n) =0. PROOF: We cleverly construct G(n,k) := 3 2 3 2 4 - 9 (- 18 - 17 k - 57 X n - 31 n - 62 n X - 93 X n - 21 X n - 21 X n 3 5 7 6 2 - 36 X - 34 X + 18 X n k + 6 X n k + 12 X n k - 36 X n k - 24 n X k 2 6 6 7 4 6 2 7 4 2 - 54 X + 4 X + 10 X n + 5 X n - 7 X k + 6 X n + 5 X k + 3 X k 5 5 2 2 2 2 5 2 5 + 6 X + 15 X n - 24 n X - 9 X k - 51 X k + 9 X k + 15 X k 7 2 7 6 2 6 7 2 5 2 + 3 X k + 2 X + 6 X k + 10 X k + 3 X n - 12 n k - 34 X k + 9 X n 2 2 2 4 2 2 4 3 3 2 - 36 X n - 12 n - 6 X n - 6 X k - 14 X - 29 X k - 18 X k n - 3 k / 3\(2 n + 1) 3 2 |1 - X | (3 k) - 3 X k ) k (3 k - 1) |------| (k + n)! (k - 1/3 + n)! X \ 1 - X/ n (-1) (- n - 2/3)! (3 n + 1)! / (n + 1) 3 / ((n + 2) (n + 1) k! (k - 1/3)! 3 (n!) (n + 1/3)!) / with the motive that 2 2 (- 9 (X + X + 1) (3 n + 4) (3 n + 2) 2 + 9 (X + 1) (X - X + 1) (2 n + 3) (n + 1) N 2 2 - (- 1 + X) (n + 2) (n + 1) N ) F(n, k) = G(n,k+1)-G(n,k) (check!) and the theorem follows upon summing with respect to k . A PROOF OF THE Left2 of (Done) RECURRENCE by Shalosh B. Ekhad, Temple University, ekhad@math.temple.edu I will give a short proof of the following result( Paper refined.tex Doron Z.'s collection ). Theorem:Let F(n,k) be given by / 3\(2 n + 1) |1 - X | (3 k + 1) n |------| (k + n)! (k + 1/3 + n)! X (-1) (- n - 2/3)! \ 1 - X/ / (n + 1) 3 (3 n + 1)! / (k! (k + 1/3)! 3 (n!) (n + 1/3)!) / and let SUM(n) be the sum of F(n,k) with respect to k . SUM(n) satisfies the following linear recurrence equation 2 2 (- 9 (X + X + 1) (3 n + 4) (3 n + 2) 2 + 9 (X + 1) (X - X + 1) (2 n + 3) (n + 1) N 2 2 - (- 1 + X) (n + 2) (n + 1) N ) SUM(n) =0. PROOF: We cleverly construct G(n,k) := 4 2 4 3 2 2 - 9 (- 24 - 6 X n - 19 k - 21 X n - 63 X n - 12 n - 35 n - 24 n X 5 3 2 2 2 2 3 - 70 n X + 21 X n - 21 X n - 105 X n - 36 X n - 48 X - 44 X 6 2 7 2 5 6 + 12 X n k - 72 X + 6 X n k - 36 X n k + 18 X n k - 24 n X k + 8 X 7 6 6 2 7 2 5 2 5 6 + 7 X n + 14 X n + 6 X n + 3 X n + 9 X n + 12 X + 14 X k 5 2 4 2 4 7 2 2 2 6 2 + 9 X k + 3 X k - 5 X k + 4 X - 9 X k - 57 X k + 6 X k 5 7 7 2 2 4 3 + 21 X k + 7 X k + 3 X k - 6 X k - 12 n k - 38 X k - 16 X - 31 X k / 3\(2 n + 1) 3 2 3 2 |1 - X | - 18 X k n - 3 k - 3 X k ) k (3 k + 1) |------| (k + n)! \ 1 - X/ (3 k + 1) n (k + 1/3 + n)! X (-1) (- n - 2/3)! (3 n + 1)! / (n + 1) 3 / ((n + 2) (n + 1) k! (k + 1/3)! 3 (n!) (n + 1/3)!) / with the motive that 2 2 (- 9 (X + X + 1) (3 n + 4) (3 n + 2) 2 + 9 (X + 1) (X - X + 1) (2 n + 3) (n + 1) N 2 2 - (- 1 + X) (n + 2) (n + 1) N ) F(n, k) = G(n,k+1)-G(n,k) (check!) and the theorem follows upon summing with respect to k . The whole thing took, 380.066, seconds of CPU time