sum - Maple Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Group Theory : Inert Functions : sum/details

sum

definite and indefinite symbolic summation

Sum

inert form of sum

 

Calling Sequence

Parameters

Basic Information

Description

Note

Details

Options

Examples

Examples for the parametric case

Comparing sum and add

References

Compatibility

Calling Sequence

sum(f, k)

kf

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

k=mnf

sum(f, k=alpha)

k=αf

sum(f, k=expr)

k=exprf

Sum(f, k)

kf

Sum(f, k=m..n)

k=mnf

Sum(f, k=alpha)

k=αf

Sum(f, k=expr)

k=exprf

Parameters

f

-

expression

k

-

name; summation index

m, n

-

integers or arbitrary expressions

parametric

-

(optional) literal name

b

-

(optional) either true or false

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..n-1), which returns 12n212n.

• 

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

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 fk with respect to k. It computes an anti-difference gk of fk such that gk+1gk=fk in general (SumTools[IndefiniteSum][Indefinite]).

• 

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

k=lm1f+k=mnf=k=lnf

• 

The call sum(f, k=alpha) computes the definite sum of fk summed over the roots of a polynomial given by 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 j-fold 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 n-m is a small integer, the sum is computed directly by adding up terms. 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 Newton-Leibniz'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.

  

Note: To access directly one of the above three methods, see Telescoping for (a), CreativeTelescoping for (b), and pFqToStandardFunctions for (c).

d. 

As in the case for indefinite sums, the pattern-match approach is also employed.

• 

For definite sums depending on one or more parameters other than the summation variable, the result will in general be a function of these parameters. However, that result may only be correct in a generic sense; it may not be correct for all possible values of the parameter(s). Use option parametric (see the Options section in this help page) to obtain a complete case discussion that is correct for all possible integer values of the parameter(s).

• 

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 or using the formal option. 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.

• 

The SumTools[IndefiniteSum] package provides an extension mechanism (AddIndefiniteSum) that is used by sum. Using this facility, you can add summation definitions related to additional special functions.

• 

For numerical summation, see evalf/Sum.

Options

• 

If the option parametric is specified for a definite parametric sum, then a result is returned that is valid at least for all possible integer values of the parameter(s) occurring in the summand or the summation bounds. In general, the result is expressed in terms of piecewise functions. The piecewise result may contain FAIL or undefined. Here, FAIL is used to indicate that there is a singularity in the range of summation, and undefined indicates that the sum is divergent.

• 

Using the option formal is equivalent to assigning to the environment variable _EnvFormal (see above): specifying formal=true (or just formal for short) is equivalent to assigning true to _EnvFormal, and formal=false is equivalent to assigning false to _EnvFormal.

Examples

Indefinite sums

Polynomials:

kk2

13k312k2+16k

(1)

Rationals:

kk+k2+512k1k2+512k1k

13k32+12513k12+12513k+12+1254Ψk3+53+5

(2)

Hypergeometric terms:

k4kk4binomial2k,k

16932k163k4140k3+60k2+26k64kbinomial2k,k

(3)

2-fold hypergeometric terms:

kk1k2!

212k!+212k+12!

(4)

Sum of hypergeometric terms:

k22k1k2k+1binomial2k,k+k+124k+1k+2k+3

22k1binomial2k,kk+13k14k+1k+2

(5)

Accurate summation

kΓk+1ΓkΨk

k4k36k26k5Γk+1ΓkΨkk2+k+3k5k410k39k22Γk+2Γk+1Ψk+1kk2+k+3+k+1k35k2+4k2Γk+3Γk+2Ψk+2kk2+k+3

(6)

Additive decomposition of hypergeometric terms:

kk22k12kk+1k2k+3!

112k+3_i=1k12_i+4k+k112k2+2k1_i=1k12_i+4k2

(7)

Sum of a logarithm of a rational function (provided the argument of the logarithm has constant sign):

kln2k+1assuming0k

ln2k+lnΓk+12

(8)

kln2k+1assumingk1

ln2klnΓ12k+Ikπ

(9)

Library extension mechanism:

ksinkcosk+1Ψk

12sin12k+2Ψk+1ksin1+cosk22γsin12Ψksin12sin1ksin1

(10)

Definite sums

Classical telescoping:

kbinomial2n2k,nk24k2k2k+1binomial2k,k1

1224kbinomial2n2k,nk2n+2k1binomial2k,kk2n+1

(11)

k=1nbinomial2n2k,nk24k2k2k+1binomial2k,k1

4binomial2n2,n12n+12n+1

(12)

Creative telescoping:

k=0nbinomial2n,2k2

121n22n+2Γn+122nπ+1422n+522Γ2n+12n12Γ2n+124n121n4nΓn+122πΓn+12Γn+14n1

(13)

Conversion method:

k=0∞22kΓknΓk+nzkπ12Γ2k+1assumingz1

πcos2narcsinzcscπnn

(14)

Pattern match (Abel's type):

k=0n2+kk21+nknkk!nk!

14n+3nn!16n+3n1n1!

(15)

Maple returns the call unevaluated if it cannot find a closed form.

k=0nakxk

k=0nakxk

(16)

If the inert function is used, Maple returns unevaluated.

k=0nkk+1=k=0nkk+1

k=0nkk+1=n+1Ψn+2γ

(17)

kⅇk

ⅇkⅇ11

(18)

k=0∞1k!

ⅇ

(19)

k=1∞1k2

16π2

(20)

k=RootOfx32kk+1

2

(21)

k=1∞k32

∞

(22)

k=1∞1k

k=1∞1k

(23)

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

_EnvFormaltrue

_EnvFormal:=true

(24)

k=1∞k32

ζ32

(25)

k=1∞1k

12

(26)

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

x=11sinxx

1+2sin1

(27)

_EnvFormalfalse

_EnvFormal:=false

(28)

x=11sinxx

Error, (in SumTools:-DefiniteSum:-ClosedForm) summand is singular in the interval of summation

_EnvFormal'_EnvFormal'

_EnvFormal:=_EnvFormal

(29)

Using option formal instead of _EnvFormal has the advantage that the effect is local to the sum command; no "undoing" is necessary.

k=1∞1k

12

(30)

k=1∞1k

k=1∞1k

(31)

Examples for the parametric case

The summand is a hypergeometric term in the summation variable.

F := binomial(2*k-3,k)/4^k;

F:=binomial2k3,k4k

(32)

Sum(F,k=0..n) = sum(F,k=0..n,parametric);

k=0nbinomial2k3,k4k={124nn+1n+2binomial2n1,n+1n1n034n=1124nn+1n+2binomial2n1,n+1n1+382n

(33)

The summand is a rational function in the summation variable.

sum(1/k, k=a..b);

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

k=ab1k

(34)

sum(1/k, k=a..b, parametric);

{0a=b+1Ψb+1Ψa1aand0bΨbΨ1aa0andb1FAILotherwise

(35)

The summand is a hypergeometric term in two variables.

Sum((-1)^k*binomial(n, k)*k, k=0..n) = sum((-1)^k*binomial(n, k)*k, k=0..n, parametric);

k=0n1kbinomialn,kk={0n01n=102n

(36)
  

Without option parametric, the generic answer 0 is returned.

sum((-1)^k*binomial(n, k)*k, k = 0 .. n);

0

(37)
  

In general, the piecewise expression returned may contain an unevaluated, inert Sum.

s := sum((-1)^k*binomial(n, k)*k^3, k=0..n, parametric);

s:={0n0k=0n1kbinomialn,kk31nandn304n

(38)
  

Use the value command in order to evaluate the piecewise result at a point.

eval(s, n=2);

k=021kbinomial2,kk3

(39)

value((39));

6

(40)

Special sums.

Sum(q^n, n=1..infinity) = sum(q^n, n=1..infinity, parametric);

n&equals;1&infin;qn&equals;&lcub;qq1q<1&infin;1qundefinedotherwise

(41)

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.

sum(x^k,k=1..10000);

x10001x1xx1

(42)

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

whattype(f);

`+`

(43)

nops(f);

10000

(44)

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

sum(x^k,k=1..10);

x10&plus;x9&plus;x8&plus;x7&plus;x6&plus;x5&plus;x4&plus;x3&plus;x2&plus;x

(45)

add(x^k,k=1..10);

x10&plus;x9&plus;x8&plus;x7&plus;x6&plus;x5&plus;x4&plus;x3&plus;x2&plus;x

(46)

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:

powersum(1,5);

363

(47)

poweradd(1,5);

363

(48)

powersum(1,n);

123n&plus;132

(49)

poweradd(1,n);

Error, (in poweradd) unable to execute add

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

sum(x^k,k=5..1);

x4x3x2

(50)

add(x^k,k=5..1);

0

(51)

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 non-integer.

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

v:=12345

(52)

v[k];

Error, bad index into Vector

add(v[k],k=1..5);

15

(53)

sum(v[k],k=1..5);

Error, bad index into Vector

sum('v[k]',k=1..5);

15

(54)

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.

k := 42;

k:=42

(55)

add(k,k=1..10);

55

(56)

sum(k,k=1..10);

Error, (in sum) summation variable previously assigned, second argument evaluates to 42 = 1 .. 10

sum('k','k'=1..10);

55

(57)

k := 'k':

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.

t := time():

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

0.008

(58)

t := time():

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

0.183

(59)

t := time():

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

1.249

(60)

t := time():

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

0.021

(61)

References

  

Abramov, S.A. "Indefinite Sums of Rational Functions." In Proceedings ISSAC '95, pp. 303-308. 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 CS-2002-32, 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): 521-543.

  

Abramov, S.A., and Petkovsek, M. "Gosper's Algorithm, Accurate Summation, and the discrete Newton-Leibniz formula." Proceedings ISSAC'05, (2005): 5-12.

  

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

  

Abramov, S. A., and Zima, E. V. "D'Alembertian Solutions of Inhomogeneous Equations (differential, difference, and some other)." In Proceedings ISSAC '96, pp. 232-240. 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): 40-42.

  

Koepf, W. "Algorithms for m-Fold Hypergeometric Summation." Journal of Symbolic Computation, (October 1995): 399-417.

  

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. 301-308. 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): 109-131.

  

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

Compatibility

• 

The sum command was updated in Maple 2016.

• 

The formal option was introduced in Maple 2016.

• 

For more information on Maple 2016 changes, see Updates in Maple 2016.

See Also

add

collect

convert/StandardFunctions

evalf/Sum

expand

normal

product

RootOf

sum/numerical

SumTools

SumTools[IndefiniteSum][AddIndefiniteSum]

 


Download Help Document

Was this information helpful?



Please add your Comment (Optional)
E-mail Address (Optional)
What is ? This question helps us to combat spam