skip to main content
10.1145/1005285.1005326acmconferencesArticle/Chapter ViewAbstractPublication PagesissacConference Proceedingsconference-collections
Article

Symbolic summation with single-nested sum extensions

Published: 04 July 2004 Publication History

Abstract

We present a streamlined and refined version of Karr's summation algorithm. Karr's original approach constructively decides the telescoping problem in ΠΣ-fields, a very general class of difference fields that can describe rational terms of arbitrarily nested indefinite sums and products. More generally, our new algorithm can decide constructively if there exists a so called single-nested ΠΣ-extension over a given ΠΣ-field in which the telescoping problem for f can be solved in terms that are not more nested than f itself. This allows to eliminate an indefinite sum over f by expressing it in terms of additional sums that are not more nested than f. Moreover, our refined algorithm contributes to definite summation: it can decide constructively if the creative telescoping problem for a fixed order can be solved in single-nested Σ*-extensions that are less nested than the definite sum itself.

References

[1]
S. A. Abramov and M. Petkovsek. D'Alembertian solutions of linear differential and difference equations. In J. von zur Gathen, editor, Proc. ISSAC'94, pages 169--174. ACM Press, Baltimore, 1994.
[2]
M. Bronstein. On solutions of linear ordinary difference equations in their coefficient field. J. Symbolic Comput., 29(6):841--877, June 2000.
[3]
R. M. Cohn. Difference Algebra. Interscience Publishers, John Wiley & Sons, 1965.
[4]
K. Driver, H. Prodinger, C. Schneider, and A. Weideman. Pad'e approximations to the logarithm III: Alternative methods and additional results. To Appear in Ramanujan Journal, 2004.
[5]
P. A. Hendriks and M. F. Singer. Solving difference equations in finite terms. J. Symbolic Comput., 27(3):239--259, 1999.
[6]
M. Karr. Summation in finite terms. J. ACM, 28:305--350, 1981.
[7]
M. Karr. Theory of summation in finite terms. J. Symbolic Comput., 1:303--315, 1985.
[8]
P. Paule and C. Schneider. Computer proofs of a new family of harmonic number identities. Adv. in Appl. Math., 31(2):359--378, 2003.
[9]
C. Schneider. Symbolic summation in difference fields. Technical Report 01-17, RISC-Linz, J. Kepler University, November 2001. PhD Thesis.
[10]
C. Schneider. A collection of denominator bounds to solve parameterized linear difference equations in ΠΣ-fields. SFB-Report 02-20, J. Kepler University, Linz, November 2002. Submitted.
[11]
C. Schneider. Degree bounds to find polynomial solutions of parameterized linear difference equations in ΠΣ-fields. SFB-Report 02-21, J. Kepler University, Linz, November 2002. Submitted.
[12]
C. Schneider. Solving parameterized linear difference equations in ΠΣ-fields. SFB-Report 02-19, J. Kepler University, Linz, November 2002. Submitted.
[13]
C. Schneider. Product representations in ΠΣ-fields. Technical Report 02-24, RISC-Linz, J. Kepler University, 2003. Submitted.
[14]
C. Schneider. Symbolic summation with single-nested sum extensions (extended version). SFB-Report 2004-7, J. Kepler University, Linz, 2004.
[15]
D. Zeilberger. A fast algorithm for proving terminating hypergeometric identities. Discrete Math., 80(2):207--211, 1990.

Cited By

View all

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ISSAC '04: Proceedings of the 2004 international symposium on Symbolic and algebraic computation
July 2004
334 pages
ISBN:158113827X
DOI:10.1145/1005285
  • General Chair:
  • Josef Schicho
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 July 2004

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. creative telescoping
  2. difference field extensions
  3. telescoping

Qualifiers

  • Article

Conference

ISSAC04
Sponsor:

Acceptance Rates

Overall Acceptance Rate 395 of 838 submissions, 47%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)8
  • Downloads (Last 6 weeks)2
Reflects downloads up to 17 Feb 2025

Other Metrics

Citations

Cited By

View all

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media