Combinatorial sums and finite differences

We present a new approach to evaluating combinatorial sums by using finite differences. Let {ak}k=0∞ and {bk}k=0∞ be sequences with the property that Δbk=akΔbk=ak for k⩾0k⩾0. Let gn=∑k=0nnkak, and let hn=∑k=0nnkbk. We derive expressions for gngn in terms of hnhn and for hnhn in terms of gngn. We then extend our approach to handle binomial sums of the form ∑k=0nnk(-1)kak, ∑kn2kak, and ∑kn2k+1ak, as well as sums involving unsigned and signed Stirling numbers of the first kind, ∑k=0nnkak and ∑k=0ns(n,k)ak. For each type of sum we illustrate our methods by deriving an expression for the power sum, with ak=kmak=km, and the harmonic number sum, with ak=Hk=1+1/2+⋯+1/kak=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.