Concrete Mathematics

Hypergeometric terms

The center stage, in recurrence solving and summations, play hypergeometric terms. Formally these are sequences annihilated by first order linear recurrence operators. In simple words if we are given term \(a(n)\) then it is hypergeometric if its consecutive term ratio is a rational function in \(n\).

To check if a sequence is of this type you can use the is_hypergeometric method which is available in Basic class. Here is simple example involving a polynomial:

>>> from sympy import *
>>> n, k = symbols('n,k')
>>> (n**2 + 1).is_hypergeometric(n)
True

Of course polynomials are hypergeometric but are there any more complicated sequences of this type? Here are some trivial examples:

>>> factorial(n).is_hypergeometric(n)
True
>>> binomial(n, k).is_hypergeometric(n)
True
>>> rf(n, k).is_hypergeometric(n)
True
>>> ff(n, k).is_hypergeometric(n)
True
>>> gamma(n).is_hypergeometric(n)
True
>>> (2**n).is_hypergeometric(n)
True

We see that all species used in summations and other parts of concrete mathematics are hypergeometric. Note also that binomial coefficients and both rising and falling factorials are hypergeometric in both their arguments:

>>> binomial(n, k).is_hypergeometric(k)
True
>>> rf(n, k).is_hypergeometric(k)
True
>>> ff(n, k).is_hypergeometric(k)
True

To say more, all previously shown examples are valid for integer linear arguments:

>>> factorial(2*n).is_hypergeometric(n)
True
>>> binomial(3*n+1, k).is_hypergeometric(n)
True
>>> rf(n+1, k-1).is_hypergeometric(n)
True
>>> ff(n-1, k+1).is_hypergeometric(n)
True
>>> gamma(5*n).is_hypergeometric(n)
True
>>> (2**(n-7)).is_hypergeometric(n)
True

However nonlinear arguments make those sequences fail to be hypergeometric:

>>> factorial(n**2).is_hypergeometric(n)
False
>>> (2**(n**3 + 1)).is_hypergeometric(n)
False

If not only the knowledge of being hypergeometric or not is needed, you can use hypersimp() function. It will try to simplify combinatorial expression and if the term given is hypergeometric it will return a quotient of polynomials of minimal degree. Otherwise is will return \(None\) to say that sequence is not hypergeometric:

>>> hypersimp(factorial(2*n), n)
4*n**2 + 6*n + 2
>>> hypersimp(factorial(n**2), n)

Concrete Class Reference

class sympy.concrete.summations.Sum[source]

Represents unevaluated summation.

euler_maclaurin(m=0, n=0, eps=0, eval_integral=True)[source]

Return an Euler-Maclaurin approximation of self, where m is the number of leading terms to sum directly and n is the number of terms in the tail.

With m = n = 0, this is simply the corresponding integral plus a first-order endpoint correction.

Returns (s, e) where s is the Euler-Maclaurin approximation and e is the estimated error (taken to be the magnitude of the first omitted term in the tail):

>>> from sympy.abc import k, a, b
>>> from sympy import Sum
>>> Sum(1/k, (k, 2, 5)).doit().evalf()
1.28333333333333
>>> s, e = Sum(1/k, (k, 2, 5)).euler_maclaurin()
>>> s
-log(2) + 7/20 + log(5)
>>> from sympy import sstr
>>> print sstr((s.evalf(), e.evalf()), full_prec=True)
(1.26629073187415, 0.0175000000000000)

The endpoints may be symbolic:

>>> s, e = Sum(1/k, (k, a, b)).euler_maclaurin()
>>> s
-log(a) + log(b) + 1/(2*b) + 1/(2*a)
>>> e
Abs(-1/(12*b**2) + 1/(12*a**2))

If the function is a polynomial of degree at most 2n+1, the Euler-Maclaurin formula becomes exact (and e = 0 is returned):

>>> Sum(k, (k, 2, b)).euler_maclaurin()
(b**2/2 + b/2 - 1, 0)
>>> Sum(k, (k, 2, b)).doit()
b**2/2 + b/2 - 1

With a nonzero eps specified, the summation is ended as soon as the remainder term is less than the epsilon.

free_symbols[source]

This method returns the symbols that will exist when the summation is evaluated. This is useful if one is trying to determine whether a sum depends on a certain symbol or not.

>>> from sympy import Sum
>>> from sympy.abc import x, y
>>> Sum(x, (x, y, 1)).free_symbols
set([y])
is_number[source]

Return True if the Sum will result in a number, else False.

sympy considers anything that will result in a number to have is_number == True.

>>> from sympy import log
>>> log(2).is_number
True

Sums are a special case since they contain symbols that can be replaced with numbers. Whether the integral can be done or not is another issue. But answering whether the final result is a number is not difficult.

>>> from sympy import Sum
>>> from sympy.abc import x, y
>>> Sum(x, (y, 1, x)).is_number
False
>>> Sum(1, (y, 1, x)).is_number
False
>>> Sum(0, (y, 1, x)).is_number
True
>>> Sum(x, (y, 1, 2)).is_number
False
>>> Sum(x, (y, 1, 1)).is_number
False
>>> Sum(x, (x, 1, 2)).is_number
True
>>> Sum(x*y, (x, 1, 2), (y, 1, 3)).is_number
True
is_zero[source]

A Sum is only zero if its function is zero or if all terms cancel out. This only answers whether the summand zero.

variables[source]

Return a list of the summation variables

>>> from sympy import Sum
>>> from sympy.abc import x, i
>>> Sum(x**i, (i, 1, 3)).variables
[i]
class sympy.concrete.products.Product[source]

Represents unevaluated product.

free_symbols[source]

This method returns the symbols that will affect the value of the Product when evaluated. This is useful if one is trying to determine whether a product depends on a certain symbol or not.

>>> from sympy import Product
>>> from sympy.abc import x, y
>>> Product(x, (x, y, 1)).free_symbols
set([y])
is_number[source]

Return True if the Product will result in a number, else False.

sympy considers anything that will result in a number to have is_number == True.

>>> from sympy import log, Product
>>> from sympy.abc import x, y, z
>>> log(2).is_number
True
>>> Product(x, (x, 1, 2)).is_number
True
>>> Product(y, (x, 1, 2)).is_number
False
>>> Product(1, (x, y, z)).is_number
True
>>> Product(2, (x, y, z)).is_number
False
is_zero[source]

A Product is zero only if its term is zero.

variables[source]

Return a list of the product variables

>>> from sympy import Product
>>> from sympy.abc import x, i
>>> Product(x**i, (i, 1, 3)).variables
[i]

Concrete Functions Reference

sympy.concrete.summations.summation(f, *symbols, **kwargs)[source]

Compute the summation of f with respect to symbols.

The notation for symbols is similar to the notation used in Integral. summation(f, (i, a, b)) computes the sum of f with respect to i from a to b, i.e.,

                            b
                          ____
                          \   `
summation(f, (i, a, b)) =  )    f
                          /___,
                          i = a

If it cannot compute the sum, it returns an unevaluated Sum object. Repeated sums can be computed by introducing additional symbols tuples:

>>> from sympy import summation, oo, symbols, log
>>> i, n, m = symbols('i n m', integer=True)
>>> summation(2*i - 1, (i, 1, n))
n**2
>>> summation(1/2**i, (i, 0, oo))
2
>>> summation(1/log(n)**n, (n, 2, oo))
Sum(log(n)**(-n), (n, 2, oo))
>>> summation(i, (i, 0, n), (n, 0, m))
m**3/6 + m**2/2 + m/3
>>> from sympy.abc import x
>>> from sympy import factorial
>>> summation(x**n/factorial(n), (n, 0, oo))
exp(x)
sympy.concrete.products.product(*args, **kwargs)[source]

Compute the product.

The notation for symbols is similiar to the notation used in Sum or Integral. product(f, (i, a, b)) computes the product of f with respect to i from a to b, i.e.,

                             b
                           _____
product(f(n), (i, a, b)) = |   | f(n)
                           |   |
                           i = a

If it cannot compute the product, it returns an unevaluated Product object. Repeated products can be computed by introducing additional symbols tuples:

>>> from sympy import product, symbols
>>> i, n, m, k = symbols('i n m k', integer=True)
>>> product(i, (i, 1, k))
k!
>>> product(m, (i, 1, k))
m**k
>>> product(i, (i, 1, k), (k, 1, n))
Product(k!, (k, 1, n))
sympy.concrete.gosper.gosper_normal(f, g, n, polys=True)[source]

Compute the Gosper’s normal form of f and g.

Given relatively prime univariate polynomials f and g, rewrite their quotient to a normal form defined as follows:

\[\frac{f(n)}{g(n)} = Z \cdot \frac{A(n) C(n+1)}{B(n) C(n)}\]

where Z is an arbitrary constant and A, B, C are monic polynomials in n with the following properties:

  1. \(\gcd(A(n), B(n+h)) = 1 \forall h \in \mathbb{N}\)
  2. \(\gcd(B(n), C(n+1)) = 1\)
  3. \(\gcd(A(n), C(n)) = 1\)

This normal form, or rational factorization in other words, is a crucial step in Gosper’s algorithm and in solving of difference equations. It can be also used to decide if two hypergeometric terms are similar or not.

This procedure will return a tuple containing elements of this factorization in the form (Z*A, B, C).

Examples

>>> from sympy.concrete.gosper import gosper_normal
>>> from sympy.abc import n
>>> gosper_normal(4*n+5, 2*(4*n+1)*(2*n+3), n, polys=False)
(1/4, n + 3/2, n + 1/4)
sympy.concrete.gosper.gosper_term(f, n)[source]

Compute Gosper’s hypergeometric term for f.

Suppose f is a hypergeometric term such that:

\[s_n = \sum_{k=0}^{n-1} f_k\]

and \(f_k\) doesn’t depend on \(n\). Returns a hypergeometric term \(g_n\) such that \(g_{n+1} - g_n = f_n\).

Examples

>>> from sympy.concrete.gosper import gosper_term
>>> from sympy.functions import factorial
>>> from sympy.abc import n
>>> gosper_term((4*n + 1)*factorial(n)/factorial(2*n + 1), n)
(-n - 1/2)/(n + 1/4)
sympy.concrete.gosper.gosper_sum(f, k)[source]

Gosper’s hypergeometric summation algorithm.

Given a hypergeometric term f such that:

\[s_n = \sum_{k=0}^{n-1} f_k\]

and \(f(n)\) doesn’t depend on \(n\), returns \(g_{n} - g(0)\) where \(g_{n+1} - g_n = f_n\), or None if \(s_n\) can not be expressed in closed form as a sum of hypergeometric terms.

References

[R12]Marko Petkovsek, Herbert S. Wilf, Doron Zeilberger, A = B, AK Peters, Ltd., Wellesley, MA, USA, 1997, pp. 73–100

Examples

>>> from sympy.concrete.gosper import gosper_sum
>>> from sympy.functions import factorial
>>> from sympy.abc import i, n, k
>>> f = (4*k + 1)*factorial(k)/factorial(2*k + 1)
>>> gosper_sum(f, (k, 0, n))
(-n! + 2*(2*n + 1)!)/(2*n + 1)!
>>> _.subs(n, 2) == sum(f.subs(k, i) for i in [0, 1, 2])
True
>>> gosper_sum(f, (k, 3, n))
(-60*n! + (2*n + 1)!)/(60*(2*n + 1)!)
>>> _.subs(n, 5) == sum(f.subs(k, i) for i in [3, 4, 5])
True

Table Of Contents

Previous topic

Number Theory

Next topic

Numerical evaluation

This Page