# Can someone prove (or reference) this summation equation from wikipedia?

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?

-
What you have written is not true for $b=1$ since $$\sum_{i=1}^n \log(i)^c i^d = \theta(n^{d+1} \log(n)^c)$$ – user17762 Oct 31 '12 at 22:30
Also obviously not true for $|b| < 1$. – Robert Israel Oct 31 '12 at 22:37
You're right. I forgot the qualifications in the article. I've updated it to reflect that. – Mike Izbicki Oct 31 '12 at 22:39
$\Theta$ rather than $\theta$ – Henry Oct 31 '12 at 22:46

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}.$
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}$$