sum  definite and indefinite symbolic summation
Sum  inert form of sum

Calling Sequence


sum(f, k)


sum(f, k=m..n, parametric)


sum(f, k=alpha)


sum(f, expr)


Sum(f, k)


Sum(f, k=m..n)


Sum(f, k=alpha)


Sum(f, k=expr)






Parameters


f



expression

k



name; summation index

m, n



integers or arbitrary expressions

parametric



(optional) literal name

alpha



RootOf expression

expr



expression, of type algebraic, not containing k





Basic Information


•

This help page contains complete information about the sum command. For basic information on the sum command, see the sum help page.



Description


•

The sum command (
definition of sum
) is for symbolic summation. It is used to compute a closed form for an indefinite or definite sum. A typical example is sum(k,k=0..n1), which returns .

•

You can enter the sum command using either the 1D or 2D calling sequence. For example, sum(k^2, k) is equivalent to .



Note


•

To add a finite sequence of values, rather than compute a formula, use the add command. For example, add(k, k=0..9) returns 45. Although the sum command can often be used to compute explicit sums, it is strongly recommended that the add command be used in programs if an explicit sum is needed, in particular, when summing over all elements of a list, Array, Matrix, or similar data structure. For more details and examples, see the Comparing sum and add section in this help page.



Details


•

The call sum(f, k) computes an indefinite sum of f(k) with respect to k. It computes an antidifference g(k) of f(k) such that g(k+1)g(k)=f(k) for all k.

•

The call sum(f, k=m..n) computes the definite sum of f(k) over the given range m..n. That is, it computes f(m) + f(m+1) + ... + f(n). If m = n+1, the value returned is 0. If m > n+1 are integers, the value returned is sum(f, k=n+1..m1). With these conventions, the following holds for all integers l,m,n.

•

The call sum(f, k=alpha) computes the definite sum of f(k) summed over the roots of a polynomial alpha where alpha must be a RootOf.

•

The call sum(f, k=expr) substitutes the value of expr for k in f.

•

For indefinite summation, Maple uses the following methods:

a.

Polynomials are summed using a formula based on Bernoulli polynomials.

b.

Rational functions of k are summed using the algorithm that solves the additive decomposition problem of rational functions. The result is a rational function plus a sum of terms involving the Polygamma function and its derivatives.

c.

Hypergeometric terms, for example, expressions containing factorials (including binomial coefficients) and powers, are summed using Gosper's algorithm and the algorithm that solves the additive decomposition problem of hypergeometric terms. An extension of Gosper's algorithm is used to handle summands which are sums of hypergeometric terms. Koepf's extension to Gosper's algorithm is used to handle jfold hypergeometric terms.

d.

The method of accurate summation.

e.

Additionally, a library extension mechanism is used to include sums for which an algorithmic approach to finding closed forms is not yet implemented or does not yet exist (that is, the pattern match approach is employed in principal). Currently the computable summands include expressions containing the harmonic function; the logarithmic function; the digamma and polygamma functions; and the sine, cosine, and exponential functions.

•

For definite sums, if nm is a small integer, the sum is computed directly. Otherwise, Maple uses the following methods:

a.

Classical telescoping computes a closed form of the definite sum of f over the specified range of k using telescoping method, or NewtonLeibniz's formula. That is, it first computes a closed form of the corresponding indefinite sum.

b.

Creative telescoping method for computing closed forms of definite sums of hypergeometric terms.

c.

Conversion method computes a closed form of the definite sum of f over the specified range of k by first converting the specified sum into hypergeometric functions. If possible, the output is then converted to standard functions.

d.

As in the case for indefinite sums, the patternmatch approach is also employed.

•

If Maple cannot find a closed form for the summation, the function call is returned. (Maple displays the sum function using a stylized summation sign.)

•

The capitalized function name Sum is the inert sum function, which simply returns unevaluated. It appears gray so that it is easily distinguished from a returned sum calling sequence.

•

For divergent sums, the sum command may return infinity, infinity, unevaluated, or a finite result correct in the sense of analytic continuation. This behavior can be changed by setting the _EnvFormal environment variable. By default, the _EnvFormal environment variable is unassigned.


If _EnvFormal is assigned true, the sum command uses resummation methods to return a finite result for various classes of divergent sums.


If _EnvFormal is assigned false, the sum command uses more convergence testing to detect divergence for infinite sums. It more often returns infinity, infinity, or unevaluated for divergent sums. This may slow down the computation.


If _EnvFormal is assigned false and the summation bounds are numeric, the sum command also tries harder to detect removable singularities in the interval of summation, and returns an error in that case. By default, sum will try to remove them.



Options


•

If the option parametric is specified for a definite sum, then a result is returned that is valid for all possible integer values of any parameters occurring in the summand or the summation bounds. In general, the result is expressed in terms of piecewise functions.



Compatibility


•

The sum command was updated in Maple 15.



Examples


Indefinite sums
Polynomials:
>


 (1) 
Rationals:
>


 (2) 
Hypergeometric terms:
>


 (3) 
2fold hypergeometric terms:
>


 (4) 
Sum of hypergeometric terms:
>


 (5) 
Accurate summation
>


 (6) 
Additive decomposition of hypergeometric terms:
>


 (7) 
Library extension mechanism:
>


 (8) 
Definite sums
Classical telescoping:
>


 (9) 
>


 (10) 
Creative telescoping:
>


 (11) 
Conversion method:
>


 (12) 
Pattern match (Abel's type):
>


 (13) 
Maple returns the call unevaluated if it cannot find a closed form.
>


 (14) 
If the inert function is used, Maple returns unevaluated.
>


 (15) 
>


 (16) 
>


 (17) 
>


 (18) 
>


 (19) 
>


 (20) 
>


 (21) 
Parametric case discussions may be returned:
>


 (22) 
>


 (23) 
>


Warning, unable to determine if the summand is singular in the interval of summation; try to use assumptions or use the parametric option
 
 (24) 
>


 (25) 
If _EnvFormal is assigned true, the sum command uses resummation methods to return a finite result for various classes of divergent sums.
>


 (26) 
>


 (27) 
>


 (28) 
Setting _EnvFormal to false will also trigger detection of removable singularities in the interval of summation for numerical bounds.
>


 (29) 
>


 (30) 
>


>


 (31) 


Comparing sum and add



The sum command tries to find a formula for a definite sum, while the add command adds a finite sequence of terms.

 (32) 
>

f := add(x^k,k=1..10000):

 (33) 
 (34) 

For short finite sums, the sum command uses the add command.

 (35) 
 (36) 

The add command can be used only if the summation bounds are numeric.

>

powersum := proc(a,b)
local k;
sum(3^k, k=a..b);
end proc:

>

poweradd := proc(a,b)
local k;
add(3^k, k=a..b);
end proc:

 (37) 
 (38) 
 (39) 

The results from sum and add differ when the upper bound is less than the lower bound.

 (40) 
 (41) 

In contrast to the sum command, the add command has special evaluation rules. Thus, no unevaluation quotes are necessary when summing over an expression that gives an error when evaluated at a noninteger.

>

v := Vector([1,2,3,4,5]);

 (42) 
 (43) 
 (44) 

The summation variable is local to the add command, but not to the sum command. The sum command raises an error if the summation variable has a value.

 (45) 
 (46) 
 (47) 

In contrast to the sum command, the add command is implemented in the Maple kernel. When it is applicable, it is usually much more efficient. An exception to this rule is the case in which there is a large number of terms and the sum command is able to compute a closed form.

>

for i from 1 to 1000 do
add(x^k,k=1..10):
end do:
time()  t;

 (48) 
>

for i from 1 to 1000 do
sum(x^k,k=1..10):
end do:
time()  t;

 (49) 
>

for i from 1 to 100 do
add(x^k,k=1..1000):
end do:
time()  t;

 (50) 
>

for i from 1 to 100 do
sum(x^k,k=1..1000):
end do:
time()  t;

 (51) 


See Also


add, collect, convert/StandardFunctions, evalf/Sum, expand, normal, product, RootOf, sum/numerical, SumTools, SumTools[IndefiniteSum][AddIndefiniteSum]


References



Abramov, S.A. "Indefinite Sums of Rational Functions." In Proceedings ISSAC '95, pp. 303308. Edited by A. H. M. Levelt. New York: ACM Press, 1995.


Abramov, S.A.; Carette, J.J.; Geddes, K.O.; and Le, H.Q. "Symbolic Summation in Maple." University of Waterloo Technical Report CS200232, Department of Computer Science, 2002.


Abramov, S.A., and Petkovsek, M. "Rational Normal Forms and Minimal Decompositions of Hypergeometric Terms." Journal of Symbolic Computation, (May 2002): 521543.


Abramov, S.A., and Petkovsek, M. "Gosper's Algorithm, Accurate Summation, and the discrete NewtonLeibniz formula." Proceedings ISSAC'05, (2005): 512.


Abramov, S.A., and van Hoeij, M. "Integration of Solutions of Linear Functional Equations." Integral Transformations and Special Functions, (1999): 312.


Abramov, S. A., and Zima, E. V. "D'Alembertian Solutions of Inhomogeneous Equations (differential, difference, and some other)." In Proceedings ISSAC '96, pp. 232240. Edited by Y. N. Lakshman. New York: ACM Press, 1996.


Gosper, R.W., Jr. "Decision Procedure for Indefinite Hypergeometric Summation." Proceedings of the National Academy of Sciences, (January 1978): 4042.


Koepf, W. "Algorithms for mFold Hypergeometric Summation." Journal of Symbolic Computation, (October 1995): 399417.


Petkovsek, M.; Wilf, H.; and Zeilberger, D. A=B. Wellesley, Massachusetts: A. K. Peters Ltd., 1996.


Prudnikov, A. P.; Brychkov, Yu.; and Marichev, O. Integrals and Series, Volume 3: More Special Functions. Gordon and Breach Science, 1990.


Roach, K. "Hypergeometric Function Representations." In Proceedings ISSAC '96, pp. 301308. Edited by Y. N. Lakshman. New York: ACM Press, 1996.


van Hoeij, M. "Finite Singularities and Hypergeometric Solutions of Linear Recurrence Equations." Journal of Pure and Applied Algebra, (June 1999): 109131.


Zeilberger, D. "The Method of Creative Telescoping." Journal of Symbolic Computation, (March 1991): 195204.


