sum
-- definite and indefinite
summationsum(
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).
sum(f, i)
sum(f, i = a..b)
sum(f, i = RootOf(p, x))
f |
- | 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 |
_plus
, +
, int
, numeric::sum
, product
, rec
sum
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.We 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
We 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
sum
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
The 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
sum
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) \ \ | | | | | | / /
sum
implements Abramov's algorithm for
rational expressions, Gosper's algorithm for hypergeometric
expressions, and Zeilberger's algorithm for the definite summation of
holonomic expressions.