Version of July 25, 1996. This is ANDREWS_SYNDROME A Maple program accompanying the paper "A Cure to Andrews's Syndrome", by S. B. Ekhad, Herb Wilf and Doron Zeilberger, submitted The most current version of this program is available on WWW at: http://www.math.temple.edu/~zeilberg , where also the paper can be found. Please report all bugs to: zeilberg@math.temple.edu . All bugs or other comments used will be acknowledged in future versions. For general help, and a list of the available functions, type "ezra();". For specific help type "ezra(procedure_name)" Warning: new definition for norm Warning: new definition for trace Identity 4.9 of Geroge Andrews's paper Pfaff Method I Rigorous Proof of A Summation Identity Involving Auxiliary Parameters By Shalosh B. Ekhad (E-mail: ekhad@math.temple.edu) Let F( n , k ):= k rf(- 2 n, k) rf(x + n + 2, k) rf(x, k) rf(x - z + 1/2, k) rf(z + 1, k) 4 ------------------------------------------------------------------------- k! rf(x - n + 1, 2 k) rf(2 z + 2, k) rf(1 + 2 x - 2 z, k) Theorem: 2 n ----- \ ) F(n, k) = rf(1/2, n) rf(2 z - n - x, 2 n) x (x + 2 n + 1) (2 z + 1) / ----- k = 0 / (2 z - x + n) (2 z - x + n + 1) / (rf(x - n + 1, n) rf(1 + x - z, n) / rf(z + 1/2, n) (x + n) (x + n + 1) (2 z + 2 n + 1) (2 z - x) (2 z - x + 1)) Proof: I will first check it for the first 4 values of n The identity is true when n=, 0 The identity is true when n=, 1 The identity is true when n=, 2 The identity is true when n=, 3 We now know that the identity holds for, n = 0 .. 3 Let's divide by the right side, making it 1, and let's call the new summand also F(n,k). The identity is equivalent to Theorem': Let F( n , k ):= k rf(- 2 n, k) rf(x + n + 2, k) rf(x, k) rf(x - z + 1/2, k) rf(z + 1, k) 4 rf(x - n + 1, n) rf(1 + x - z, n) rf(z + 1/2, n) (x + n) (x + n + 1) / (2 z + 2 n + 1) (2 z - x) (2 z - x + 1) / (k! rf(x - n + 1, 2 k) / rf(2 z + 2, k) rf(1 + 2 x - 2 z, k) rf(1/2, n) rf(2 z - n - x, 2 n) x (x + 2 n + 1) (2 z + 1) (2 z - x + n) (2 z - x + n + 1)) 2 n ----- \ Then, ) F(n, k) = 1, . / ----- k = 0 But this is clearly equivalent to, (since the identity is true at n =0) , to the following 2 n ----- \ ) (F(n + 1, k) - F(n, k)) = 0, (*) / ----- k = 0 Hence it suffices to prove: 2 n ----- \ 2 3 2 3 4 3 2 ) - (- 24 k - 24 x - 40 x - 20 x - 44 x n k - 24 x n k - 24 n z k / ----- k = 0 2 3 4 4 3 2 2 3 2 2 2 - 44 z x n - 24 z x n - 4 z x n - 24 z x n + 4 z x n + 24 z x n 2 3 2 2 - 20 k x z - 170 k x n + 8 k z n + 16 z x - 22 z x - 18 x z + 20 z x 2 3 2 4 + 32 z x + 4 x z - 4 z x - 104 x n + 8 n z - 48 k x + 8 k z - 100 k n 2 2 2 2 2 2 2 4 - 128 x n - 164 x n + 16 n z + 30 n z + 4 k x z - 4 k x n 2 3 4 3 2 2 3 2 2 2 2 + 2 k x - 4 x + 44 n z x - 27 k n x + 20 k z x + 20 k z n x 2 2 3 2 2 3 2 2 + 20 k x z n + 24 k x z n - 20 k x z n + 4 k x z n - 24 k x z n 3 4 2 2 4 4 4 2 2 2 2 - 24 x k + 24 n z - 18 k n + 12 n z - 4 x n - 17 k x - 18 k x z 2 2 2 3 2 2 3 2 2 + 24 k z n - 47 k x n - 23 k x n - 12 k z n + 12 k z n 2 2 2 2 2 2 2 3 2 2 - 7 k x n - 4 z x n k - 20 z x n k - 24 x n k - 28 z x n k 2 2 3 2 2 2 2 2 2 - 131 x n k - 117 x n k + 124 n z x - 28 n z k + 8 k z 2 2 3 3 2 2 2 2 2 - 105 k n - 46 z x n - 42 z x n + 44 z x n + 36 k z n - 8 z x k 4 3 2 4 2 3 2 2 - 28 x n + 68 n z - 22 k n - 73 k n + 26 k x z n + 18 k x z n 2 2 3 3 3 2 2 3 - 26 k x z n - 44 x n + 34 n z - 20 x n - 62 k n - 40 x n 2 2 2 2 2 2 - 30 k x + 4 k z + 2 k x z - 131 k x n - 94 k x n - 14 k z n 2 2 2 2 2 2 2 3 + 18 k z n - 90 k x n - 112 z x n - 30 k x z n - 132 x n - 112 x n 2 2 3 2 2 2 2 2 + 60 n z - 95 k n - 12 k - 45 x k - 214 k x n + 2 z x n - 90 z x n 2 2 2 2 2 + 112 z x n + 16 k z n + 16 k z - 149 k n + 40 z x n + 8 k x z 2 3 2 3 4 2 4 - 4 k x z + 3 k x n - 3 x k + k x ) (- 2 n + k - 1)! (x + n + 1 + k)! (x + k - 1)! (x - z - 1/2 + k)! (z + k)! (2 z + 1)! k (2 x - 2 z)! 4 (-1/2)! (2 z - n - x - 1)! x! (x - z + n)! (z - 1/2 + n)! / (x + n + 1) (2 z + 2 n + 1) (- 2 z + x) (- 2 z + x - 1) / ( / (- 2 n - 2 + k) (- 2 n + k - 1) (- 2 z + n + x + 1) (x + 2 n + 3) (- 2 z + x - n - 2) (- 2 n - 1)! (x + n + 1)! (x - 1)! (x - z - 1/2)! z! k! (x - n + 2 k)! (2 z + 1 + k)! (2 x - 2 z + k)! (- 1/2 + n)! (2 z + n - x - 1)! (x - z)! (z - 1/2)! x (x + 2 n + 1) (2 z + 1) (- 2 z + x - n) (- 2 z + x - n - 1)) = 0, (*) When, x = 1/3 and When, z = 1/5 the operator ope(N,n) is 9 (10 n + 27) (10 n + 17) (3 n + 2) (3 n + 7) (15 n + 32) (15 n + 17) (n + 2) 3 2 (n + 1) (675 n + 5871 n + 17254 n + 17038) - (10 n + 27) (3 n + 4) 7 6 5 (15 n + 32) (n + 2) (5467500 n + 94028850 n + 686124675 n 4 3 2 + 2751004215 n + 6541699509 n + 9225182715 n + 7147523504 n + 2349220232) N + (3 n + 11) (30 n + 79) (2 n + 5) (3 n + 7) (3 n + 4) 3 2 2 (5 n + 16) (15 n + 61) (15 n + 44) (675 n + 3846 n + 7537 n + 4980) N When, x = -1/4 and When, z = 1/7 the operator ope(N,n) is 8 (4 n + 7) (8 n + 3) (28 n + 45) (28 n + 17) (14 n + 37) (14 n + 23) (n + 2) 3 2 (n + 1) (139552 n + 1071568 n + 2729982 n + 2304963) - (4 n + 3) 7 6 (28 n + 45) (14 n + 37) (n + 2) (7002161152 n + 107158474752 n 5 4 3 2 + 686701611008 n + 2386723442560 n + 4856763470688 n + 5787693294728 n + 3744354048042 n + 1016266101075) N + (4 n + 7) (4 n + 3) (28 n + 59) (28 n + 69) (7 n + 22) (2 n + 5) (28 n + 127) (8 n + 27) 3 2 2 (139552 n + 652912 n + 1005502 n + 506997) N Let F(n,k):= 2 3 2 3 4 3 2 - (- 24 k - 24 x - 40 x - 20 x - 44 x n k - 24 x n k - 24 n z k 2 3 4 4 3 2 2 3 2 2 2 - 44 z x n - 24 z x n - 4 z x n - 24 z x n + 4 z x n + 24 z x n 2 3 2 2 - 20 k x z - 170 k x n + 8 k z n + 16 z x - 22 z x - 18 x z + 20 z x 2 3 2 4 + 32 z x + 4 x z - 4 z x - 104 x n + 8 n z - 48 k x + 8 k z - 100 k n 2 2 2 2 2 2 2 4 - 128 x n - 164 x n + 16 n z + 30 n z + 4 k x z - 4 k x n 2 3 4 3 2 2 3 2 2 2 2 + 2 k x - 4 x + 44 n z x - 27 k n x + 20 k z x + 20 k z n x 2 2 3 2 2 3 2 2 + 20 k x z n + 24 k x z n - 20 k x z n + 4 k x z n - 24 k x z n 3 4 2 2 4 4 4 2 2 2 2 - 24 x k + 24 n z - 18 k n + 12 n z - 4 x n - 17 k x - 18 k x z 2 2 2 3 2 2 3 2 2 + 24 k z n - 47 k x n - 23 k x n - 12 k z n + 12 k z n 2 2 2 2 2 2 2 3 2 2 - 7 k x n - 4 z x n k - 20 z x n k - 24 x n k - 28 z x n k 2 2 3 2 2 2 2 2 2 - 131 x n k - 117 x n k + 124 n z x - 28 n z k + 8 k z 2 2 3 3 2 2 2 2 2 - 105 k n - 46 z x n - 42 z x n + 44 z x n + 36 k z n - 8 z x k 4 3 2 4 2 3 2 2 - 28 x n + 68 n z - 22 k n - 73 k n + 26 k x z n + 18 k x z n 2 2 3 3 3 2 2 3 - 26 k x z n - 44 x n + 34 n z - 20 x n - 62 k n - 40 x n 2 2 2 2 2 2 - 30 k x + 4 k z + 2 k x z - 131 k x n - 94 k x n - 14 k z n 2 2 2 2 2 2 2 3 + 18 k z n - 90 k x n - 112 z x n - 30 k x z n - 132 x n - 112 x n 2 2 3 2 2 2 2 2 + 60 n z - 95 k n - 12 k - 45 x k - 214 k x n + 2 z x n - 90 z x n 2 2 2 2 2 + 112 z x n + 16 k z n + 16 k z - 149 k n + 40 z x n + 8 k x z 2 3 2 3 4 2 4 - 4 k x z + 3 k x n - 3 x k + k x ) (- 2 n + k - 1)! (x + n + 1 + k)! (x + k - 1)! (x - z - 1/2 + k)! (z + k)! (2 z + 1)! k (2 x - 2 z)! 4 (-1/2)! (2 z - n - x - 1)! x! (x - z + n)! (z - 1/2 + n)! / (x + n + 1) (2 z + 2 n + 1) (- 2 z + x) (- 2 z + x - 1) / ( / (- 2 n - 2 + k) (- 2 n + k - 1) (- 2 z + n + x + 1) (x + 2 n + 3) (- 2 z + x - n - 2) (- 2 n - 1)! (x + n + 1)! (x - 1)! (x - z - 1/2)! z! k! (x - n + 2 k)! (2 z + 1 + k)! (2 x - 2 z + k)! (- 1/2 + n)! (2 z + n - x - 1)! (x - z)! (z - 1/2)! x (x + 2 n + 1) (2 z + 1) (- 2 z + x - n) (- 2 z + x - n - 1)) We will prove that its sum w.r.t. k is identically 0. We already know this for n =0.. 1 We claim that there exists a linear recurrence operator, 2 ope(N,n):=, b0 + b1 N + b2 N , , with coefficients that are polynomials of, x, z and a polynomial in, n, and the variables, n, x, z 2 3 POLY:=, a0 + a1 k + a2 k + a3 k such that G(n,k):= 2 (x + n + 2 + k) (x + k) (2 x - 2 z + 1 + 2 k) (z + k + 1) 2 3 / 2 3 (a0 + a1 k + a2 k + a3 k ) / ((- 24 k - 24 x - 40 x - 20 x / 2 3 4 3 2 2 3 4 4 - 44 x n k - 24 x n k - 24 n z k - 44 z x n - 24 z x n - 4 z x n 3 2 2 3 2 2 2 - 24 z x n + 4 z x n + 24 z x n - 20 k x z - 170 k x n + 8 k z n 2 3 2 2 2 3 2 4 + 16 z x - 22 z x - 18 x z + 20 z x + 32 z x + 4 x z - 4 z x 2 2 - 104 x n + 8 n z - 48 k x + 8 k z - 100 k n - 128 x n - 164 x n 2 2 2 2 2 4 2 3 4 3 2 + 16 n z + 30 n z + 4 k x z - 4 k x n + 2 k x - 4 x + 44 n z x 2 3 2 2 2 2 2 2 3 - 27 k n x + 20 k z x + 20 k z n x + 20 k x z n + 24 k x z n 2 2 3 2 2 3 4 2 2 4 - 20 k x z n + 4 k x z n - 24 k x z n - 24 x k + 24 n z - 18 k n 4 4 2 2 2 2 2 2 2 3 + 12 n z - 4 x n - 17 k x - 18 k x z + 24 k z n - 47 k x n 2 2 3 2 2 2 2 2 2 2 - 23 k x n - 12 k z n + 12 k z n - 7 k x n - 4 z x n k 2 2 3 2 2 2 2 3 - 20 z x n k - 24 x n k - 28 z x n k - 131 x n k - 117 x n k 2 2 2 2 2 2 2 2 3 3 + 124 n z x - 28 n z k + 8 k z - 105 k n - 46 z x n - 42 z x n 2 2 2 2 2 4 3 2 4 + 44 z x n + 36 k z n - 8 z x k - 28 x n + 68 n z - 22 k n 2 3 2 2 2 2 3 3 - 73 k n + 26 k x z n + 18 k x z n - 26 k x z n - 44 x n + 34 n z 3 2 2 3 2 2 2 2 - 20 x n - 62 k n - 40 x n - 30 k x + 4 k z + 2 k x z - 131 k x n 2 2 2 2 2 2 2 - 94 k x n - 14 k z n + 18 k z n - 90 k x n - 112 z x n 2 2 3 2 2 3 2 2 - 30 k x z n - 132 x n - 112 x n + 60 n z - 95 k n - 12 k - 45 x k 2 2 2 2 2 2 - 214 k x n + 2 z x n - 90 z x n + 112 z x n + 16 k z n + 16 k z 2 2 2 3 2 3 4 2 4 - 149 k n + 40 z x n + 8 k x z - 4 k x z + 3 k x n - 3 x k + k x ) (- 2 n - 5 + k) (- 2 z + n + 3 + x) (x + 2 n + 7) (- 2 z + x - n - 4) (- 2 n - 4 + k) (- 2 n - 3 + k) (- 2 z + n + 2 + x) (x + n + 1) (x + n + 2) (x + 2 n + 5) (- 2 z + x - n - 3)) satisfies ope(N,n)F(n,k)=G(n,k+1)-G(n,k). It would then follow that the sum, a(n), of F(n,k) w.r.t. to k is annihilated by ope(N,n), and all we would have to check is 2 that the coefficient of, N , in ope(N,n) does not have positive integer roots. This will become apparent when we print out the ope(N,n) for specific values of the parameters: x z . Any factor of the form (n-positive integer) in ope(N,n) would also show up in any specialization of the parameters. Indeed, the coefficients of both ope(N,n) and POLY, defined above are solutions of a certain set of homogenous equations in the set of variables {a2, a1, a3, a0, b1, b0, b2} To prove that ope(N,n) and POLY exist, we must prove that this system of homogeneous equations has a non-trivial solution. In terms of the list of variables [a2, a1, a3, a0, b1, b0, b2] we have to prove that the matrix of coeffs., let's call it M times the vector of variables [a2, a1, a3, a0, b1, b0, b2] has a non-trivial solution. Since the number of eqations equals the number of unknowns, this means that we have to show that its determinant vanishes. By looking at the coefficients of the entries, it is immediately seen that the determinant is a poly. whose degrees are at most, in x is 48 in z is 26 in n is 56 In order to prove the existence of ope(N,n) and POLY mentioned above with certainty, .1 we will check that the matrix is singular by pluging in enough special values for the parameters: and compute its determinant there, to make sure that it is always zero. Since a polynomial of degree k in a variable x is identically zero if it vanishes at k+1 distinct values, it is enough to check that our determinant vanishes, when x, is in the range [-24, 24] z, is in the range [-13, 13] n, is in the range [-28, 28] Since you are willing to settle for a semirigorous proof We will chop the above interval by, .1 We have just performed this task, hence The identity was proved with certainty, .1 This took 251.616 seconds of CPU time