Manipulation of Sums

This chapter deals with the calculus of finite sums: After examining some special techniques, we develop the general theory of finite calculus, the discrete analogue of differential calculus. The discrete primitives are the tool that enable to compute finite sums. We examine in detail the case of the sums of powers of consecutive natural numbers: quite surprisingly this leads to the Stirling numbers of second kind. A section is devoted to the inversion formula, a powerful tool in many mathematical fields: we use it here to obtain the discrete analogue of the Taylor expansion, an alternative short proof of both the number of derangements of a sequence and of surjective functions between two finite sets, and, finally, a more general version of the inclusion/exclusion principle.