Closed form summation of $C$-finite sequences
HTML articles powered by AMS MathViewer
- by Curtis Greene and Herbert S. Wilf PDF
- Trans. Amer. Math. Soc. 359 (2007), 1161-1189 Request permission
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$.References
- Louis Comtet, Advanced combinatorics, Revised and enlarged edition, D. Reidel Publishing Co., Dordrecht, 1974. The art of finite and infinite expansions. MR 0460128, DOI 10.1007/978-94-010-2196-8
- 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 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 Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms. 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 10.1016/0012-365X(79)90186-9
- Doron Zeilberger, A holonomic systems approach to special functions identities, J. Comput. Appl. Math. 32 (1990), no. 3, 321–368. MR 1090884, DOI 10.1016/0377-0427(90)90042-X
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
- Received by editor(s): May 20, 2004
- Received by editor(s) in revised form: December 9, 2004
- Published electronically: September 12, 2006
- © Copyright 2006 American Mathematical Society
- 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
- MathSciNet review: 2262846
Dedicated: To David Robbins