A note on alternating sums (Q1918882)

In this paper alternating sums of the type \(\sum^N_{k= a} (\begin{smallmatrix} N\\ k\end{smallmatrix}) (- 1)^k f(k)\), \(a\) being a natural number satisfying \(0\leq a\leq N\), are considered. For the case \(a= 0\) the above expression is an \(N\)th order difference of the sequence \((f(n))\). \textit{S. O. Rice} and \textit{D. E. Knuth} (see [The art of computer programming. Vol. 3: Sorting and searching (1974; Zbl 0302.68010)]) presented a method for treating such sums by using complex contour integration, whereas here manipulations of generating functions are used to obtain explicit results from which asymptotic estimates are easily derived. Finally the results obtained here are applied to concrete examples from the average case analysis of an algorithm called ``Approximate Counting'' and from the analysis of the path length in digital search trees.