SumTools[Hypergeometric] - Maple Programming Help

Online Help

All Products    Maple    MapleSim


Home : Support : Online Help : Mathematics : Discrete Mathematics : Summation and Difference Equations : SumTools : Hypergeometric Subpackage : SumTools/Hypergeometric/SumDecomposition

SumTools[Hypergeometric]

  

SumDecomposition

  

construct the minimal additive decomposition of a hypergeometric term

 

Calling Sequence

Parameters

Options

Description

Examples

References

Calling Sequence

SumDecomposition(T, n, k, newT, opts)

Parameters

T

-

hypergeometric term of n

n

-

name

k

-

(optional) name; the index variable to use in the output

newT

-

(optional) name; will be assigned an equivalent expression for T

opts

-

(optional) equation(s) of the form keyword=value; possible keywords are minimize or maxiterations

Options

• 

The following optional arguments can be used if T is a rational function of n.

• 

minimize=v, where v is either a numeric value between 0 and 1 or one of "numerator", "sum denominator", "combined", "left", "right".

– 

If v="sum denominator", then the degree g of the denominator of T1 will be minimized.

– 

If v="numerator", then the degree e of the numerator of T2 will be minimized.

– 

If v="combined", then then the sum of the degrees g+e will be  minimized.

– 

If v is  a numeric constant between 0 and 1, then the weighted sum of the degrees vg+1ve will be minimized.

  

Note that small values of v may lead to time-consuming search; the option maxiterations (see below) can be used to restrict it.

– 

If v="left", then the remainder of the result will be aligned such that gcddenomT1&comma;denomT2n=n+k|denomT2n=n+k=1 for all integers k<0.

– 

If v="right", then the remainder of the result will be aligned such that gcddenomT1&comma;denomT2n=n+k|denomT2n=n+k=1 for all integers 0k.

• 

maxiterations=integer

  

This option can be used to restrict the number of iterations performed by the command when the option minimize=v is used with a small positive numeric value v. The default value is 10000.

Description

• 

The SumDecomposition(T, n, k) command constructs two hypergeometric terms T1 and T2 such that Tn=T1n+1T1n+T2n and the certificate ET2T2=T2n+1T2n has a rational normal form z&comma;r&comma;s&comma;u&comma;v with v of minimal degree.

• 

The output from SumDecomposition is a list of two elements T1&comma;T2. Both are represented in the form

Tin=Tn0znFnk=n0n1rkskzn0Fn0

  

for some integer 0n0. The form shown above is called a multiplicative decomposition of the hypergeometric term Tn.

• 

If the third optional argument k is not specified, the first unused name in the sequence k,k0,k1,k2,... is used.

• 

If the fourth optional argument newT is specified, it will be assigned an expression in terms of inert Products of the same form as for Ti above that is equivalent to T.

• 

If T is a rational function of n, then T1 and T2 will be rational functions as well, and the denominator of T2 is of smallest possible degree. In that case, T1 and T2 are not unique, however, and you can use the minimize=v option to impose some additional conditions on T1 and T2 (see below).

• 

Note: If you set infolevel[SumDecomposition] to 3, Maple prints diagnostics.

Examples

withSumToolsHypergeometric&colon;

Tn22n12nn&plus;1n2n&plus;3&excl;

Tn22n12nn+1n2n+3!

(1)

Set the infolevel to 3.

infolevelSumDecomposition3&colon;

SumDecompositionT&comma;n&comma;k&comma;&apos;newT&apos;

SumDecomposition:   "calling dterm"
SumDecomposition:   "construct the RCF_1 for the certificate of T"
SumDecomposition:   "construct a regular description of T"
SumDecomposition:   "calling dcert"
SumDecomposition:   "using factorization method"
SumDecomposition:   "construct a regular description of T1"
SumDecomposition:   "construct a regular description of T2"
SumDecomposition:   "T2 is not summable"
SumDecomposition:   "An attempt to control the degree of the numerator"
SumDecomposition:   "construct a triple that regularly describes T2"

n+3k=1n12k+412n&comma;n2+2n1k=1n12k+412n2

(2)

newT

n22n1k=1n12k+412n2n+1

(3)

convertvaluenewT&comma;&apos;factorial&apos;

n22n12nn+1n2n+3!

(4)

Tn32n

Tn32n

(5)

infolevelSumDecomposition0&colon;

SumDecompositionT&comma;n&comma;k

2n312n2+36n522n2&comma;0

(6)

The above result shows that the input hypergeometric term T is summable.

T2925&plus;190n&plus;19n2&plus;606n3&plus;72n5&plus;435n4&plus;3n6n&plus;5n2&plus;12n&plus;37n3&plus;2n1n

T23n6+72n5+435n4+606n3+19n2+190n+925n+5n2+12n+37n3+2n1n

(7)

SumDecompositionT&comma;n

10n1+5n+5n+1+5n+2+5n+3+5n+4&comma;4n22n2+12n+37+5n1+n22n4n3+2

(8)

SumDecompositionT&comma;n&comma;&apos;minimize&apos;&equals;numerator

4n+2n62+12n35+4n2n52+12n23+4n6n42+12n11+4n10n32+12n+1+4n14n22+12n+13+4n18n12+12n+25+5n1+5n+5n+1+5n+2+5n+3+5n+4&comma;4n+2n62+12n35+5n+n22n4n3+2

(9)

SumDecompositionT&comma;n&comma;&apos;minimize&apos;&equals;15

5n1+5n+4+4n18n12+12n+25&comma;4n18n12+12n+25+5n+4+n22n4n3+2

(10)

SumDecompositionT&comma;n&comma;&apos;minimize&apos;&equals;sum denominator

5n1&comma;4n22n2+12n+37+5n+5+n22n4n3+2

(11)

T1n13n2&plus;1n3&plus;nn&plus;12

T1n13n2+1n3+nn+12

(12)

SumDecompositionT&comma;n

n1n21n1&comma;n2+n+3n3

(13)

SumDecompositionT&comma;n&comma;&apos;minimize&apos;&equals;left

2n12n2n13+n1n2&comma;n2n+3n13

(14)

SumDecompositionT&comma;n&comma;&apos;minimize&apos;&equals;right

2n23n31n1&comma;n2+3n+5n+13

(15)

References

  

Abramov, S.A. "Indefinite Sums of Rational Functions." Proceedings ISSAC'95, pp. 303-308. 1995.

  

Abramov, S.A., and Petkovsek, M. "Minimal Decomposition of Indefinite Hypergeometric Sums." Proceedings ISSAC'2001, pp. 7-14. 2001.

  

Abramov, S.A., and Petkovsek, M. "Rational Normal Forms and Minimal Decompositions of Hypergeometric Terms." Journal of Symbolic Computation. Vol. 33 No. 5. (2002): 521-543.

  

Polyakov, S.P. "Symbolic Additive Decomposition of Rational Functions." Programming and Computer Software, Vol. 31 No. 2. (2005): 60-64.

  

Polyakov, S.P. "Indefinite Summation of Rational Functions with Additional Minimization of the Summable Part." Programming and Computer Software 34 No. 2, (2008): 95-100.

See Also

infolevel

SumTools[Hypergeometric]

SumTools[Hypergeometric][Gosper]

SumTools[Hypergeometric][MultiplicativeDecomposition]

SumTools[Hypergeometric][RationalCanonicalForm]