1
$\begingroup$

Wikipedia has a number of equations for approximating a summation. Unfortunately, there are no proofs or references.

For example: $ \sum_{i=1}^n \log(i)^c i^d b^i = \theta(n^d \log(n)^c b^n) $ for non-negative real $b\gt1$, $c$, $d$.

Does anyone know how to prove this, or where I can find a reference that proves it?

  • 0
    $\Theta$ rather than $\theta$2012-10-31

2 Answers 2

2

Obviously \[ \log(n)^cn^d b^n \le \sum_{i=1}^n \log(i)^c i^d b^i \] On the other hand \begin{align*} \sum_{i=1}^n b^i &\le \frac{b^{n+1} - 1}{b-1}\\ &= b^n \cdot \frac{b - \frac 1{b^{n-1}}}{b-1}\\ &\le b^n \cdot \frac b{b-1}\\ \end{align*} So \[\sum_{i=1}^n \log(i)^c i^d b^i\le \log(n)^c n^d\sum_{i=1}^n b^i \le \log(n)^c n^d b^n \cdot \frac b{b-1}. \]

  • 0
    Got my less than and greater than backwards :)2012-10-31
1

It is true if $b > 1$. Let $a_i(n) = \dfrac{\log(n-i)^c (n-i)^d b^{n-i}}{\log(n)^c n^d b^n} = \left(\dfrac{\log(n-i)}{\log(n)}\right)^c \left(1-\dfrac{i}{n}\right)^d b^{-i}$. Then the claim is $ \sum_{i=0}^{n-1} a_i(n) = \Theta(1) \ \text{as}\ n \to \infty$ We have $a_0(n) = 1$, while $\lim_{n \to \infty} a_i(n) = b^{-i}$ for each $i$, with
$0 \le a_i(n) \le b^{-i}$. By the Dominated Convergence Theorem and the fact that $\sum_{i=0}^\infty b^{-i}$ converges, $\lim_{n \to \infty} \sum_{i=0}^{n-1} a_i(n) = \sum_{i=0}^\infty \lim_{n \to \infty} a_i(n) = \sum_{i=0}^\infty b^{-i} = \frac{1}{1-1/b} = \frac{b}{b-1} $