Browse Reports

While analyzing the average performance of an algorithm for a geometric problem, the summation $ \sum_{k=1}^{n} k ^ m / 2 ^ k $ was encountered. This sum is a particular case of the sum $ S_{m,n} = \sum_{k=1}^n ~ \alpha ^ k ~ k ^ m $ for $ 0 ~>~ \alpha ~>~ 1$. Solving $S_{m,n}$ requires a variety of techniques and is an interesting case study in the analysis of algorithms. This paper examines both the solution of this summation and the methods used to obtain the solution. Three approaches to solving $S_{m,n}$ are examined. It is found that $S_{m,n}$ is defined by \[ S_{m,n} ~=~ C_m ~-~ D_{m,n} \] where $C_m$ is a function of $\alpha$ and $m$ and $D_{m,n}$ is the product of $\alpha^ n$ with a polynomial in $n$ of degree $m$. Both functions are defined recursively. Several techniques used in the analysis of algorithm are applied to evaluate these recurrences. Induction is used to prove results obtained by examing small cases. Generating function methods are employed to derive expressions defining $C_m$ and $D_{m,n}$. Asymptotics are found for $C_m$, $D_{m,n}$, and $S_{m,n}$. Integration is used to find a good asymptotic expression for $C_m$. Complex analysis techniques are employed to find an asymptotic for $D_{m,n}$. Asymptotics for $S_{m,n}$ are found by studyinge sum in the region about the value of $k$ that maximizes $k^ m alpha^k$.