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