Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 

 

Closed form summation of $ C$-finite sequences


Authors: Curtis Greene and Herbert S. Wilf
Journal: Trans. Amer. Math. Soc. 359 (2007), 1161-1189
MSC (2000): Primary 05A15, 05A19; Secondary 11B37, 11B39
Published electronically: September 12, 2006
MathSciNet review: 2262846
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We consider sums of the form

$\displaystyle \sum_{j=0}^{n-1}F_1(a_1n+b_1j+c_1)F_2(a_2n+b_2j+c_2)\dots F_k(a_kn+b_kj+c_k),$

in which each $ \{F_i(n)\}$ is a sequence that satisfies a linear recurrence of degree $ D(i)<\infty$, with constant coefficients. We assume further that the $ a_i$'s and the $ a_i+b_i$'s are all nonnegative integers. We prove that such a sum always has a closed form, in the sense that it evaluates to a linear combination of a finite set of monomials in the values of the sequences $ \{F_i(n)\}$ with coefficients that are polynomials in $ n$. We explicitly describe two different sets of monomials that will form such a linear combination, and give an algorithm for finding these closed forms, thereby completely automating the solution of this class of summation problems. We exhibit tools for determining when these explicit evaluations are unique of their type, and prove that in a number of interesting cases they are indeed unique. We also discuss some special features of the case of ``indefinite summation", in which $ a_1=a_2=\cdots = a_k = 0$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05A15, 05A19, 11B37, 11B39

Retrieve articles in all journals with MSC (2000): 05A15, 05A19, 11B37, 11B39


Additional Information

Curtis Greene
Affiliation: Department of Mathematics, Haverford College, Haverford, Pennsylvania 19041-1392
Email: cgreene@haverford.edu

Herbert S. Wilf
Affiliation: Department of Mathematics, University of Pennsylvania, Philadelphia, Pennsylvania 19104-6395
Email: wilf@math.upenn.edu

DOI: http://dx.doi.org/10.1090/S0002-9947-06-03994-8
Keywords: Summation, closed form, $C$-finite, recurrences
Received by editor(s): May 20, 2004
Received by editor(s) in revised form: December 9, 2004
Published electronically: September 12, 2006
Dedicated: To David Robbins
Article copyright: © Copyright 2006 American Mathematical Society