Combinatorial Sums and Finite Differences
Mathematics and Computer Science
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.
Spivey, M.Z. "Combinatorial Sums and Finite Differences." Discrete Mathematics. 307.24 (2007): 3130-3146. Print.