Title

Combinatorial Sums and Finite Differences

Document Type

Article

Publication Date

2007

Publication Title

Discrete Mathematics

Department

Mathematics and Computer Science

Abstract

We present a new approach to evaluating combinatorial sums by using finite differences. Let and be sequences with the property that ?bk=ak for k?0. Let , and let . We derive expressions for gn in terms of hn and for hn in terms of gn. We then extend our approach to handle binomial sums of the form , , and , as well as sums involving unsigned and signed Stirling numbers of the first kind, and . For each type of sum we illustrate our methods by deriving an expression for the power sum, with ak=km, and the harmonic number sum, with ak=Hk=1+1/2+?+1/k. Then we generalize our approach to a class of numbers satisfying a particular type of recurrence relation. This class includes the binomial coefficients and the unsigned Stirling numbers of the first kind.

Volume

307

Issue

24

pp.

3130-3146

ISSN

0012-365X