@@ -1,1190 +1,1190 @@ -REDUCE 3.6, 15-Jul-95, patched to 6 Mar 96 ... - - -% Tests of the ZEILBERG package. - -% Authors: Gregor Stoelting, Wolfram Koepf (koepf@zib-berlin.de) - -load zeilberg; - - -*** gamma already defined as operator - -*** pochhammer already defined as operator - -*** binomial already defined as operator - -*** hypergeom already defined as operator - -*** summ already defined as operator - -*** zb_f already defined as operator - -*** zb_sigma already defined as operator - -*** local_gamma already defined as operator - -*** local_prod already defined as operator - -*** hypergeometric already defined as operator - -*** zb_subst already defined as operator - -% on time; - -% 1) Successful summations by the Gosper algorithm -% R. W. Gosper, Jr.: -% Decision procedure for indefinite hypergeometric summation, -% Proc. Nat. Acad. Sci. USA 75 (1978), 40-42. - -gosper(k,k); - - - (k + 1)*k ------------ - 2 - -gosper(k^2,k); - - - (2*k + 1)*(k + 1)*k ---------------------- - 6 - -gosper(k^3,k); - - - 2 2 - (k + 1) *k -------------- - 4 - -gosper(k^4,k); - - - 2 - (3*k + 3*k - 1)*(2*k + 1)*(k + 1)*k --------------------------------------- - 30 - -gosper(k^5,k); - - - 2 2 2 - (2*k + 2*k - 1)*(k + 1) *k ------------------------------- - 12 - -% gosper(k^20,k); -gosper((6*k+3)/(4*k^4+8*k^3+8*k^2+4*k+3),k); - - - (k + 2)*k ----------------- - 2 - 2*k + 4*k + 3 - -% gosper(2^k*(k^3-3*k^2-3*k-1)/(k^3*(k+1)^3),k); -gosper(x*k,k); - - - (k + 1)*k*x -------------- - 2 - -gosper(k*x^k,k); - - - k - x *((x - 1)*k - 1)*x ----------------------- - 2 - (x - 1) - -gosper(k*factorial(k),k); - - -(k + 1)*factorial(k) - -gosper(1/(k^2-1),k); - - - 2 - 2*k - 1 -------------- - 2*(k + 1)*k - -gosper((1+2*k)/((1+k^2)*(k^2+2*k+2)),k); - - - (k + 2)*k ------------------- - 2 - 2*(k + 2*k + 2) - -gosper((k^2+4*k+1)*factorial(k),k); - - -(k + 4)*(k + 1)*factorial(k) - -gosper((4*k-3)*factorial(2*k-2)/factorial(k-1),k); - - - 2*(2*k - 1)*factorial(2*(k - 1)) ----------------------------------- - factorial(k - 1) - -gosper(gamma(k+n+2)*n/((k+n+1)*gamma(k+2)*gamma(n+1)),k); - - - gamma(n + 2 + k) ---------------------------- - gamma(k + 2)*gamma(n + 1) - -gosper((k+n)*factorial(k+n),k); - - -(n + 1 + k)*factorial(k + n) - -gosper((3*(1+2*k))/((1+k^2)*(2+2*k+k^2)),k); - - - 3*(k + 2)*k ------------------- - 2 - 2*(k + 2*k + 2) - -% gosper((-25+15*k+18*k^2-2*k^3-k^4)/ -% (-23+479*k+613*k^2+137*k^3+53*k^4+5*k^5+k^6),k); -% gosper(3^k*(2*k^4+4*k^3-7*k^2-k-4)/(k*(k+1)*(k^2+1)*((k+1)^2+1)),k); -gosper(3^k*(4*k^2-2*k-3)/((2*k+3)*(2*k+1)*(k+1)*k),k); - - - k - 3*3 -------------------- - (2*k + 3)*(k + 1) - -% gosper(2^k*(2*k^3+3*k^2-20*k-15)/ -% ((2*k+3)*(2*k+1)*(k+5)*(k+4)*(k+1)*k),k); -% gosper(-2^k*((k+11)^2*(k+1)^2-2*(k+10)^2*k^2)/ -% ((k+11)^2*(k+10)^2*(k+1)^2*k^2),k); -% gosper(-2^k*((k+6)^2*(k+1)^2-2*(k+5)^2*k^2)/ -% ((k+6)^2*(k+5)^2*(k+1)^2*k^2),k); -% gosper(2^k*(k^4-14*k^2-24*k-9)/(k^2*(k+1)^2*(k+2)^2*(k+3)^2),k); -% gosper(((k^2-k-n^2-n-2)*gamma(k+n+2)*gamma(n+1))/ -% (2*(-1)^k*2^k*(k+n+1)*gamma(-(k-n-1))*gamma(k+2)),k); -% gosper(1/(k+1)*binomial(2*k,k)/(n-k+1)*binomial(2*n-2*k,n-k),k); -gosper(3^k*(4*k^2+2*a*k-4*k-2-a)/((2*k+2+a)*(2*k+a)*(k+1)*k),k); - - - k - 3*3 -------------------------- - (2*(k + 1) + a)*(k + 1) - -gosper(2^k*(k^2-2*k-1)/(k^2*(k+1)^2),k); - - - k - 2*2 ----------- - 2 - (k + 1) - -gosper((3*k^2+3*k+1)/(k^3*(k+1)^3),k); - - - 2 - (k + 3*k + 3)*k ------------------- - 3 - (k + 1) - -gosper((6*k+3)/(4*k^4+8*k^3+8*k^2+4*k+3),k); - - - (k + 2)*k ----------------- - 2 - 2*k + 4*k + 3 - -gosper(-(k^2+3*k+3)/(k^4+2*k^3-3*k^2-4*k+2),k); - - - (2*k + 5)*k --------------- - 2 - k + 2*k - 1 - -gosper(k^2*4^k/((k+1)*(k+2)),k); - - - k - 4*4 *(k - 1) --------------- - 3*(k + 2) - -gosper((2*k-1)^3,k); - - - 2 2 -(2*k - 1)*k - -gosper(3*k^2+3*k+1,k); - - - 2 -(k + 3*k + 3)*k - -gosper((k^2+4*k+2)*2^k,k); - - - k 2 -2*2 *(k + 1) - -% gosper(2^k*(k^3-3*k^2-3*k-1)/(k^3*(k+1)^3),k); -gosper(k*n^k,k); - - - k - n *((n - 1)*k - 1)*n ----------------------- - 2 - (n - 1) - -% gosper(3^k*(2*k^3+k^2+3*k+6)/((k^2+2)*(k^2+2*k+3)),k); -% gosper(4*(1-k)*(k^2-2*k-1)/(k^2*(k+1)^2*(k-2)^2*(k-3)^2),k); -% gosper(2^k*(k^4-14*k^2-24*k-9)/(k^2*(k+1)^2*(k+2)^2*(k+3)^2),k); -gosper((1+k)/(1-k)+2/k,k); - - - 2 - - (k - 2) -------------- - k - -gosper(1/(k*(k+1)),k); - - - k -------- - k + 1 - -gosper(1/(k*(k+2)),k); - - - (3*k + 5)*k -------------------- - 4*(k + 2)*(k + 1) - -gosper(1/(k*(k+10)),k); - - - 9 8 7 6 5 4 -((7381*k + 380755*k + 8495520*k + 107353950*k + 844356513*k + 4272540195*k - - 3 2 - + 13854467330*k + 27627865100*k + 30558324456*k + 14171968800)*k)/(25200 - - *(k + 10)*(k + 9)*(k + 8)*(k + 7)*(k + 6)*(k + 5)*(k + 4)*(k + 3)*(k + 2) - - *(k + 1)) - -% gosper(1/(k*(k+30)),k); -gosper(1/(k*(k+1)*(k+2)),k); - - - (k + 3)*k -------------------- - 4*(k + 2)*(k + 1) - -gosper(1/(k*(k+1)*(k+2)*(k+3)*(k+4)*(k+5)*(k+6)*(k+7)*(k+8)*(k+9)* - (k+10)),k); - - - 8 7 6 5 4 3 2 -((k + 44*k + 836*k + 8954*k + 59279*k + 249986*k + 667084*k + 1071576*k - - + 966240)*(k + 11)*k)/(36288000*(k + 10)*(k + 9)*(k + 8)*(k + 7)*(k + 6) - - *(k + 5)*(k + 4)*(k + 3)*(k + 2)*(k + 1)) - -gosper(pochhammer(k-n,n),k); - - - pochhammer(k - n,n)*k ------------------------ - n + 1 - -gosper((a+k-1)*pochhammer(a,k),k); - - -(a + k)*pochhammer(a,k) - -gosper((a-k-1)/pochhammer(a-k,k),k); - - - - 1 ---------------------- - pochhammer(a - k,k) - -gosper(binomial(k,n),k); - - - (k + 1)*binomial(k,n) ------------------------ - n + 1 - -gosper(k*binomial(k,n),k); - - - (k*n + k + n)*(k + 1)*binomial(k,n) -------------------------------------- - (n + 2)*(n + 1) - -% gosper(k^10*binomial(k,n),k); -gosper(1/binomial(k,n),k); - - - n - 1 - k ------------------------ - (n - 1)*binomial(k,n) - -gosper(k/binomial(k,n),k); - - - (n - 1 - k)*k ------------------------ - (n - 2)*binomial(k,n) - -% gosper(k^10/binomial(k,n),k); -gosper(binomial(k-n,k),k); - - - (n - 1 - k)*binomial(k - n,k) -------------------------------- - n - 1 - -gosper((-1)^k*binomial(n,k),k); - - - k - - ( - 1) *(k - n)*binomial(n,k) ----------------------------------- - n - -gosper((-1)^k/binomial(n,k),k); - - - k - ( - 1) *(k + 1) ------------------------ - (n + 2)*binomial(n,k) - -gosper((-1)^(k+1)*(4*k+1)*factorial(2*k)/ -(factorial(k)*4^k*(2*k-1)*factorial(k+1)),k); - - - k - - ( - 1) *factorial(2*k) ----------------------------------- - k - 4 *factorial(k + 1)*factorial(k) - -% term:=3^k*(3*k^2+2*a*k-4*k-2-a)/((2*k+2+a)*(2*k+a)*(k+1)*k)$ -% term:=sub(k=k+3,term)-term$ -% gosper(term,k); -% clear(term); - -% 2) Examples for the Wilf-Zeilberger method: -% H. S. Wilf and D. Zeilberger: -% Rational functions certify combinatorial identities. -% J. Amer. Math. Soc. 3, 1990, 147-158. - -% Binomial theorem -summand:=binomial(n,k)/2^n$ - - -gosper(sub(n=n+1,summand)-summand,k); - - - (n + 1 - k)*(binomial(n + 1,k) - 2*binomial(n,k)) ---------------------------------------------------- - n - 2*2 *(n + 1 - 2*k) - - -% Vandermonde -summand:=binomial(n,k)^2/binomial(2*n,n)$ - - -gosper(sub(n=n+1,summand)-summand,k); - - - 2 2 -((binomial(n + 1,k) *binomial(2*n,n) - binomial(2*(n + 1),n + 1)*binomial(n,k) ) - - 2 - *(2*k - 3*n - 1)*(k - n - 1) )/( - - 2 - (2*(2*(n + 1) - k)*(2*n + 1)*k - (3*n + 1)*(n + 1) ) - - *binomial(2*(n + 1),n + 1)*binomial(2*n,n)) - - -% Gauss -% summand:=factorial(n+k)*factorial(b+k)*factorial(c-n-1)*factorial(c-b-1) -% /(factorial(n-1)*factorial(c-n-b-1)*factorial(k+1)*factorial(c+k)* -% factorial(b-1))$ -% gosper(sub(n=n+1,summand)-summand,k); - -% Kummer -% summand:=(-1)^(n+k)*factorial(2*n+c-1)*factorial(n)*factorial(n+c-1)/( -% factorial(2*n+c-1-k)*factorial(2*n-k)*factorial(c+k-1)*factorial(k))$ -% gosper(sub(n=n+1,summand)-summand,k); - -% Saalschuetz -% summand:=factorial(a+k-1)*factorial(b+k-1)*factorial(n)* -% factorial(n+c-a-b-k-1)*factorial(n+c-1)/(factorial(k)*factorial(n-k)* -% factorial(k+c-1)*factorial(n+c-a-1)*factorial(n+c-b-1))$ -% gosper(sub(n=n+1,summand)-summand,k); - -% Dixon -% summand:=(-1)^k*binomial(n+b,n+k)*binomial(n+c,c+k)*binomial(b+c,b+k)* -% factorial(n)*factorial(b)*factorial(c)/factorial(n+b+c)$ -% gosper(sub(n=n+1,summand)-summand,k); - -% 3) Results from Gosper's original work -% R. W. Gosper, Jr.: -% Decision procedure for indefinite hypergeometric summation, -% Proc. Nat. Acad. Sci. USA 75 (1978), 40-42. - -% ff(k)=product(a+b*j+c*j^2,j,1,k); -% gg(k)=product(e+b*j+c*j^2,j,1,k); - -operator ff,gg; - - - -let {ff(~k+~m) => ff(k+m-1)*(c*(k+m)^2+b*(k+m)+a) - when (fixp(m) and m>0), -ff(~k+~m) => ff(k+m+1)/(c*(k+m+1)^2+b*(k+m+1)+a) - when (fixp(m) and m<0)}; - - - -let {gg(~k+~m) => gg(k+m-1)*(c*(k+m)^2+b*(k+m)+e) - when (fixp(m) and m>0), -gg(~k+~m) => gg(k+m+1)/(c*(k+m+1)^2+b*(k+m+1)+e) - when (fixp(m) and m<0)}; - - - -gosper(ff(k-1)/gg(k),k); - - - ff(k) ---------------- - (a - e)*gg(k) - -% gosper(ff(k-1)/gg(k+1),k); -% gosper(ff(k-1)/gg(k+2),k); - -% ff(k)=product(a+b*j+c*j^2+d*j^3,j,1,k); -% gg(k)=product(e+b*j+c*j^2+d*j^3,j,1,k); - -let { -ff(~k+~m) => ff(k+m-1)*(d*(k+m)^3+c*(k+m)^2+b*(k+m)+a) - when (fixp(m) and m>0), -ff(~k+~m) => ff(k+m+1)/(d*(k+m+1)^3+c*(k+m+1)^2+b*(k+m+1)+a) -when (fixp(m) and m<0)}; - - - -let { -gg(~k+~m) => gg(k+m-1)*(d*(k+m)^3+c*(k+m)^2+b*(k+m)+e) - when (fixp(m) and m>0), -gg(~k+~m) => gg(k+m+1)/(d*(k+m+1)^3+c*(k+m+1)^2+b*(k+m+1)+e) -when (fixp(m) and m<0)}; - - - -gosper(ff(k-1)/gg(k),k); - - - ff(k) ---------------- - (a - e)*gg(k) - -gosper(ff(k-1)/gg(k+1),k); - - -***** Gosper algorithm: no closed form solution exists - -% Decision: no closed form solution exists - -% ff(k)=product(a+b*j+c*j^2+d*j^3+e*j^4,j,1,k); -% gg(k)=product(f+b*j+c*j^2+d*j^3+e*j^4,j,1,k); - -let { -ff(~k+~m) => ff(k+m-1)*(e*(k+m)^4+d*(k+m)^3+c*(k+m)^2+b*(k+m)+a) -when (fixp(m) and m>0), -ff(~k+~m) => ff(k+m+1)/(e*(k+m+1)^4+d*(k+m+1)^3+c*(k+m+1)^2+b*(k+m+1)+a) -when (fixp(m) and m<0)}; - - - -let { -gg(~k+~m) => gg(k+m-1)*(e*(k+m)^4+d*(k+m)^3+c*(k+m)^2+b*(k+m)+f) -when (fixp(m) and m>0), -gg(~k+~m) => - gg(k+m+1)/(e*(k+m+1)^4+d*(k+m+1)^3+c*(k+m+1)^2+b*(k+m+1)+f) - when (fixp(m) and m<0)}; - - - -gosper(ff(k-1)/gg(k),k); - - - ff(k) ---------------- - (a - f)*gg(k) - - -% ff=product(j^3+b*j^2+c*j+(2*c-4*b+8),j,1,k); -% gg=product(j^3+b*j^2+c*j,j,1,k) - -let { -ff(~k+~m) => ff(k+m-1)*((k+m)^3+c*(k+m)^2+b*(k+m)+(2*c-4*b+8)) -when (fixp(m) and m>0), -ff(~k+~m) => ff(k+m+1)/((k+m+1)^2+c*(k+m+1)^2+b*(k+m+1)+(2*c-4*b+8)) -when (fixp(m) and m<0)}; - - - -let { -gg(~k+~m) => gg(k+m-1)*((k+m)^3+c*(k+m)^2+b*(k+m)+1) - when (fixp(m) and m>0), -gg(~k+~m) => gg(k+m+1)/((k+m+1)^2+c*(k+m+1)^2+b*(k+m+1)+1) -when (fixp(m) and m<0)}; - - - -gosper(ff(k-1)/gg(k),k); - - - ff(k) ------------------------ - (2*c + 7 - 4*b)*gg(k) - - -clear(ff,gg); - - - -% 4) Examples for which gosper decides that no hypergeometric term -% antidifference exists - -gosper(factorial(k),k); - - -***** Gosper algorithm: no closed form solution exists - -gosper(factorial(2*k)/(factorial(k)*factorial(k+1)),k); - - -***** Gosper algorithm: no closed form solution exists - -% gosper(1/(factorial(k)*(k^4+k^2+1)),k); -gosper(binomial(A,k),k); - - -***** Gosper algorithm: no closed form solution exists - -gosper(1/k,k); - - -***** Gosper algorithm: no closed form solution exists - -gosper((1+k)/(1-k),k); - - -***** Gosper algorithm: no closed form solution exists - -% gosper(3^k*(3*k^2+2*a*k-4*k-2-a)/((2*k+2+a)*(2*k+a)*(k+1)*k),k); -gosper(factorial(k+n)*factorial(n)/ -((-1)^k*factorial(n-k)*factorial(k)*2^k),k); - - -***** Gosper algorithm: no closed form solution exists - -gosper(1/(k*(k+1/2)),k); - - -***** Gosper algorithm: no closed form solution exists - -gosper(pochhammer(a,k),k); - - -***** Gosper algorithm: no closed form solution exists - -gosper(binomial(n,k),k); - - -***** Gosper algorithm: no closed form solution exists - - -% 5) Finding recurrence equations for definite sums -% D. Zeilberger, -% A fast algorithm for proving terminating hypergeometric identities, -% Discrete Math. 80 (1990), 207-211. - -sumrecursion(binomial(n,k),k,n); - - -2*summ(n - 1) - summ(n) - -sumrecursion(k*binomial(n,k),k,n); - - -recursion valid for n>=2 - -(n - 1)*summ(n) - 2*summ(n - 1)*n - -% sumrecursion( -% (-1)^k*binomial(2*n,k)*binomial(2*k,k)*binomial(4*n-2*k,2*n-k),k,n); -sumrecursion(binomial(n,k)^2,k,n); - - -2*(2*n - 1)*summ(n - 1) - summ(n)*n - -sumrecursion(binomial(n,k)^2/binomial(2*n,n),k,n); - - -summ(n - 1) - summ(n) - -% sumrecursion((-1)^k*binomial(n,k)^2,k,n); -% Gauss -sumrecursion( -factorial(n+k)*factorial(b+k)*factorial(c-n-1)*factorial(c-b-1),k,n); - - - - ((n - 1 - c)*(c - n)*summ(n) + summ(n - 2)) - - + (n - 1 - b)*(n - 1 - c)*summ(n - 1) - -sumrecursion( -pochhammer(a,k)*pochhammer(b,k)/(factorial(k)*pochhammer(c,k)),k,a); - - -(b - c + a)*summ(a) - (a - c)*summ(a - 1) - -% Kummer -sumrecursion((-1)^(n+k)*factorial(2*n+c-1)*factorial(n)*factorial(n+c-1) -/(factorial(2*n+c-1-k)*factorial(2*n-k)*factorial(c+k-1)* - factorial(k)),k,n); - - -summ(n - 1) - summ(n) - -sumrecursion((-1)^k/( -factorial(2*n+c-1-k)*factorial(2*n-k)*factorial(c+k-1)* - factorial(k)),k,n); - - -(2*n - 1 + c)*(2*(n - 1) + c)*(n - 1 + c)*summ(n)*n + summ(n - 1) - -% Saalschuetz -% sumrecursion(factorial(a+k-1)*factorial(b+k-1)*factorial(n)* -% factorial(n+c-a-b-k-1)*factorial(n+c-1)/ -% (factorial(k)*factorial(n-k)*factorial(k+c-1)* -% factorial(n+c-a-1)*factorial(n+c-b-1)),k,n); -sumrecursion(factorial(a+k-1)*factorial(b+k-1)*factorial(n+c-a-b-k-1)/( -factorial(k)*factorial(n-k)*factorial(k+c-1)),k,n); - - - - (n - 1 + c - a)*(n - 1 + c - b)*summ(n - 1) + (n - 1 + c)*summ(n)*n - -% Dixon -% sumrecursion((-1)^k*binomial(n+b,n+k)*binomial(n+c,c+k)* -% binomial(b+c,b+k)* -% factorial(n)*factorial(b)*factorial(c)/factorial(n+b+c),k,n); -sumrecursion((-1)^k*binomial(n+b,n+k)*binomial(n+c,c+k)* - binomial(b+c,b+k),k,n); - - -(c + n + b)*summ(n - 1) - summ(n)*n - -sumrecursion((-1)^(k-n)*binomial(2*n,k)^3,k,n); - - - 2 -3*(3*n - 1)*(3*n - 2)*summ(n - 1) - summ(n)*n - -sumrecursion( -(-1)^(k-n)*binomial(2*n,k)^3/(binomial(3*n,n)*binomial(2*n,n)),k,n); - - -summ(n - 1) - summ(n) - -% Clausen -% summand:=factorial(a+k-1)*factorial(b+k-1)/ -% (factorial(k)*factorial(-1/2+a+b+k))*factorial(a+n-k-1)* -% factorial(b+n-k-1)/(factorial(n-k)*factorial(-1/2+a+b+n-k))$ -% sumrecursion(summand,k,n); -% Dougall -% summand:= -% pochhammer(d,k)*pochhammer(1+d/2,k)*pochhammer(d+b-a,k)* -% pochhammer(d+c-a,k)* -% pochhammer(1+a-b-c,k)*pochhammer(n+a,k)*pochhammer(-n,k)/ -% (factorial(k)* -% pochhammer(d/2,k)*pochhammer(1+a-b,k)*pochhammer(1+a-c,k)* -% pochhammer(b+c+d-a,k)*pochhammer(1+d-a-n,k)*pochhammer(1+d+n,k))$ -% sumrecursion(summand,k,n); -% Apery -sumrecursion(binomial(n,k)^2*binomial(n+k,k)^2,k,n); - - - 3 3 - - ((n - 1) *summ(n - 2) + summ(n)*n ) - - 2 - + (17*n - 17*n + 5)*(2*n - 1)*summ(n - 1) - -% sumrecursion(4*(-1)^k*binomial(m-1,k)*binomial(2*m-1,2*k)/ -% binomial(4*m-1,4*k)*(4*m^2+16*k^2-16*k*m+16*k-6*m+3)/ -% ((4*m-4*k-3)*(4*m-4*k-1)),k,m); -sumrecursion((-1)^k*binomial(n,k)*binomial(k,n),k,n); - - -summ(n - 1) + summ(n) - -sumrecursion((-1)^k*binomial(n,k)*binomial(2*k,n),k,n); - - -2*summ(n - 1) + summ(n) - -sumrecursion((-1)^k*binomial(n,k)*binomial(k,j)^2,k,n); - - - 2 -(n - 1 - 2*j)*summ(n - 1)*n - (j - n) *summ(n) - -sumrecursion(binomial(n,k)*binomial(a,k),k,n); - - -(a + n)*summ(n - 1) - summ(n)*n - -sumrecursion((3*k-2*n)*binomial(n,k)^2*binomial(2*k,k),k,n); - - -summ(n - 1) - summ(n) - -sumrecursion(binomial(n-k,k),k,n); - - -summ(n - 1) - summ(n) + summ(n - 2) - -sumrecursion(binomial(n,k)*binomial(n+k,k),k,n); - - -6*summ(n - 1)*n - 3*summ(n - 1) - summ(n)*n - (n - 1)*summ(n - 2) - -% sumrecursion(binomial(n+k,m+2*k)*binomial(2*k,k)*(-1)^k/(k+1),k,n); -sumrecursion((-1)^k*binomial(n-k,k)*binomial(n-2*k,m-k),k,n); - - -summ(n - 1) - summ(n) - -% sumrecursion((-1)^k*binomial(n-k,k)*binomial(n-2*k,m-k),k,m); -sumrecursion(binomial(n+k,2*k)*2^(n-k),k,n); - - -5*summ(n - 1) - summ(n) - 4*summ(n - 2) - -sumrecursion(binomial(n,k)*binomial(2*k,k)*(-1/4)^k,k,n); - - -(2*n - 1)*summ(n - 1) - 2*summ(n)*n - -% sumrecursion(binomial(n,i)*binomial(2*n,n-i),i,n); -sumrecursion((-1)^k*binomial(n,k)*binomial(2*k,k)*4^(n-k),k,n); - - -2*(2*n - 1)*summ(n - 1) - summ(n)*n - -sumrecursion((-1)^k*binomial(n,k)/binomial(k+a,k),k,n); - - -summ(n - 1) + summ(n) - -% sumrecursion((-1)^k*binomial(n,k)/binomial(k+a,k),k,a); -sumrecursion((-1)^(n-k)*binomial(2*n,k)^2,k,n); - - -2*(2*n - 1)*summ(n - 1) - summ(n)*n - -sumrecursion(factorial(a+k)*factorial(b+k)*factorial(n+c-a-b-k-1)/( -factorial(k+1)*factorial(n-k)*factorial(k+c)),k,a); - - - - (n + 1 + c - a)*(b - c + a)*summ(a) + (a - c)*(a - 1)*summ(a - 1) - -% sumrecursion(factorial(a+k)*factorial(b+k)*factorial(n+c-a-b-k-1)/( -% factorial(k+1)*factorial(n-k)*factorial(k+c)),k,b); -% sumrecursion(factorial(a+k)*factorial(b+k)*factorial(n+c-a-b-k-1)/( -% factorial(k+1)*factorial(n-k)*factorial(k+c)),k,c); -sumrecursion(binomial(2*n+1,2*p+2*k+1)*binomial(p+k,k),k,n); - - -(2*p + 1 - 2*n)*(n - p)*summ(n) - 2*(p + 1 - 2*n)*(2*n - p)*summ(n - 1) - -% sumrecursion(binomial(2*n+1,2*p+2*k+1)*binomial(p+k,k),k,p); -sumrecursion(binomial(r,m)*binomial(s,t-m),m,r); - - -(s - t + r)*summ(r) - (r + s)*summ(r - 1) - -% sumrecursion(binomial(r,m)*binomial(s,t-m),m,s); -% sumrecursion(binomial(r,m)*binomial(s,t-m),m,t); -sumrecursion(binomial(2*n+1,2*k)*binomial(m+k,2*n),k,n); - - -(2*n - 3 - 2*m)*(n - 1 - m)*summ(n - 1) - (2*n - 1)*summ(n)*n - -% sumrecursion(binomial(2*n+1,2*k)*binomial(m+k,2*n),k,m); -sumrecursion(binomial(n,k)*binomial(k,j)*x^j,k,n); - - -(j - n)*summ(n) + 2*summ(n - 1)*n - -% sumrecursion(binomial(n,k)*binomial(k,j)*x^j,k,j); -% sumrecursion(binomial(n,k)*binomial(k,j)*x^k,k,n); -sumrecursion(x*binomial(n+k,2*k)*((x^2-1)/4)^(n-k),k,n); - - - 2 2 2 - - ((x + 1) *(x - 1) *summ(n - 2) + 16*summ(n)) + 8*(x + 1)*summ(n - 1) - -sumrecursion(binomial(n+k-1,2*k-1)*(x-1)^(2*k)*x^(n-k)/k,k,n); - - - 2 2 - - ((n - 2)*summ(n - 2)*x + summ(n)*n) + (n - 1)*(x + 1)*summ(n - 1) - -sumrecursion( -1/(k+1)*binomial(2*k,k)/(n-k+1)*binomial(2*n-2*k,n-k),k,n); - - -summ(n - 1) + summ(n) - -sumrecursion(binomial(m,r)*binomial(n-r,n-r-q)*(t-1)^r,r,m); - - -(t + 1 + n*t - (t - 1)*q - (t + 1)*m)*summ(m - 1) - - - ((n + 1 - m)*summ(m) - (m - 1)*summ(m - 2)*t) - -% sumrecursion(binomial(m,r)*binomial(n-r,n-r-q)*(t-1)^r,r,n); -% sumrecursion(binomial(m,r)*binomial(n-r,n-r-q)*(t-1)^r,r,q); -% sumrecursion(binomial(m,r)*binomial(n-r,n-r-q)*(t-1)^r,r,r); -sumrecursion(pochhammer(-n/2,k)*pochhammer(-n/2+1/2,k)/ -(factorial(k)*pochhammer(b+1/2,k)),k,n); - - -(n - 1 + 2*b)*summ(n) - 2*(n - 1 + b)*summ(n - 1) - -% Watson -% sumrecursion(pochhammer(a,k)*pochhammer(b,k)*pochhammer(c,k)/( -% factorial(k)*pochhammer(1/2*(a+b+1),k)*pochhammer(2*c,k)),k,c); -% sumrecursion(pochhammer(-m,j)*pochhammer(m+2*k+2,j)*pochhammer(k+1/2,j)/ -% (factorial(j)*pochhammer(k+3/2,j)*pochhammer(2*k+1,j)),j,k); -sumrecursion((-1)^k*binomial(n,k)^3,k,n); - - - 2 -3*(3*n - 2)*(3*n - 4)*summ(n - 2) + summ(n)*n - -% sumrecursion(pochhammer(-n,k)*pochhammer(n+2*a,k)*pochhammer(a,k)/( -% factorial(k)*pochhammer(2*a/2,k)*pochhammer((2*a+1)/2,k))*(2/4)^k,k,n); -% sumrecursion(pochhammer(-n,k)*pochhammer(n+4*a,k)*pochhammer(a,k)/( -% factorial(k)*pochhammer(4*a/2,k)*pochhammer((4*a+1)/2,k))*(4/4)^k,k,n); -% sumrecursion(binomial(n+k+1,n-k)*pochhammer(-n+k,j)*pochhammer(k+1/2,j)* -% pochhammer(n+k+2,j)/(factorial(j)*pochhammer(k+3/2,j)* -% pochhammer(2*k+1,j)),j,n); -% sumrecursion(pochhammer(-m,j)*pochhammer(m+2*k+2,j)* -% pochhammer(k+1/2,j)/( -% factorial(j)*pochhammer(k+3/2,j)*pochhammer(2*k+1,j)),j,m); -% sumrecursion(binomial(n+k+1,n-k)*pochhammer(-n+k,j)* -% pochhammer(k+1/2,j)* -% pochhammer(n+k+2,j)/(factorial(j)*pochhammer(k+3/2,j)* -% pochhammer(2*k+1,j)), -% j,k); -% sumrecursion(pochhammer(a+b+c-n,j+l)*pochhammer(a+b-n/2,j+l)/ -% (factorial(j)*factorial(l)*pochhammer(a-n/2+1,j)* -% pochhammer(b-n/2+1,l)),j,a); -% sumrecursion(pochhammer(a+b+c-n,j+l)*pochhammer(a+b-n/2,j+l)/ -% (factorial(j)*factorial(l)*pochhammer(a-n/2+1,j)* -% pochhammer(b-n/2+1,l)),j,b); -sumrecursion(pochhammer(a+b+c-n,j+l)*pochhammer(a+b-n/2,j+l)/ -(factorial(j)*factorial(l)*pochhammer(a-n/2+1,j)* - pochhammer(b-n/2+1,l)),j,c); - - - - (n + 1 - l - c - b - a)*(n + 2 - 2*l - 2*c - 2*b)*summ(c - 1) - - + 2*(n + 1 - 2*l - c - 2*b - a)*(n + 1 - c - b - a)*summ(c) - -% sumrecursion( -% (-1)^(a+b+c)*gamma(a+b+c-d/2)*gamma(d/2-c)*gamma(a+c-d/2)* -% gamma(b+c-d/2)/ -% (gamma(a)*gamma(b)*gamma(d/2)*gamma(a+b+2*c-d)*(m^2)^(a+b+c-d))* -% pochhammer(a+b+c-d,k)*pochhammer(a+c-d/2,k)/ -% (pochhammer(a+b+2*c-d,k)*factorial(k)),k,a); -% sumrecursion( -% (-1)^(a+b+c)*gamma(a+b+c-d/2)*gamma(d/2-c)*gamma(a+c-d/2)* -% gamma(b+c-d/2)/ -% (gamma(a)*gamma(b)*gamma(d/2)*gamma(a+b+2*c-d)*(m^2)^(a+b+c-d))* -% pochhammer(a+b+c-d,k)*pochhammer(a+c-d/2,k)/ -% (pochhammer(a+b+2*c-d,k)*factorial(k)),k,b); -% sumrecursion( -% (-1)^(a+b+c)*gamma(a+b+c-d/2)*gamma(d/2-c)*gamma(a+c-d/2)* -% gamma(b+c-d/2)/ -% (gamma(a)*gamma(b)*gamma(d/2)*gamma(a+b+2*c-d)*(m^2)^(a+b+c-d))* -% pochhammer(a+b+c-d,k)*pochhammer(a+c-d/2,k)/ -% (pochhammer(a+b+2*c-d,k)*factorial(k)),k,c); -% sumrecursion(pochhammer(-n,k)*pochhammer(n+3*a,k)*pochhammer(a,k)/( -% factorial(k)*pochhammer(3*a/2,k)* -% pochhammer((3*a+1)/2,k))*(3/4)^k,k,n); -% summand:=k*(-1)^j*pochhammer(2*k+j+1,j)*pochhammer(2*k+2*j+2,n-k-j)/( -% factorial(k+j)*factorial(j)*factorial(n-k-j))*exp(-(j+k)*t)$ -% summand:=k*(-1)^j*pochhammer(2*k+j+1,j)*pochhammer(2*k+2*j+2,n-k-j)/( -% (k+j)*factorial(j)*factorial(n-k-j))*exp(-(j+k)*t)$ -% sumrecursion(summand,j,n); -clear(summand); - - - -% 6) Finding recurrence equations for hypergeometric functions -% Koornwinder, T. H.: -% On Zeilberger's algorithm and -% its q-analogue: a rigorous description. -% J. of Comput. and Appl. Math. 48, 1993, 91-111. - -% Gauss -hyperrecursion({a,b},{c},1,a); - - -(b - c + a)*summ(a) - (a - c)*summ(a - 1) - -% Dougall -% hyperrecursion({d,1+d/2,d+b-a,d+c-a,1+a-b-c,n+a,-n}, -% {d/2,1+a-b,1+a-c,b+c+d-a,1+d-a-n,1+d+n},1,n); -% Baxter -% hyperrecursion({-n,-n-1,-n-2},{2,3},-1,n); -% Krawtchouk polynomials -% krawtchoukterm := -% (-1)^n*p^n*binomial(NN,n)*hyperterm({-n,-x},{-NN},1/p,k)$ -% sumrecursion(krawtchoukterm,k,n); -% sumrecursion(krawtchoukterm,k,x); -% sumrecursion(krawtchoukterm,k,NN); -% clear(krawtchoukterm); -% hyperrecursion({-n,b,c+4},{b+1,c},1,n); -hyperrecursion({-n,b,c+1,d+1},{b+1,c,d},1,n); - - -recursion valid for n>=3 - -(b + n)*summ(n) - summ(n - 1)*n - - -% 7) Extended versions of Gosper's and Zeilberger's algorithms -% Koepf, W.: -% Algorithms for the indefinite and definite summation. -% Konrad-Zuse-Zentrum Berlin (ZIB), Preprint SC 94-33, 1994. - -% extended Gosper algorithm -extended_gosper(k*factorial(k/7),k,7); - - - k -(k + 7)*factorial(---) - 7 - -extended_gosper(k*factorial(k/2),k,2); - - - k -(k + 2)*factorial(---) - 2 - -extended_gosper(k*factorial(k/2),k); - - - k k - 1 -(k + 2)*factorial(---) + (k + 1)*factorial(-------) - 2 2 - -extended_gosper(binomial(k/2,n),k); - - - k k - 1 - (k + 2)*binomial(---,n) + (k + 1)*binomial(-------,n) - 2 2 -------------------------------------------------------- - 2*(n + 1) - -extended_gosper(binomial(n,k/2)-binomial(n,k/2-1),k); - - - k - 3 k - 1 -( - ((2*n + 3 - k)*(n + 1 - k)*(binomial(n,-------) - binomial(n,-------)) - 2 2 - - k - 2 k - + (n + 2 - k)*(2*(n + 1) - k)*(binomial(n,-------) - binomial(n,---))))/(2 - 2 2 - - *(n + 2 - k)*(n + 1 - k)) - - -% extended Zeilberger algorithm -% extended_sumrecursion(binomial(n,k)*binomial(k/2,n),k,n,1,2); -sumrecursion(binomial(n,k)*binomial(k/2,n),k,n); - - -recursion valid for n>=3 - -summ(n - 1) + 2*summ(n) - -extended_sumrecursion(binomial(n/2,k),k,n,2,1); - - -2*summ(n - 2) - summ(n) - -sumrecursion(binomial(n/2,k),k,n); - - -2*summ(n - 2) - summ(n) - -% sumrecursion(hyperterm({a,b,a+1/2-b,1+2*a/3,-n}, -% {2*a+1-2*b,2*b,2/3*a,1+a+n/2},4,k)/ -% (factorial(n)*2^(-n)/factorial(n/2))/ -% hyperterm({a+1,1},{a-b+1,b+1/2},1,n/2),k,n); - -% Watson -% sumrecursion(pochhammer(a,k)*pochhammer(b,k)*pochhammer(c,k)/( -% factorial(k)*pochhammer(1/2*(a+b+1),k)*pochhammer(2*c,k))/ -% (GAMMA(1/2)*GAMMA(1/2+c)*GAMMA(1/2+a/2+b/2)*GAMMA(1/2-a/2-b/2+c))* -% GAMMA(1/2+a/2)*GAMMA(1/2+b/2)*GAMMA(1/2-a/2+c)*GAMMA(1/2-b/2+c),k,a); -% hyperrecursion({a,b,c},{1/2*(a+b+1),2*c},1,a); -% hyperrecursion({a,b,c},{1/2*(a+b+1),2*c},1,b); - -% 8) Closed form representations of hypergeometric sums - -% Vandermonde -hypersum({-n,b},{c},1,n); - - - pochhammer( - b + c,n) ------------------------- - pochhammer(c,n) - -% Saalschuetz -hypersum({a,b,-n},{c,1+a+b-c-n},1,n); - - - pochhammer( - a + c,n)*pochhammer( - b + c,n) ------------------------------------------------ - pochhammer( - a - b + c,n)*pochhammer(c,n) - -% Kummer -hypersum({a,-n},{1+a+n},-1,n); - - - pochhammer(a + 1,n) ------------------------ - a + 2 - pochhammer(-------,n) - 2 - -% Dixon -hypersum({a,b,-n},{1+a-b,1+a+n},1,n); - - - a - 2*b + 2 - pochhammer(a + 1,n)*pochhammer(-------------,n) - 2 -------------------------------------------------- - a + 2 - pochhammer(a - b + 1,n)*pochhammer(-------,n) - 2 - -% Dougall -% hypersum({a,1+a/2,b,c,d,1+2*a-b-c-d+n,-n}, -% {a/2,1+a-b,1+a-c,1+a-d,1+a-(1+2*a-b-c-d+n),1+a+n},1,n); -% Clausen -% hypersum({a,b,1/2-a-b-n,-n},{1/2+a+b,1-a-n,1-b-n},1,n); - -hypersum({a,1+a/2,c,d,-n},{a/2,1+a-c,1+a-d,1+a+n},1,n); - - - pochhammer(a - c - d + 1,n)*pochhammer(a + 1,n) -------------------------------------------------- - pochhammer(a - c + 1,n)*pochhammer(a - d + 1,n) - -hypersum({a,1+a/2,d,-n},{a/2,1+a-d,1+a+n},-1,n); - - - pochhammer(a + 1,n) -------------------------- - pochhammer(a - d + 1,n) - - -% m-fold case: -hypersum({-n,-n,-n},{1,1},1,n); - - - n/2 2 n 1 n - ( - 27) *pochhammer(---,---)*pochhammer(---,---) - 3 2 3 2 -{----------------------------------------------------, - n 2 - factorial(---) - 2 - - 0} - -% hypersum({-n,n+3*a,a},{3*a/2,(3*a+1)/2},3/4,n); - -% 9) Hypergeometric representations - -sumtohyper(binomial(n,k)^3,k); - - -hypergeom({ - n, - n, - n},{1,1},-1) - -sumtohyper(binomial(n,k)/2^n-sub(n=n-1,binomial(n,k)/2^n),k); - - - - n + 2 - n - - hypergeom({----------, - n},{------},-1) - 2 2 ---------------------------------------------- - n - 2 - -sumtohyper(binomial(k+j-1,k-j)*2*(-1)^(j+1)*factorial(2*j-1)/ -factorial(j-1)/factorial(j+1)*x^j,j); - - -hypergeom({k + 1, - k + 1},{3},x)*k*x - -% term:=1/(n-1+k)*(1/2-1/2*x)^k/n*binomial(k-n-1,-n-1)*k* -% binomial(n-1+k,n-1); -% sumtohyper(sub(n=n+1,term)-term,k); - -end; -(TIME: zeilberg 141560 147540) +REDUCE 3.6, 15-Jul-95, patched to 6 Mar 96 ... + + +% Tests of the ZEILBERG package. + +% Authors: Gregor Stoelting, Wolfram Koepf (koepf@zib-berlin.de) + +load zeilberg; + + +*** gamma already defined as operator + +*** pochhammer already defined as operator + +*** binomial already defined as operator + +*** hypergeom already defined as operator + +*** summ already defined as operator + +*** zb_f already defined as operator + +*** zb_sigma already defined as operator + +*** local_gamma already defined as operator + +*** local_prod already defined as operator + +*** hypergeometric already defined as operator + +*** zb_subst already defined as operator + +% on time; + +% 1) Successful summations by the Gosper algorithm +% R. W. Gosper, Jr.: +% Decision procedure for indefinite hypergeometric summation, +% Proc. Nat. Acad. Sci. USA 75 (1978), 40-42. + +gosper(k,k); + + + (k + 1)*k +----------- + 2 + +gosper(k^2,k); + + + (2*k + 1)*(k + 1)*k +--------------------- + 6 + +gosper(k^3,k); + + + 2 2 + (k + 1) *k +------------- + 4 + +gosper(k^4,k); + + + 2 + (3*k + 3*k - 1)*(2*k + 1)*(k + 1)*k +-------------------------------------- + 30 + +gosper(k^5,k); + + + 2 2 2 + (2*k + 2*k - 1)*(k + 1) *k +------------------------------ + 12 + +% gosper(k^20,k); +gosper((6*k+3)/(4*k^4+8*k^3+8*k^2+4*k+3),k); + + + (k + 2)*k +---------------- + 2 + 2*k + 4*k + 3 + +% gosper(2^k*(k^3-3*k^2-3*k-1)/(k^3*(k+1)^3),k); +gosper(x*k,k); + + + (k + 1)*k*x +------------- + 2 + +gosper(k*x^k,k); + + + k + x *((x - 1)*k - 1)*x +---------------------- + 2 + (x - 1) + +gosper(k*factorial(k),k); + + +(k + 1)*factorial(k) + +gosper(1/(k^2-1),k); + + + 2 + 2*k - 1 +------------- + 2*(k + 1)*k + +gosper((1+2*k)/((1+k^2)*(k^2+2*k+2)),k); + + + (k + 2)*k +------------------ + 2 + 2*(k + 2*k + 2) + +gosper((k^2+4*k+1)*factorial(k),k); + + +(k + 4)*(k + 1)*factorial(k) + +gosper((4*k-3)*factorial(2*k-2)/factorial(k-1),k); + + + 2*(2*k - 1)*factorial(2*(k - 1)) +---------------------------------- + factorial(k - 1) + +gosper(gamma(k+n+2)*n/((k+n+1)*gamma(k+2)*gamma(n+1)),k); + + + gamma(n + 2 + k) +--------------------------- + gamma(k + 2)*gamma(n + 1) + +gosper((k+n)*factorial(k+n),k); + + +(n + 1 + k)*factorial(k + n) + +gosper((3*(1+2*k))/((1+k^2)*(2+2*k+k^2)),k); + + + 3*(k + 2)*k +------------------ + 2 + 2*(k + 2*k + 2) + +% gosper((-25+15*k+18*k^2-2*k^3-k^4)/ +% (-23+479*k+613*k^2+137*k^3+53*k^4+5*k^5+k^6),k); +% gosper(3^k*(2*k^4+4*k^3-7*k^2-k-4)/(k*(k+1)*(k^2+1)*((k+1)^2+1)),k); +gosper(3^k*(4*k^2-2*k-3)/((2*k+3)*(2*k+1)*(k+1)*k),k); + + + k + 3*3 +------------------- + (2*k + 3)*(k + 1) + +% gosper(2^k*(2*k^3+3*k^2-20*k-15)/ +% ((2*k+3)*(2*k+1)*(k+5)*(k+4)*(k+1)*k),k); +% gosper(-2^k*((k+11)^2*(k+1)^2-2*(k+10)^2*k^2)/ +% ((k+11)^2*(k+10)^2*(k+1)^2*k^2),k); +% gosper(-2^k*((k+6)^2*(k+1)^2-2*(k+5)^2*k^2)/ +% ((k+6)^2*(k+5)^2*(k+1)^2*k^2),k); +% gosper(2^k*(k^4-14*k^2-24*k-9)/(k^2*(k+1)^2*(k+2)^2*(k+3)^2),k); +% gosper(((k^2-k-n^2-n-2)*gamma(k+n+2)*gamma(n+1))/ +% (2*(-1)^k*2^k*(k+n+1)*gamma(-(k-n-1))*gamma(k+2)),k); +% gosper(1/(k+1)*binomial(2*k,k)/(n-k+1)*binomial(2*n-2*k,n-k),k); +gosper(3^k*(4*k^2+2*a*k-4*k-2-a)/((2*k+2+a)*(2*k+a)*(k+1)*k),k); + + + k + 3*3 +------------------------- + (2*(k + 1) + a)*(k + 1) + +gosper(2^k*(k^2-2*k-1)/(k^2*(k+1)^2),k); + + + k + 2*2 +---------- + 2 + (k + 1) + +gosper((3*k^2+3*k+1)/(k^3*(k+1)^3),k); + + + 2 + (k + 3*k + 3)*k +------------------ + 3 + (k + 1) + +gosper((6*k+3)/(4*k^4+8*k^3+8*k^2+4*k+3),k); + + + (k + 2)*k +---------------- + 2 + 2*k + 4*k + 3 + +gosper(-(k^2+3*k+3)/(k^4+2*k^3-3*k^2-4*k+2),k); + + + (2*k + 5)*k +-------------- + 2 + k + 2*k - 1 + +gosper(k^2*4^k/((k+1)*(k+2)),k); + + + k + 4*4 *(k - 1) +-------------- + 3*(k + 2) + +gosper((2*k-1)^3,k); + + + 2 2 +(2*k - 1)*k + +gosper(3*k^2+3*k+1,k); + + + 2 +(k + 3*k + 3)*k + +gosper((k^2+4*k+2)*2^k,k); + + + k 2 +2*2 *(k + 1) + +% gosper(2^k*(k^3-3*k^2-3*k-1)/(k^3*(k+1)^3),k); +gosper(k*n^k,k); + + + k + n *((n - 1)*k - 1)*n +---------------------- + 2 + (n - 1) + +% gosper(3^k*(2*k^3+k^2+3*k+6)/((k^2+2)*(k^2+2*k+3)),k); +% gosper(4*(1-k)*(k^2-2*k-1)/(k^2*(k+1)^2*(k-2)^2*(k-3)^2),k); +% gosper(2^k*(k^4-14*k^2-24*k-9)/(k^2*(k+1)^2*(k+2)^2*(k+3)^2),k); +gosper((1+k)/(1-k)+2/k,k); + + + 2 + - (k - 2) +------------- + k + +gosper(1/(k*(k+1)),k); + + + k +------- + k + 1 + +gosper(1/(k*(k+2)),k); + + + (3*k + 5)*k +------------------- + 4*(k + 2)*(k + 1) + +gosper(1/(k*(k+10)),k); + + + 9 8 7 6 5 4 +((7381*k + 380755*k + 8495520*k + 107353950*k + 844356513*k + 4272540195*k + + 3 2 + + 13854467330*k + 27627865100*k + 30558324456*k + 14171968800)*k)/(25200 + + *(k + 10)*(k + 9)*(k + 8)*(k + 7)*(k + 6)*(k + 5)*(k + 4)*(k + 3)*(k + 2) + + *(k + 1)) + +% gosper(1/(k*(k+30)),k); +gosper(1/(k*(k+1)*(k+2)),k); + + + (k + 3)*k +------------------- + 4*(k + 2)*(k + 1) + +gosper(1/(k*(k+1)*(k+2)*(k+3)*(k+4)*(k+5)*(k+6)*(k+7)*(k+8)*(k+9)* + (k+10)),k); + + + 8 7 6 5 4 3 2 +((k + 44*k + 836*k + 8954*k + 59279*k + 249986*k + 667084*k + 1071576*k + + + 966240)*(k + 11)*k)/(36288000*(k + 10)*(k + 9)*(k + 8)*(k + 7)*(k + 6) + + *(k + 5)*(k + 4)*(k + 3)*(k + 2)*(k + 1)) + +gosper(pochhammer(k-n,n),k); + + + pochhammer(k - n,n)*k +----------------------- + n + 1 + +gosper((a+k-1)*pochhammer(a,k),k); + + +(a + k)*pochhammer(a,k) + +gosper((a-k-1)/pochhammer(a-k,k),k); + + + - 1 +--------------------- + pochhammer(a - k,k) + +gosper(binomial(k,n),k); + + + (k + 1)*binomial(k,n) +----------------------- + n + 1 + +gosper(k*binomial(k,n),k); + + + (k*n + k + n)*(k + 1)*binomial(k,n) +------------------------------------- + (n + 2)*(n + 1) + +% gosper(k^10*binomial(k,n),k); +gosper(1/binomial(k,n),k); + + + n - 1 - k +----------------------- + (n - 1)*binomial(k,n) + +gosper(k/binomial(k,n),k); + + + (n - 1 - k)*k +----------------------- + (n - 2)*binomial(k,n) + +% gosper(k^10/binomial(k,n),k); +gosper(binomial(k-n,k),k); + + + (n - 1 - k)*binomial(k - n,k) +------------------------------- + n - 1 + +gosper((-1)^k*binomial(n,k),k); + + + k + - ( - 1) *(k - n)*binomial(n,k) +---------------------------------- + n + +gosper((-1)^k/binomial(n,k),k); + + + k + ( - 1) *(k + 1) +----------------------- + (n + 2)*binomial(n,k) + +gosper((-1)^(k+1)*(4*k+1)*factorial(2*k)/ +(factorial(k)*4^k*(2*k-1)*factorial(k+1)),k); + + + k + - ( - 1) *factorial(2*k) +---------------------------------- + k + 4 *factorial(k + 1)*factorial(k) + +% term:=3^k*(3*k^2+2*a*k-4*k-2-a)/((2*k+2+a)*(2*k+a)*(k+1)*k)$ +% term:=sub(k=k+3,term)-term$ +% gosper(term,k); +% clear(term); + +% 2) Examples for the Wilf-Zeilberger method: +% H. S. Wilf and D. Zeilberger: +% Rational functions certify combinatorial identities. +% J. Amer. Math. Soc. 3, 1990, 147-158. + +% Binomial theorem +summand:=binomial(n,k)/2^n$ + + +gosper(sub(n=n+1,summand)-summand,k); + + + (n + 1 - k)*(binomial(n + 1,k) - 2*binomial(n,k)) +--------------------------------------------------- + n + 2*2 *(n + 1 - 2*k) + + +% Vandermonde +summand:=binomial(n,k)^2/binomial(2*n,n)$ + + +gosper(sub(n=n+1,summand)-summand,k); + + + 2 2 +((binomial(n + 1,k) *binomial(2*n,n) - binomial(2*(n + 1),n + 1)*binomial(n,k) ) + + 2 + *(2*k - 3*n - 1)*(k - n - 1) )/( + + 2 + (2*(2*(n + 1) - k)*(2*n + 1)*k - (3*n + 1)*(n + 1) ) + + *binomial(2*(n + 1),n + 1)*binomial(2*n,n)) + + +% Gauss +% summand:=factorial(n+k)*factorial(b+k)*factorial(c-n-1)*factorial(c-b-1) +% /(factorial(n-1)*factorial(c-n-b-1)*factorial(k+1)*factorial(c+k)* +% factorial(b-1))$ +% gosper(sub(n=n+1,summand)-summand,k); + +% Kummer +% summand:=(-1)^(n+k)*factorial(2*n+c-1)*factorial(n)*factorial(n+c-1)/( +% factorial(2*n+c-1-k)*factorial(2*n-k)*factorial(c+k-1)*factorial(k))$ +% gosper(sub(n=n+1,summand)-summand,k); + +% Saalschuetz +% summand:=factorial(a+k-1)*factorial(b+k-1)*factorial(n)* +% factorial(n+c-a-b-k-1)*factorial(n+c-1)/(factorial(k)*factorial(n-k)* +% factorial(k+c-1)*factorial(n+c-a-1)*factorial(n+c-b-1))$ +% gosper(sub(n=n+1,summand)-summand,k); + +% Dixon +% summand:=(-1)^k*binomial(n+b,n+k)*binomial(n+c,c+k)*binomial(b+c,b+k)* +% factorial(n)*factorial(b)*factorial(c)/factorial(n+b+c)$ +% gosper(sub(n=n+1,summand)-summand,k); + +% 3) Results from Gosper's original work +% R. W. Gosper, Jr.: +% Decision procedure for indefinite hypergeometric summation, +% Proc. Nat. Acad. Sci. USA 75 (1978), 40-42. + +% ff(k)=product(a+b*j+c*j^2,j,1,k); +% gg(k)=product(e+b*j+c*j^2,j,1,k); + +operator ff,gg; + + + +let {ff(~k+~m) => ff(k+m-1)*(c*(k+m)^2+b*(k+m)+a) + when (fixp(m) and m>0), +ff(~k+~m) => ff(k+m+1)/(c*(k+m+1)^2+b*(k+m+1)+a) + when (fixp(m) and m<0)}; + + + +let {gg(~k+~m) => gg(k+m-1)*(c*(k+m)^2+b*(k+m)+e) + when (fixp(m) and m>0), +gg(~k+~m) => gg(k+m+1)/(c*(k+m+1)^2+b*(k+m+1)+e) + when (fixp(m) and m<0)}; + + + +gosper(ff(k-1)/gg(k),k); + + + ff(k) +--------------- + (a - e)*gg(k) + +% gosper(ff(k-1)/gg(k+1),k); +% gosper(ff(k-1)/gg(k+2),k); + +% ff(k)=product(a+b*j+c*j^2+d*j^3,j,1,k); +% gg(k)=product(e+b*j+c*j^2+d*j^3,j,1,k); + +let { +ff(~k+~m) => ff(k+m-1)*(d*(k+m)^3+c*(k+m)^2+b*(k+m)+a) + when (fixp(m) and m>0), +ff(~k+~m) => ff(k+m+1)/(d*(k+m+1)^3+c*(k+m+1)^2+b*(k+m+1)+a) +when (fixp(m) and m<0)}; + + + +let { +gg(~k+~m) => gg(k+m-1)*(d*(k+m)^3+c*(k+m)^2+b*(k+m)+e) + when (fixp(m) and m>0), +gg(~k+~m) => gg(k+m+1)/(d*(k+m+1)^3+c*(k+m+1)^2+b*(k+m+1)+e) +when (fixp(m) and m<0)}; + + + +gosper(ff(k-1)/gg(k),k); + + + ff(k) +--------------- + (a - e)*gg(k) + +gosper(ff(k-1)/gg(k+1),k); + + +***** Gosper algorithm: no closed form solution exists + +% Decision: no closed form solution exists + +% ff(k)=product(a+b*j+c*j^2+d*j^3+e*j^4,j,1,k); +% gg(k)=product(f+b*j+c*j^2+d*j^3+e*j^4,j,1,k); + +let { +ff(~k+~m) => ff(k+m-1)*(e*(k+m)^4+d*(k+m)^3+c*(k+m)^2+b*(k+m)+a) +when (fixp(m) and m>0), +ff(~k+~m) => ff(k+m+1)/(e*(k+m+1)^4+d*(k+m+1)^3+c*(k+m+1)^2+b*(k+m+1)+a) +when (fixp(m) and m<0)}; + + + +let { +gg(~k+~m) => gg(k+m-1)*(e*(k+m)^4+d*(k+m)^3+c*(k+m)^2+b*(k+m)+f) +when (fixp(m) and m>0), +gg(~k+~m) => + gg(k+m+1)/(e*(k+m+1)^4+d*(k+m+1)^3+c*(k+m+1)^2+b*(k+m+1)+f) + when (fixp(m) and m<0)}; + + + +gosper(ff(k-1)/gg(k),k); + + + ff(k) +--------------- + (a - f)*gg(k) + + +% ff=product(j^3+b*j^2+c*j+(2*c-4*b+8),j,1,k); +% gg=product(j^3+b*j^2+c*j,j,1,k) + +let { +ff(~k+~m) => ff(k+m-1)*((k+m)^3+c*(k+m)^2+b*(k+m)+(2*c-4*b+8)) +when (fixp(m) and m>0), +ff(~k+~m) => ff(k+m+1)/((k+m+1)^2+c*(k+m+1)^2+b*(k+m+1)+(2*c-4*b+8)) +when (fixp(m) and m<0)}; + + + +let { +gg(~k+~m) => gg(k+m-1)*((k+m)^3+c*(k+m)^2+b*(k+m)+1) + when (fixp(m) and m>0), +gg(~k+~m) => gg(k+m+1)/((k+m+1)^2+c*(k+m+1)^2+b*(k+m+1)+1) +when (fixp(m) and m<0)}; + + + +gosper(ff(k-1)/gg(k),k); + + + ff(k) +----------------------- + (2*c + 7 - 4*b)*gg(k) + + +clear(ff,gg); + + + +% 4) Examples for which gosper decides that no hypergeometric term +% antidifference exists + +gosper(factorial(k),k); + + +***** Gosper algorithm: no closed form solution exists + +gosper(factorial(2*k)/(factorial(k)*factorial(k+1)),k); + + +***** Gosper algorithm: no closed form solution exists + +% gosper(1/(factorial(k)*(k^4+k^2+1)),k); +gosper(binomial(A,k),k); + + +***** Gosper algorithm: no closed form solution exists + +gosper(1/k,k); + + +***** Gosper algorithm: no closed form solution exists + +gosper((1+k)/(1-k),k); + + +***** Gosper algorithm: no closed form solution exists + +% gosper(3^k*(3*k^2+2*a*k-4*k-2-a)/((2*k+2+a)*(2*k+a)*(k+1)*k),k); +gosper(factorial(k+n)*factorial(n)/ +((-1)^k*factorial(n-k)*factorial(k)*2^k),k); + + +***** Gosper algorithm: no closed form solution exists + +gosper(1/(k*(k+1/2)),k); + + +***** Gosper algorithm: no closed form solution exists + +gosper(pochhammer(a,k),k); + + +***** Gosper algorithm: no closed form solution exists + +gosper(binomial(n,k),k); + + +***** Gosper algorithm: no closed form solution exists + + +% 5) Finding recurrence equations for definite sums +% D. Zeilberger, +% A fast algorithm for proving terminating hypergeometric identities, +% Discrete Math. 80 (1990), 207-211. + +sumrecursion(binomial(n,k),k,n); + + +2*summ(n - 1) - summ(n) + +sumrecursion(k*binomial(n,k),k,n); + + +recursion valid for n>=2 + +(n - 1)*summ(n) - 2*summ(n - 1)*n + +% sumrecursion( +% (-1)^k*binomial(2*n,k)*binomial(2*k,k)*binomial(4*n-2*k,2*n-k),k,n); +sumrecursion(binomial(n,k)^2,k,n); + + +2*(2*n - 1)*summ(n - 1) - summ(n)*n + +sumrecursion(binomial(n,k)^2/binomial(2*n,n),k,n); + + +summ(n - 1) - summ(n) + +% sumrecursion((-1)^k*binomial(n,k)^2,k,n); +% Gauss +sumrecursion( +factorial(n+k)*factorial(b+k)*factorial(c-n-1)*factorial(c-b-1),k,n); + + + - ((n - 1 - c)*(c - n)*summ(n) + summ(n - 2)) + + + (n - 1 - b)*(n - 1 - c)*summ(n - 1) + +sumrecursion( +pochhammer(a,k)*pochhammer(b,k)/(factorial(k)*pochhammer(c,k)),k,a); + + +(b - c + a)*summ(a) - (a - c)*summ(a - 1) + +% Kummer +sumrecursion((-1)^(n+k)*factorial(2*n+c-1)*factorial(n)*factorial(n+c-1) +/(factorial(2*n+c-1-k)*factorial(2*n-k)*factorial(c+k-1)* + factorial(k)),k,n); + + +summ(n - 1) - summ(n) + +sumrecursion((-1)^k/( +factorial(2*n+c-1-k)*factorial(2*n-k)*factorial(c+k-1)* + factorial(k)),k,n); + + +(2*n - 1 + c)*(2*(n - 1) + c)*(n - 1 + c)*summ(n)*n + summ(n - 1) + +% Saalschuetz +% sumrecursion(factorial(a+k-1)*factorial(b+k-1)*factorial(n)* +% factorial(n+c-a-b-k-1)*factorial(n+c-1)/ +% (factorial(k)*factorial(n-k)*factorial(k+c-1)* +% factorial(n+c-a-1)*factorial(n+c-b-1)),k,n); +sumrecursion(factorial(a+k-1)*factorial(b+k-1)*factorial(n+c-a-b-k-1)/( +factorial(k)*factorial(n-k)*factorial(k+c-1)),k,n); + + + - (n - 1 + c - a)*(n - 1 + c - b)*summ(n - 1) + (n - 1 + c)*summ(n)*n + +% Dixon +% sumrecursion((-1)^k*binomial(n+b,n+k)*binomial(n+c,c+k)* +% binomial(b+c,b+k)* +% factorial(n)*factorial(b)*factorial(c)/factorial(n+b+c),k,n); +sumrecursion((-1)^k*binomial(n+b,n+k)*binomial(n+c,c+k)* + binomial(b+c,b+k),k,n); + + +(c + n + b)*summ(n - 1) - summ(n)*n + +sumrecursion((-1)^(k-n)*binomial(2*n,k)^3,k,n); + + + 2 +3*(3*n - 1)*(3*n - 2)*summ(n - 1) - summ(n)*n + +sumrecursion( +(-1)^(k-n)*binomial(2*n,k)^3/(binomial(3*n,n)*binomial(2*n,n)),k,n); + + +summ(n - 1) - summ(n) + +% Clausen +% summand:=factorial(a+k-1)*factorial(b+k-1)/ +% (factorial(k)*factorial(-1/2+a+b+k))*factorial(a+n-k-1)* +% factorial(b+n-k-1)/(factorial(n-k)*factorial(-1/2+a+b+n-k))$ +% sumrecursion(summand,k,n); +% Dougall +% summand:= +% pochhammer(d,k)*pochhammer(1+d/2,k)*pochhammer(d+b-a,k)* +% pochhammer(d+c-a,k)* +% pochhammer(1+a-b-c,k)*pochhammer(n+a,k)*pochhammer(-n,k)/ +% (factorial(k)* +% pochhammer(d/2,k)*pochhammer(1+a-b,k)*pochhammer(1+a-c,k)* +% pochhammer(b+c+d-a,k)*pochhammer(1+d-a-n,k)*pochhammer(1+d+n,k))$ +% sumrecursion(summand,k,n); +% Apery +sumrecursion(binomial(n,k)^2*binomial(n+k,k)^2,k,n); + + + 3 3 + - ((n - 1) *summ(n - 2) + summ(n)*n ) + + 2 + + (17*n - 17*n + 5)*(2*n - 1)*summ(n - 1) + +% sumrecursion(4*(-1)^k*binomial(m-1,k)*binomial(2*m-1,2*k)/ +% binomial(4*m-1,4*k)*(4*m^2+16*k^2-16*k*m+16*k-6*m+3)/ +% ((4*m-4*k-3)*(4*m-4*k-1)),k,m); +sumrecursion((-1)^k*binomial(n,k)*binomial(k,n),k,n); + + +summ(n - 1) + summ(n) + +sumrecursion((-1)^k*binomial(n,k)*binomial(2*k,n),k,n); + + +2*summ(n - 1) + summ(n) + +sumrecursion((-1)^k*binomial(n,k)*binomial(k,j)^2,k,n); + + + 2 +(n - 1 - 2*j)*summ(n - 1)*n - (j - n) *summ(n) + +sumrecursion(binomial(n,k)*binomial(a,k),k,n); + + +(a + n)*summ(n - 1) - summ(n)*n + +sumrecursion((3*k-2*n)*binomial(n,k)^2*binomial(2*k,k),k,n); + + +summ(n - 1) - summ(n) + +sumrecursion(binomial(n-k,k),k,n); + + +summ(n - 1) - summ(n) + summ(n - 2) + +sumrecursion(binomial(n,k)*binomial(n+k,k),k,n); + + +6*summ(n - 1)*n - 3*summ(n - 1) - summ(n)*n - (n - 1)*summ(n - 2) + +% sumrecursion(binomial(n+k,m+2*k)*binomial(2*k,k)*(-1)^k/(k+1),k,n); +sumrecursion((-1)^k*binomial(n-k,k)*binomial(n-2*k,m-k),k,n); + + +summ(n - 1) - summ(n) + +% sumrecursion((-1)^k*binomial(n-k,k)*binomial(n-2*k,m-k),k,m); +sumrecursion(binomial(n+k,2*k)*2^(n-k),k,n); + + +5*summ(n - 1) - summ(n) - 4*summ(n - 2) + +sumrecursion(binomial(n,k)*binomial(2*k,k)*(-1/4)^k,k,n); + + +(2*n - 1)*summ(n - 1) - 2*summ(n)*n + +% sumrecursion(binomial(n,i)*binomial(2*n,n-i),i,n); +sumrecursion((-1)^k*binomial(n,k)*binomial(2*k,k)*4^(n-k),k,n); + + +2*(2*n - 1)*summ(n - 1) - summ(n)*n + +sumrecursion((-1)^k*binomial(n,k)/binomial(k+a,k),k,n); + + +summ(n - 1) + summ(n) + +% sumrecursion((-1)^k*binomial(n,k)/binomial(k+a,k),k,a); +sumrecursion((-1)^(n-k)*binomial(2*n,k)^2,k,n); + + +2*(2*n - 1)*summ(n - 1) - summ(n)*n + +sumrecursion(factorial(a+k)*factorial(b+k)*factorial(n+c-a-b-k-1)/( +factorial(k+1)*factorial(n-k)*factorial(k+c)),k,a); + + + - (n + 1 + c - a)*(b - c + a)*summ(a) + (a - c)*(a - 1)*summ(a - 1) + +% sumrecursion(factorial(a+k)*factorial(b+k)*factorial(n+c-a-b-k-1)/( +% factorial(k+1)*factorial(n-k)*factorial(k+c)),k,b); +% sumrecursion(factorial(a+k)*factorial(b+k)*factorial(n+c-a-b-k-1)/( +% factorial(k+1)*factorial(n-k)*factorial(k+c)),k,c); +sumrecursion(binomial(2*n+1,2*p+2*k+1)*binomial(p+k,k),k,n); + + +(2*p + 1 - 2*n)*(n - p)*summ(n) - 2*(p + 1 - 2*n)*(2*n - p)*summ(n - 1) + +% sumrecursion(binomial(2*n+1,2*p+2*k+1)*binomial(p+k,k),k,p); +sumrecursion(binomial(r,m)*binomial(s,t-m),m,r); + + +(s - t + r)*summ(r) - (r + s)*summ(r - 1) + +% sumrecursion(binomial(r,m)*binomial(s,t-m),m,s); +% sumrecursion(binomial(r,m)*binomial(s,t-m),m,t); +sumrecursion(binomial(2*n+1,2*k)*binomial(m+k,2*n),k,n); + + +(2*n - 3 - 2*m)*(n - 1 - m)*summ(n - 1) - (2*n - 1)*summ(n)*n + +% sumrecursion(binomial(2*n+1,2*k)*binomial(m+k,2*n),k,m); +sumrecursion(binomial(n,k)*binomial(k,j)*x^j,k,n); + + +(j - n)*summ(n) + 2*summ(n - 1)*n + +% sumrecursion(binomial(n,k)*binomial(k,j)*x^j,k,j); +% sumrecursion(binomial(n,k)*binomial(k,j)*x^k,k,n); +sumrecursion(x*binomial(n+k,2*k)*((x^2-1)/4)^(n-k),k,n); + + + 2 2 2 + - ((x + 1) *(x - 1) *summ(n - 2) + 16*summ(n)) + 8*(x + 1)*summ(n - 1) + +sumrecursion(binomial(n+k-1,2*k-1)*(x-1)^(2*k)*x^(n-k)/k,k,n); + + + 2 2 + - ((n - 2)*summ(n - 2)*x + summ(n)*n) + (n - 1)*(x + 1)*summ(n - 1) + +sumrecursion( +1/(k+1)*binomial(2*k,k)/(n-k+1)*binomial(2*n-2*k,n-k),k,n); + + +summ(n - 1) + summ(n) + +sumrecursion(binomial(m,r)*binomial(n-r,n-r-q)*(t-1)^r,r,m); + + +(t + 1 + n*t - (t - 1)*q - (t + 1)*m)*summ(m - 1) + + - ((n + 1 - m)*summ(m) - (m - 1)*summ(m - 2)*t) + +% sumrecursion(binomial(m,r)*binomial(n-r,n-r-q)*(t-1)^r,r,n); +% sumrecursion(binomial(m,r)*binomial(n-r,n-r-q)*(t-1)^r,r,q); +% sumrecursion(binomial(m,r)*binomial(n-r,n-r-q)*(t-1)^r,r,r); +sumrecursion(pochhammer(-n/2,k)*pochhammer(-n/2+1/2,k)/ +(factorial(k)*pochhammer(b+1/2,k)),k,n); + + +(n - 1 + 2*b)*summ(n) - 2*(n - 1 + b)*summ(n - 1) + +% Watson +% sumrecursion(pochhammer(a,k)*pochhammer(b,k)*pochhammer(c,k)/( +% factorial(k)*pochhammer(1/2*(a+b+1),k)*pochhammer(2*c,k)),k,c); +% sumrecursion(pochhammer(-m,j)*pochhammer(m+2*k+2,j)*pochhammer(k+1/2,j)/ +% (factorial(j)*pochhammer(k+3/2,j)*pochhammer(2*k+1,j)),j,k); +sumrecursion((-1)^k*binomial(n,k)^3,k,n); + + + 2 +3*(3*n - 2)*(3*n - 4)*summ(n - 2) + summ(n)*n + +% sumrecursion(pochhammer(-n,k)*pochhammer(n+2*a,k)*pochhammer(a,k)/( +% factorial(k)*pochhammer(2*a/2,k)*pochhammer((2*a+1)/2,k))*(2/4)^k,k,n); +% sumrecursion(pochhammer(-n,k)*pochhammer(n+4*a,k)*pochhammer(a,k)/( +% factorial(k)*pochhammer(4*a/2,k)*pochhammer((4*a+1)/2,k))*(4/4)^k,k,n); +% sumrecursion(binomial(n+k+1,n-k)*pochhammer(-n+k,j)*pochhammer(k+1/2,j)* +% pochhammer(n+k+2,j)/(factorial(j)*pochhammer(k+3/2,j)* +% pochhammer(2*k+1,j)),j,n); +% sumrecursion(pochhammer(-m,j)*pochhammer(m+2*k+2,j)* +% pochhammer(k+1/2,j)/( +% factorial(j)*pochhammer(k+3/2,j)*pochhammer(2*k+1,j)),j,m); +% sumrecursion(binomial(n+k+1,n-k)*pochhammer(-n+k,j)* +% pochhammer(k+1/2,j)* +% pochhammer(n+k+2,j)/(factorial(j)*pochhammer(k+3/2,j)* +% pochhammer(2*k+1,j)), +% j,k); +% sumrecursion(pochhammer(a+b+c-n,j+l)*pochhammer(a+b-n/2,j+l)/ +% (factorial(j)*factorial(l)*pochhammer(a-n/2+1,j)* +% pochhammer(b-n/2+1,l)),j,a); +% sumrecursion(pochhammer(a+b+c-n,j+l)*pochhammer(a+b-n/2,j+l)/ +% (factorial(j)*factorial(l)*pochhammer(a-n/2+1,j)* +% pochhammer(b-n/2+1,l)),j,b); +sumrecursion(pochhammer(a+b+c-n,j+l)*pochhammer(a+b-n/2,j+l)/ +(factorial(j)*factorial(l)*pochhammer(a-n/2+1,j)* + pochhammer(b-n/2+1,l)),j,c); + + + - (n + 1 - l - c - b - a)*(n + 2 - 2*l - 2*c - 2*b)*summ(c - 1) + + + 2*(n + 1 - 2*l - c - 2*b - a)*(n + 1 - c - b - a)*summ(c) + +% sumrecursion( +% (-1)^(a+b+c)*gamma(a+b+c-d/2)*gamma(d/2-c)*gamma(a+c-d/2)* +% gamma(b+c-d/2)/ +% (gamma(a)*gamma(b)*gamma(d/2)*gamma(a+b+2*c-d)*(m^2)^(a+b+c-d))* +% pochhammer(a+b+c-d,k)*pochhammer(a+c-d/2,k)/ +% (pochhammer(a+b+2*c-d,k)*factorial(k)),k,a); +% sumrecursion( +% (-1)^(a+b+c)*gamma(a+b+c-d/2)*gamma(d/2-c)*gamma(a+c-d/2)* +% gamma(b+c-d/2)/ +% (gamma(a)*gamma(b)*gamma(d/2)*gamma(a+b+2*c-d)*(m^2)^(a+b+c-d))* +% pochhammer(a+b+c-d,k)*pochhammer(a+c-d/2,k)/ +% (pochhammer(a+b+2*c-d,k)*factorial(k)),k,b); +% sumrecursion( +% (-1)^(a+b+c)*gamma(a+b+c-d/2)*gamma(d/2-c)*gamma(a+c-d/2)* +% gamma(b+c-d/2)/ +% (gamma(a)*gamma(b)*gamma(d/2)*gamma(a+b+2*c-d)*(m^2)^(a+b+c-d))* +% pochhammer(a+b+c-d,k)*pochhammer(a+c-d/2,k)/ +% (pochhammer(a+b+2*c-d,k)*factorial(k)),k,c); +% sumrecursion(pochhammer(-n,k)*pochhammer(n+3*a,k)*pochhammer(a,k)/( +% factorial(k)*pochhammer(3*a/2,k)* +% pochhammer((3*a+1)/2,k))*(3/4)^k,k,n); +% summand:=k*(-1)^j*pochhammer(2*k+j+1,j)*pochhammer(2*k+2*j+2,n-k-j)/( +% factorial(k+j)*factorial(j)*factorial(n-k-j))*exp(-(j+k)*t)$ +% summand:=k*(-1)^j*pochhammer(2*k+j+1,j)*pochhammer(2*k+2*j+2,n-k-j)/( +% (k+j)*factorial(j)*factorial(n-k-j))*exp(-(j+k)*t)$ +% sumrecursion(summand,j,n); +clear(summand); + + + +% 6) Finding recurrence equations for hypergeometric functions +% Koornwinder, T. H.: +% On Zeilberger's algorithm and +% its q-analogue: a rigorous description. +% J. of Comput. and Appl. Math. 48, 1993, 91-111. + +% Gauss +hyperrecursion({a,b},{c},1,a); + + +(b - c + a)*summ(a) - (a - c)*summ(a - 1) + +% Dougall +% hyperrecursion({d,1+d/2,d+b-a,d+c-a,1+a-b-c,n+a,-n}, +% {d/2,1+a-b,1+a-c,b+c+d-a,1+d-a-n,1+d+n},1,n); +% Baxter +% hyperrecursion({-n,-n-1,-n-2},{2,3},-1,n); +% Krawtchouk polynomials +% krawtchoukterm := +% (-1)^n*p^n*binomial(NN,n)*hyperterm({-n,-x},{-NN},1/p,k)$ +% sumrecursion(krawtchoukterm,k,n); +% sumrecursion(krawtchoukterm,k,x); +% sumrecursion(krawtchoukterm,k,NN); +% clear(krawtchoukterm); +% hyperrecursion({-n,b,c+4},{b+1,c},1,n); +hyperrecursion({-n,b,c+1,d+1},{b+1,c,d},1,n); + + +recursion valid for n>=3 + +(b + n)*summ(n) - summ(n - 1)*n + + +% 7) Extended versions of Gosper's and Zeilberger's algorithms +% Koepf, W.: +% Algorithms for the indefinite and definite summation. +% Konrad-Zuse-Zentrum Berlin (ZIB), Preprint SC 94-33, 1994. + +% extended Gosper algorithm +extended_gosper(k*factorial(k/7),k,7); + + + k +(k + 7)*factorial(---) + 7 + +extended_gosper(k*factorial(k/2),k,2); + + + k +(k + 2)*factorial(---) + 2 + +extended_gosper(k*factorial(k/2),k); + + + k k - 1 +(k + 2)*factorial(---) + (k + 1)*factorial(-------) + 2 2 + +extended_gosper(binomial(k/2,n),k); + + + k k - 1 + (k + 2)*binomial(---,n) + (k + 1)*binomial(-------,n) + 2 2 +------------------------------------------------------- + 2*(n + 1) + +extended_gosper(binomial(n,k/2)-binomial(n,k/2-1),k); + + + k - 3 k - 1 +( - ((2*n + 3 - k)*(n + 1 - k)*(binomial(n,-------) - binomial(n,-------)) + 2 2 + + k - 2 k + + (n + 2 - k)*(2*(n + 1) - k)*(binomial(n,-------) - binomial(n,---))))/(2 + 2 2 + + *(n + 2 - k)*(n + 1 - k)) + + +% extended Zeilberger algorithm +% extended_sumrecursion(binomial(n,k)*binomial(k/2,n),k,n,1,2); +sumrecursion(binomial(n,k)*binomial(k/2,n),k,n); + + +recursion valid for n>=3 + +summ(n - 1) + 2*summ(n) + +extended_sumrecursion(binomial(n/2,k),k,n,2,1); + + +2*summ(n - 2) - summ(n) + +sumrecursion(binomial(n/2,k),k,n); + + +2*summ(n - 2) - summ(n) + +% sumrecursion(hyperterm({a,b,a+1/2-b,1+2*a/3,-n}, +% {2*a+1-2*b,2*b,2/3*a,1+a+n/2},4,k)/ +% (factorial(n)*2^(-n)/factorial(n/2))/ +% hyperterm({a+1,1},{a-b+1,b+1/2},1,n/2),k,n); + +% Watson +% sumrecursion(pochhammer(a,k)*pochhammer(b,k)*pochhammer(c,k)/( +% factorial(k)*pochhammer(1/2*(a+b+1),k)*pochhammer(2*c,k))/ +% (GAMMA(1/2)*GAMMA(1/2+c)*GAMMA(1/2+a/2+b/2)*GAMMA(1/2-a/2-b/2+c))* +% GAMMA(1/2+a/2)*GAMMA(1/2+b/2)*GAMMA(1/2-a/2+c)*GAMMA(1/2-b/2+c),k,a); +% hyperrecursion({a,b,c},{1/2*(a+b+1),2*c},1,a); +% hyperrecursion({a,b,c},{1/2*(a+b+1),2*c},1,b); + +% 8) Closed form representations of hypergeometric sums + +% Vandermonde +hypersum({-n,b},{c},1,n); + + + pochhammer( - b + c,n) +------------------------ + pochhammer(c,n) + +% Saalschuetz +hypersum({a,b,-n},{c,1+a+b-c-n},1,n); + + + pochhammer( - a + c,n)*pochhammer( - b + c,n) +----------------------------------------------- + pochhammer( - a - b + c,n)*pochhammer(c,n) + +% Kummer +hypersum({a,-n},{1+a+n},-1,n); + + + pochhammer(a + 1,n) +----------------------- + a + 2 + pochhammer(-------,n) + 2 + +% Dixon +hypersum({a,b,-n},{1+a-b,1+a+n},1,n); + + + a - 2*b + 2 + pochhammer(a + 1,n)*pochhammer(-------------,n) + 2 +------------------------------------------------- + a + 2 + pochhammer(a - b + 1,n)*pochhammer(-------,n) + 2 + +% Dougall +% hypersum({a,1+a/2,b,c,d,1+2*a-b-c-d+n,-n}, +% {a/2,1+a-b,1+a-c,1+a-d,1+a-(1+2*a-b-c-d+n),1+a+n},1,n); +% Clausen +% hypersum({a,b,1/2-a-b-n,-n},{1/2+a+b,1-a-n,1-b-n},1,n); + +hypersum({a,1+a/2,c,d,-n},{a/2,1+a-c,1+a-d,1+a+n},1,n); + + + pochhammer(a - c - d + 1,n)*pochhammer(a + 1,n) +------------------------------------------------- + pochhammer(a - c + 1,n)*pochhammer(a - d + 1,n) + +hypersum({a,1+a/2,d,-n},{a/2,1+a-d,1+a+n},-1,n); + + + pochhammer(a + 1,n) +------------------------- + pochhammer(a - d + 1,n) + + +% m-fold case: +hypersum({-n,-n,-n},{1,1},1,n); + + + n/2 2 n 1 n + ( - 27) *pochhammer(---,---)*pochhammer(---,---) + 3 2 3 2 +{----------------------------------------------------, + n 2 + factorial(---) + 2 + + 0} + +% hypersum({-n,n+3*a,a},{3*a/2,(3*a+1)/2},3/4,n); + +% 9) Hypergeometric representations + +sumtohyper(binomial(n,k)^3,k); + + +hypergeom({ - n, - n, - n},{1,1},-1) + +sumtohyper(binomial(n,k)/2^n-sub(n=n-1,binomial(n,k)/2^n),k); + + + - n + 2 - n + - hypergeom({----------, - n},{------},-1) + 2 2 +--------------------------------------------- + n + 2 + +sumtohyper(binomial(k+j-1,k-j)*2*(-1)^(j+1)*factorial(2*j-1)/ +factorial(j-1)/factorial(j+1)*x^j,j); + + +hypergeom({k + 1, - k + 1},{3},x)*k*x + +% term:=1/(n-1+k)*(1/2-1/2*x)^k/n*binomial(k-n-1,-n-1)*k* +% binomial(n-1+k,n-1); +% sumtohyper(sub(n=n+1,term)-term,k); + +end; +(TIME: zeilberg 141560 147540)