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?

  • 1
    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) $$2012-10-31
  • 0
    Also obviously not true for $|b| < 1$.2012-10-31
  • 0
    You're right. I forgot the qualifications in the article. I've updated it to reflect that.2012-10-31
  • 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
    This proves an upper bound, but not the lower bound, right?2012-10-31
  • 1
    The lower bound is in the first line, note that obviously a sum is bounded below by one of its summands.2012-10-31
  • 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} $$