A note on alternating sums
type: Item
instance of: scholarly article
title: A note on alternating sums
zbMATH Open document ID: 0855.05009
published in: The Electronic Journal of Combinatorics
publication date: 1996-07-21T00:00:00Z
full work available at URL: https://eudml.org/doc/119009
full work available at URL: R7
review text: 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.
Mathematics Subject Classification ID: 05A16
zbMATH DE Number: 907646
zbMATH Keywords: alternating sums
zbMATH Keywords: generating functions
zbMATH Keywords: asymptotic estimates
zbMATH Keywords: average case analysis
zbMATH Keywords: path length
zbMATH Keywords: search trees
author: Peter Kirschenhofer
reviewed by: D. V. Chopra
MaRDI profile type: Publication
Recommended article: Almost Alternating Sums
Recommended article: On the sum of some alternating series
Recommended article: Q5094083
Recommended article: Q4684600
Recommended article: A note for alternating Ramanujan's circular summation formula
Recommended article: A NOTE ON THE SUM OF RECIPROCALS
Recommended article: A note on sums of a class of series
Recommended article: Q5060327
description: scientific article; zbMATH DE number 907646