Sun May 31 14:17:29 MDT 1998 aquarius% reduce REDUCE 3.6, 15-Jul-95, patched to 15 Apr 96 ... 1: % ----------[ R e d u c e ]---------- % ---------- Initialization ---------- on multiplicities; on time; Time: 0 ms % ---------- Sums ---------- % Simplify the sum below to sum(x[i]^2, i = 1..n) - sum(x[i], i = 1..n)^2/n operator x; Time: 0 ms xbar:= sum(x(j), j, 1, n) / n; sum(x(j),j,1,n) xbar := ----------------- n Time: 110 ms sum((x(i) - xbar)^2, i, 1, n); 2 x(i) 2 sum(x(i) ,i,1,n)*n - 2*sum(------,i,1,n)*sum(x(j),j,1,n)*n + sum(x(j),j,1,n) n ------------------------------------------------------------------------------- n Time: 180 ms clear xbar; Time: 0 ms % Derivation of the least squares fitting of data points (x[i], y[i]) to a % line y = m x + b. See G. Keady, ``Using Maple's linalg package with Zill % and Cullen _Advanced Engineering Mathematics_, Part II: Vectors, Matrices % and Vector Calculus'', University of Western Australia, % ftp://maths.uwa.edu.au/pub/keady/ operator y; Time: 0 ms f:= sum((y(i) - m*x(i) - b)^2, i, 1, n)$ Time: 160 ms solve({df(f, m) = 0, df(f, b) = 0}, {m, b}); sum(x(i)*y(i),i,1,n)*n - sum(x(i),i,1,n)*sum(y(i),i,1,n) {{m=----------------------------------------------------------, 2 2 sum(x(i) ,i,1,n)*n - sum(x(i),i,1,n) 2 sum(x(i) ,i,1,n)*sum(y(i),i,1,n) - sum(x(i)*y(i),i,1,n)*sum(x(i),i,1,n) b=-------------------------------------------------------------------------}} 2 2 sum(x(i) ,i,1,n)*n - sum(x(i),i,1,n) Time: 460 ms plus GC time: 20 ms clear f, x, y; Time: 0 ms % Indefinite sum => (-1)^n binomial(2 n, n). See Herbert S, Wilf, % ``IDENTITIES and their computer proofs'', University of Pennsylvania. load_package(specfn)$ Time: 1270 ms load_package(zeilberg)$ *** gamma already defined as operator *** pochhammer already defined as operator *** binomial already defined as operator Time: 50 ms sum((-1)^k * Binomial(2*n, k)^2, k); k 2 sum(( - 1) *binomial(2*n,k) ,k) Time: 20 ms % Check whether the full Gosper algorithm is implemented % => 1/2^(n + 1) binomial(n, k - 1) sum(Binomial(n, k)/2^n - Binomial(n + 1, k)/2^(n + 1), k); binomial(n,k) - binomial(n + 1,k) sum(---------------,k) + sum(----------------------,k) n n 2 2*2 Time: 30 ms gosper(Binomial(n, k)/2^n - Binomial(n + 1, k)/2^(n + 1), k); - (n + 1 - k)*(binomial(n + 1,k) - 2*binomial(n,k)) ------------------------------------------------------ n 2*2 *(n + 1 - 2*k) Time: 3720 ms plus GC time: 540 ms simplify_combinatorial(ws); (n + 1 - k)*gamma(n + 2) -------------------------------------------- n 2*2 *(n + 1)*gamma(k + 1)*gamma(n + 2 - k) Time: 1580 ms plus GC time: 210 ms ws where gammatofactorial; factorial(n + 1)*( - k + n + 1) --------------------------------------------------- n 2*2 *factorial( - k + n + 1)*factorial(k)*(n + 1) Time: 20 ms % Dixon's identity (check whether Zeilberger's algorithm is implemented). % Note that the indefinite sum is equivalent to the definite % sum(..., k = -min(a, b, c)..min(a, b, c)) => (a + b + c)!/(a! b! c!) % [Wilf] sum((-1)^k * Binomial(a+b, a+k) * Binomial(b+c, b+k) * Binomial(c+a, c+k), k); k sum(( - 1) *binomial(a + b,a + k)*binomial(a + c,c + k)*binomial(b + c,b + k),k) Time: 30 ms % Telescoping sum => g(n + 1) - g(0) operator g; Time: 0 ms sum(g(k + 1) - g(k), k, 0, n); sum(g(k + 1),k,0,n) + sum( - g(k),k,0,n) Time: 30 ms clear g; Time: 0 ms % => n^2 (n + 1)^2 / 4 sum(k^3, k, 1, n); 2 2 n *(n + 2*n + 1) ------------------- 4 Time: 10 ms on factor; Time: 0 ms ws; 2 2 (n + 1) *n ------------- 4 Time: 0 ms off factor; Time: 0 ms % See Daniel I. A. Cohen, _Basic Techniques of Combinatorial Theory_, John % Wiley and Sons, 1978, p. 60. The following two sums can be derived directly % from the binomial theorem: % sum(k^2 * binomial(n, k) * x^k, k = 1..n) = n x (1 + n x) (1 + x)^(n - 2) % => n (n + 1) 2^(n - 2) [Cohen, p. 60] sum(k^2 * Binomial(n, k), k, 1, n); 2 sum(k *binomial(n,k),k,1,n) Time: 20 ms % => [2^(n + 1) - 1]/(n + 1) [Cohen, p. 83] sum(Binomial(n, k)/(k + 1), k, 0, n); binomial(n,k) sum(---------------,k,0,n) k + 1 Time: 30 ms % Vandermonde's identity => binomial(n + m, r) [Cohen, p. 31] sum(Binomial(n, k) * Binomial(m, r - k), k, 0, r); sum(binomial(m, - k + r)*binomial(n,k),k,0,r) Time: 40 ms % => Fibonacci[2 n] [Cohen, p. 88] %sum(Binomial(n, k) * Fibonacci(k), k, 0, n); % => Fibonacci[n] Fibonacci[n + 1] [Cohen, p. 65] %sum(Fibonacci(k)^2, k, 1, n); % => 1/2 cot(x/2) - cos([2 n + 1] x/2)/[2 sin(x/2)] % See Konrad Knopp, _Theory and Application of Infinite Series_, Dover % Publications, Inc., 1990, p. 480. sum(sin(k*x), k, 1, n); 2*n*x + x x - cos(-----------) + cos(---) 2 2 -------------------------------- x 2*sin(---) 2 Time: 40 ms % => sin(n x)^2/sin x [Gradshteyn and Ryzhik 1.342(3)] load_package(trigsimp)$ Time: 360 ms sum(sin((2*k - 1)*x), k, 1, n); - cos(2*n*x) + 1 ------------------- 2*sin(x) Time: 50 ms plus GC time: 80 ms trigsimp(ws); 2 sin(n*x) ----------- sin(x) Time: 150 ms % => Fibonacci[n + 1] [Cohen, p. 87] sum(Binomial(n - k, k), k, 0, floor(n/2)); n sum(binomial( - k + n,k),k,0,floor(---)) 2 Time: 40 ms % => pi^2 / 6 + zeta(3) =~ 2.84699 sum(1/k^2 + 1/k^3, k, 1, infinity); 2 6*zeta(3) + pi ----------------- 6 Time: 40 ms on rounded; Time: 0 ms ws; 2.84699097001 Time: 30 ms off rounded; Time: 0 ms % => pi^2/12 - 1/2 (log 2)^2 [Gradshteyn and Ryzhik 0.241(2)] sum(1/(2^k*k^2), k, 1, infinity); 1 sum(-------,k,1,infinity) k 2 2 *k Time: 30 ms % => pi/12 sqrt(3) - 1/4 log 3 [Knopp, p. 268] sum(1/((3*k + 1)*(3*k + 2)*(3*k + 3)), k, 0, infinity); 1 sum(--------------------------,k,0,infinity) 3 2 27*k + 54*k + 33*k + 6 Time: 30 ms % => 1/2 (2^(n - 1) + 2^(n/2) cos(n pi/4)) [Gradshteyn and Ryzhik 0.153(1)] sum(Binomial(n, 4*k), k, 0, infinity); sum(binomial(n,4*k),k,0,infinity) Time: 20 ms % => 1 [Knopp, p. 233] sum(1/(sqrt(k*(k + 1)) * (sqrt(k) + sqrt(k + 1))), k, 1, infinity); 1 sum(-------------------------------------------------,k,1,infinity) 2 2 sqrt(k + 1)*sqrt(k + k) + sqrt(k)*sqrt(k + k) Time: 50 ms % => 1/sqrt([1 - x y]^2 - 4 x^2) (| x y | < 1 and -1 <= x < 1). % From Evangelos A. Coutsias, Michael J. Wester and Alan S. Perelson, ``A % Nucleation Theory of Cell Surface Capping'', draft. sum(sum(Binomial(n, k)*Binomial(n - k, n - 2*k)*x^n*y^(n - 2*k), k, 0, floor(n/2)), n, 0, infinity); n n binomial( - k + n, - 2*k + n)*binomial(n,k) n sum(y *x *sum(---------------------------------------------,k,0,floor(---)),n,0, 2*k 2 y infinity) Time: 310 ms plus GC time: 80 ms % An equivalent summation to the above is: sum(sum(factorial(n)/(factorial(k)^2*factorial(n - 2*k))*(x/y)^k*(x*y)^(n - k), n, 2*k, infinity), k, 0, infinity); n x k (x*y) *factorial(n) sum((---) *sum(--------------------------------------------,n,2*k,infinity),k,0, y k 2 (x*y) *factorial( - 2*k + n)*factorial(k) infinity) Time: 350 ms % => pi/2 [Knopp, p. 269] sum(prod(k/(2*k - 1), k, 1, m), m, 2, infinity); gamma(m + 1) sqrt(pi)*sum(---------------------,m,2,infinity) m 2*m + 1 2 *gamma(---------) 2 Time: 130 ms plus GC time: 70 ms % ---------- Quit ---------- quit; Quitting real 31.49 user 10.54 sys 2.38