3
$\begingroup$

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

2 Answers 2

2

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

  • 0
    Not to take credit away from the answer, but isn't this the same as what I have?2012-06-25
  • 0
    Pretty much, but expressed somewhat more concisely perhaps.2012-06-26
2

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