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.

I encountered the following in a paper and do not understand how the error term is being bounded. In what follows, $n$ and $k$ are large integer constants.

$$ \sum_{i=0}^{n-1} \ln\left(1 - \frac{i}{k}\right) = \int_0^n \ln\left(1 - \frac{x}{k}\right) dx \pm e(n,k) $$ where the error term $e(n,k)$ can be bounded by $$ e(n,k) \leq \int_0^n \ln\left(1 - \frac{x}{k}\right) - \ln\left(1 - \frac{x+1}{k}\right) dx $$

share|improve this question

2 Answers 2

up vote 2 down vote accepted

$$0 \le e(n,k) = \int_0^n \left(\ln \left(1 - \dfrac{\lfloor x \rfloor}{k} \right) - \ln \left(1 - \dfrac{x}{k}\right)\right) dx \le \int_0^n \left(\ln \left(1 - \dfrac{ x-1}{k} \right) - \ln \left(1 - \dfrac{x}{k}\right)\right) dx $$ So the inequality is true if $$\ln \left(1 - \dfrac{ x-1}{k} \right) - \ln \left(1 - \dfrac{x}{k}\right) \le \ln \left(1 - \dfrac{x}{k}\right) - \ln \left(1 - \dfrac{x+1}{k} \right)$$ but rearranging and taking exponential of both sides, this becomes $$\left(1 - \dfrac{ x-1}{k}\right)\left(1 - \dfrac{x+1}{k}\right) \le \left( 1 - \dfrac{x}{k}\right)^2$$ and the left side is $\left(1 - \dfrac{x}{k}\right)^2 - \left(\dfrac{1}{k}\right)^2$.

share|improve this answer
    
Not to take credit away from the answer, but isn't this the same as what I have? –  user17762 Jun 25 '12 at 20:40
    
Pretty much, but expressed somewhat more concisely perhaps. –  Robert Israel Jun 26 '12 at 1:07

Note that $\ln \left( 1- \dfrac{x}k \right)$ is a decreasing function of $x$ for all $x < k$. Hence, $$\int_a^{a+1} \ln \left( 1 -\dfrac{x}k \right) dx \leq \ln \left( 1 - \dfrac{a}k\right) \leq \int_{a-1}^{a} \ln \left( 1 -\dfrac{x}k \right) dx $$ Hence, taking $a=0$ to $a=n-1$ and adding them up, we get that $$\int_0^{n} \ln \left( 1 -\dfrac{x}k \right) dx \leq \sum_{a=0}^{n-1}\ln \left( 1 - \dfrac{a}k\right) \leq \int_{-1}^{n-1} \ln \left( 1 -\dfrac{x}k \right) dx$$ Hence, we get that $$0 \leq \underbrace{\sum_{a=0}^{n-1}\ln \left( 1 - \dfrac{a}k\right) - \int_0^{n} \ln \left( 1 -\dfrac{x}k \right) dx}_{e(n,k)} \leq \int_{-1}^{n-1} \ln \left( 1 -\dfrac{x}k \right) dx - \int_0^{n} \ln \left( 1 -\dfrac{x}k \right) dx$$ Hence, we get that $$\vert e(n,k) \vert \leq \int_0^{n} \left( \ln \left( 1 - \dfrac{x-1}k\right) - \ln \left( 1 - \dfrac{x}k\right)\right) dx$$ which is a slightly better bound than what you want. If you want the bound you have mentioned, note that $$\left( \ln \left( 1 - \dfrac{x-1}k\right) - \ln \left( 1 - \dfrac{x}k\right)\right)$$ is an increasing function of $x$ for $x < k+1$. Hence, $$\int_0^{n} \left( \ln \left( 1 - \dfrac{x-1}k\right) - \ln \left( 1 - \dfrac{x}k\right)\right) dx \leq \int_1^{n+1} \left( \ln \left( 1 - \dfrac{x-1}k\right) - \ln \left( 1 - \dfrac{x}k\right)\right) dx\\ = \int_0^{n} \left( \ln \left( 1 - \dfrac{x}k\right) - \ln \left( 1 - \dfrac{x+1}k\right)\right) dx$$ Hence, $$\vert e(n,k) \vert \leq \int_0^{n} \left( \ln \left( 1 - \dfrac{x-1}k\right) - \ln \left( 1 - \dfrac{x}k\right)\right) dx \leq \int_0^{n} \left( \ln \left( 1 - \dfrac{x}k\right) - \ln \left( 1 - \dfrac{x+1}k\right)\right) dx$$

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.