Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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) $$ –  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

2 Answers 2

up vote 2 down vote accepted

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}. \]

share|improve this answer
    
This proves an upper bound, but not the lower bound, right? –  Mike Izbicki Oct 31 '12 at 23:02
1  
The lower bound is in the first line, note that obviously a sum is bounded below by one of its summands. –  martini Oct 31 '12 at 23:20
    
Got my less than and greater than backwards :) –  Mike Izbicki Oct 31 '12 at 23:26

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.