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

DOI:
https://doi.org/10.1090/S0002-9947-06-03994-8

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 \[ \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$.

- Louis Comtet,
*Advanced combinatorics*, Revised and enlarged edition, D. Reidel Publishing Co., Dordrecht, 1974. The art of finite and infinite expansions. MR**0460128** - Randolph P. Flowe and Gary A. Harris,
*A note on generalized Vandermonde determinants*, SIAM J. Matrix Anal. Appl.**14**(1993), no. 4, 1146–1151. MR**1238929**, DOI https://doi.org/10.1137/0614079 - Charles Jordan,
*Calculus of Finite Differences*, Chelsea, New York, 1950. - Curtis Greene, Herbert S. Wilf, CFSum.nb, (Mathematica notebook), http://www.haverford.edu/math/cgreene/cfsum.nb, http://www.math.upenn.edu/~wilf/website/cfsum.nb.
- Donald E. Knuth,
*The art of computer programming*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**0378456** - C. Krattenthaler,
*Advanced determinant calculus*, Sém. Lothar. Combin.**42**(1999), Art. B42q, 67. The Andrews Festschrift (Maratea, 1998). MR**1701596** - Marko Petkovšek, Herbert S. Wilf, and Doron Zeilberger,
*$A=B$*, A K Peters, Ltd., Wellesley, MA, 1996. With a foreword by Donald E. Knuth; With a separately available computer disk. MR**1379802** - John Riordan,
*Generating functions for powers of Fibonacci numbers*, Duke Math. J.**29**(1962), 5–12. MR**132023** - David L. Russell,
*Sums of products of terms from linear recurrence sequences*, Discrete Math.**28**(1979), no. 1, 65–79. MR**542937**, DOI https://doi.org/10.1016/0012-365X%2879%2990186-9 - Doron Zeilberger,
*A holonomic systems approach to special functions identities*, J. Comput. Appl. Math.**32**(1990), no. 3, 321–368. MR**1090884**, DOI https://doi.org/10.1016/0377-0427%2890%2990042-X

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

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