sum -- definite and indefinite
summation
Introductionsum(f, i) computes a symbolic
antidifference of f(i) with respect to i.
sum(f, i = a..b) tries to find a closed
form representation of the sum sum(f(i),i=a..b).
Call(s)sum(f, i)
sum(f, i = a..b)
sum(f, i = RootOf(p, x))
Parametersf |
- | an arithmetical expression
depending on i |
i |
- | the summation index: an identifier |
a, b |
- | the boundaries: arithmetical expressions |
p |
- | a polynomial of type
DOM_POLY or a polynomial expression |
x |
- | an indeterminate of p |
Returns
Related
Functions_plus, +, int, numeric::sum, product, rec
Detailssum serves for simplifying symbolic sums (the
discrete analog of integration). It should not be used for
adding a finite number of terms: if a and b
are integers of type DOM_INT, the call _plus(f $ i = a..b) is more efficient
than sum(f, i = a..b). See example 3.sum(f, i) computes the indefinite sum of
f with respect to i. This is an expression
g such that f(i) = g(i + 1) - g(i).sum(f, i = a..b) computes the definite
sum with i running from a to b.
If b - a is a nonnegative integer, then the explicit
sum f(a) + f(a + 1) + .. + f(b) is returned.
If b - a is a negative integer, then the negative of
the result of sum(f, i = b+1..a-1) is
returned. With this convention, the rule
sum(f, i = a..b) + sum(f, i = b+1..c) = sum(f, i =
a..c)
is satisfied for any a, b, and
c.
sum(f, i = RootOf(p, x)) computes the sum
with i extending over all roots of the polynomial
p with respect to x.
If f is a rational function of i, a closed
form of the sum will be found.
See example 2.
sum if it cannot
compute a closed form representation of the sum.float or
numeric::sum. Cf.
example 4.
Example
1We compute some indefinite sums:
>> sum(1/(i^2 - 1), i)
1 1
- --- - ---------
2 i 2 (i - 1)
>> sum(1/i/(i + 2)^2, i)
psi(i + 2, 1) 1 1
------------- - --- - -------
2 4 i 4 i + 4
>> sum(binomial(n + i, i), i)
i binomial(i + n, i)
--------------------
n + 1
>> sum(binomial(n, i)/2^n - binomial(n + 1, i)/2^(n + 1), i)
2 i binomial(n, i) - i binomial(n + 1, i)
-----------------------------------------
n n n
2 2 - 4 i 2 + 2 n 2
We compute some definite sums. Note that +-infinity are valid boundaries:
>> sum(1/(i^2 + 21*i), i = 1..infinity)
18858053/108636528
>> sum(1/i, i = a .. a + 3)
1 1 1 1
- + ----- + ----- + -----
a a + 1 a + 2 a + 3
Example
2We compute some sums over all roots of a polynomial:
>> sum(i^2, i = RootOf(x^3 + a*x^2 + b*x + c, x))
2
a - 2 b
>> sum(1/(z + i), i = RootOf(x^4 - y*x + 1, x))
3
y + 4 z
------------
4
y z + z + 1
Example
3sum can compute finite sums with integer
boundaries of type DOM_INT:
>> sum(1/(i^2 + i), i = 1..100)
100/101
>> sum(binomial(n, i), i = 0..4)
n + binomial(n, 2) + binomial(n, 3) + binomial(n, 4) + 1
>> expand(%)
2 3 4
7 n 11 n n n
--- + ----- - -- + -- + 1
12 24 12 24
However, it is usually more efficient to use _plus in such a case:
>> _plus(1/(i^2 + i) $ i = 1..100)
100/101
>> _plus(binomial(n, i) $ i = 0..4)
n + binomial(n, 2) + binomial(n, 3) + binomial(n, 4) + 1
However, if one of the boundaries is symbolic, then
_plus cannot be
used:
>> _plus(1/(i^2 + i) $ i = 1..n)
Error: Illegal argument [_seqgen]
>> _plus(binomial(n, i) $ i = 0..n)
Error: Illegal argument [_seqgen]
>> sum(1/(i^2 + i), i = 1..n), sum(binomial(n, i), i = 0..n)
n n
-----, 2
n + 1
Example
4The following infinite sum cannot be computed symbolically:
>> sum(ln(i)/i^5, i = 1..infinity)
/ ln(i) \
sum| -----, i = 1..infinity |
| 5 |
\ i /
We obtain a floating point approximation via float:
>> float(%)
0.0285737805
Alternatively, the function numeric::sum can be used directly. This
is usually much faster than applying float, since it avoids the overhead of
sum attempting to compute a symbolic representation:
>> numeric::sum(ln(i)/i^5, i = 1..infinity)
0.0285737805
Example
5sum does not find a closed form for the
following definite sum. It returns a recurrence formula (see rec) for the sum instead:
>> sum(binomial(n, i)^3, i = 0..n)
/ / 2
| | 8 u2(n) (n + 1)
solve| rec| u2(n + 2) - ---------------- -
| | 2
\ \ (n + 2)
2
u2(n + 1) (21 n + 7 n + 16)
----------------------------, u2(n), {u2(0) = 1, u2(1) = 2}
2
(n + 2)
\ \
| |
| |
| |
/ /
Backgroundsum implements Abramov's algorithm for
rational expressions, Gosper's algorithm for hypergeometric
expressions, and Zeilberger's algorithm for the definite summation of
holonomic expressions.