## `sum` -- definite and indefinite summation

#### Introduction

`sum(`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))`

#### Parameters

`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`

#### Returns

an arithmetical expression.

#### Related Functions

`_plus`, `+`, `int`, `numeric::sum`, `product`, `rec`

#### Details

- `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.

- The system returns a symbolic call of `sum` if it cannot compute a closed form representation of the sum.
- Infinite symbolic sums without symbolic parameters can be evaluated numerically via `float` or `numeric::sum`. Cf. example 4.

#### Example 1

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

#### Example 2

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

#### Example 3

`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

#### Example 4

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

#### Example 5

`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)

             \ \
             | |
             | |
             | |
             / /

#### Background

- The function `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.

#### Changes

- no changes

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000