Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

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

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


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


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$.
Similar Articles
Additional Information
  • Curtis Greene
  • Affiliation: Department of Mathematics, Haverford College, Haverford, Pennsylvania 19041-1392
  • Email:
  • Herbert S. Wilf
  • Affiliation: Department of Mathematics, University of Pennsylvania, Philadelphia, Pennsylvania 19104-6395
  • Email:
  • 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
  • © Copyright 2006 American Mathematical Society
  • Journal: Trans. Amer. Math. Soc. 359 (2007), 1161-1189
  • MSC (2000): Primary 05A15, 05A19; Secondary 11B37, 11B39
  • DOI:
  • MathSciNet review: 2262846