# Evaluate $\lim_{n \to \infty}\sum_{k= 1}^n (1 + k/n) \left ( \log ( 1 + k/n) - \log (1 + (k-1)/n)\right)$

I got the sum $$\lim_{n \to \infty }\sum_{k= 1}^n (1 + k/n) \left ( \log ( 1 + k/n) - \log (1 + (k-1)/n)\right)$$ while trying to evaluate the integral $\int_0^{\ln 2} e^x dx$ while partitioning the range. How do I evaluate the sum? or alternatively how do I evaluate $\int_0^{\ln 2} e^x dx$ using Lebesgue integral by partitioning the range?

• I really don't understand how you got a sum of logs to evaluate an integral of exponential, but anyway: these problems are usually designed to do the other way around, meaning: one uses the integral to evaluate a series, not what you want...if I understood correctly. – DonAntonio Mar 12 '17 at 22:52
• Presumably, OP took $x_k=\log(1+k/n)$ and then he gets $\sum_{k=1}^{n} e^{x_k}(x_{k}-x_{k-1})$, @DonAntonio – Thomas Andrews Mar 12 '17 at 22:57
• @ThomasAndrews Thanks, that seems a reasonable assumption. – DonAntonio Mar 13 '17 at 8:17

Lemma: For $0\le u,$

$$u-u^2/2 \le \ln (1+u) \le u.$$

You can prove this by noting it holds for $u=0,$ and then showing that the inequality holds for the derivatives.

Now the given sum equals

$$(1+1/n)\ln(1+1/n) + \sum_{k=2}^{n}(1 + k/n) [\ln (1+k/n)-\ln (1+(k-1)/n].$$

Note $(1+1/n)\ln(1+1/n) \to 0,$ so we can forget about this term. We can write the remaining sum as

$$\sum_{k=2}^{n}(1 + k/n) \ln \left (\frac{1+k/n}{1+(k-1)/n}\right ) = \sum_{k=2}^{n}(1 + k/n) \ln \left (1+\frac{1/n}{1+(k-1)/n}\right ).$$

By the lemma, the last sum is bounded above by

$$\sum_{k=2}^{n}(1 + k/n) \frac {1/n}{1+(k-1)/n}$$ $$\tag 1= \sum_{k=2}^{n}(1 + (k-1)/n)\frac {1/n}{1+(k-1)/n} + \sum_{k=2}^{n}\frac {1/n^2}{1+(k-1)/n}.$$

The first sum in $(1)$ equals $(n-1)/n \to 1.$ The second sum $\to 0.$

We have shown that our sum is bounded above by an expression that $\to 1.$ Similarly we can use the lemma to bound our sum from below with an expression that also $\to 1.$ By the squeeze theorem, the desired limit is $1.$

We have in fact that $$\begin{gathered} \sum\limits_{1\, \leqslant \,k\, \leqslant \,n} {\left( {1 + k/n} \right)\left( {\ln \left( {1 + k/n} \right) - \ln \left( {1 + \left( {k - 1} \right)/n} \right)} \right)} = \hfill \\ = \ln \prod\limits_{1\, \leqslant \,k\, \leqslant \,n} {\left( {\frac{{n + k}} {{n + k - 1}}} \right)^{\left( {1 + k/n} \right)} } = \hfill \\ = \ln \left( {\left( {\frac{{\prod\limits_{1\, \leqslant \,k\, \leqslant \,n} {\left( {n + k} \right)^{n + k} } }} {{\prod\limits_{1\, \leqslant \,k\, \leqslant \,n} {\left( {n + k - 1} \right)} \prod\limits_{1\, \leqslant \,k\, \leqslant \,n} {\left( {n + k - 1} \right)^{n + k - 1} } }}} \right)^{1/n} } \right) = \hfill \\ = \ln \left( {\left( {\frac{{\prod\limits_{1\, \leqslant \,k\, \leqslant \,n} {\left( {n + k} \right)^{n + k} } }} {{\prod\limits_{0\, \leqslant \,k\, \leqslant \,n - 1} {\left( {n + k} \right)} \prod\limits_{0\, \leqslant \,k\, \leqslant \,n - 1} {\left( {n + k} \right)^{n + k} } }}} \right)^{1/n} } \right) = \hfill \\ = \ln \left( {\left( {\frac{{\left( {2n} \right)^{2n} }} {{n^n \prod\limits_{0\, \leqslant \,k\, \leqslant \,n - 1} {\left( {n + k} \right)} }}} \right)^{1/n} } \right) = \ln \left( {\frac{{\left( {2n} \right)^2 }} {{n\left( {n^{\,\overline {\,n\,} } } \right)^{1/n} }}} \right) = \ln \left( {\frac{{4n}} {{\left( {\Gamma (2n)/\Gamma (n)} \right)^{1/n} }}} \right) = \hfill \\ = \ln \left( {\frac{{4n}} {{\left( {\frac{{2^{2n - 1} }} {{\sqrt \pi }}\Gamma (n + 1/2)} \right)^{1/n} }}} \right) = \ln \left( {\frac{{4n}} {{4\left( {\frac{1} {{2\sqrt \pi }}\Gamma (n + 1/2)} \right)^{1/n} }}} \right) = \hfill \\ \mathop \propto \limits_{n\, \to \,\infty } \ln \left( {\frac{n} {{\left( {\frac{1} {{2\sqrt \pi }}\sqrt {\frac{{2\pi }} {{n + 1/2}}} \left( {\frac{{n + 1/2}} {e}} \right)^{n + 1/2} } \right)^{1/n} }}} \right) = \hfill \\ \mathop \propto \limits_{n\, \to \,\infty } \ln \left( {\frac{n} {{\left( {1/\sqrt 2 } \right)^{1/n} \left( {n + 1/2} \right)}}e} \right)\;\quad \mathop \propto \limits_{n\, \to \,\infty } 1 \hfill \\ \end{gathered}$$

where we have used the following identities

Rising Factorial definition: $$\prod\limits_{0\, \leqslant \,k\, \leqslant \,w - 1} {\left( {z + k} \right)} = z^{\,\overline {\,w\,} } = \Gamma \left( {z + w} \right)/\Gamma \left( z \right)$$

Duplication Formula for Gamma $$\Gamma \left( {2\,z} \right) = \frac{{2^{\,2\,z - 1} }} {{\sqrt \pi }}\Gamma \left( z \right)\Gamma \left( {z + 1/2} \right)$$

Stirling Asymptotyc formula for Gamma $$\Gamma (z) \propto \sqrt {\,\frac{{2\,\pi }} {z}\,} \left( {\frac{z} {e}} \right)^{\,z} \quad \left| {\;z\, \to \,\infty ,\;\;\left| {\,\arg (z)\,} \right|} \right. < \pi$$

Note the interesting fact that to your sum can be actually given a closed form value (3rd to last row).

We can rearrange the summand in terms of two telescoping components and a third component that is the kernel of a Riemann sum. To that end, we now proceed.

Let $a_n=(1+k/n)\left(\log\left(1+\frac kn\right)-\log\left(1+\frac {k-1}n\right)\right)$. Then, we can write

\begin{align} a_n&=(1+k/n)\left(\log\left(1+\frac kn\right)-\log\left(1+\frac {k-1}n\right)\right)\\\\ &=\left(\log\left(1+\frac kn\right)-\log\left(1+\frac {k-1}n\right)\right)\\\\ &+\left(\frac kn\log\left(1+\frac kn\right)-\frac{k-1}{n}\log\left(1+\frac {k-1}n\right)\right)\\\\ &-\frac1n\log\left(1+\frac {k-1}n\right) \tag 1 \end{align}

Using $(1)$ it is straightforward to see that

\begin{align} \sum_{k=1}^na_n&=\sum_{k=1}^n(1+k/n)\left(\log\left(1+\frac kn\right)-\log\left(1+\frac {k-1}n\right)\right)\\\\ &=\sum_{k=1}^n\left(\log\left(1+\frac kn\right)-\log\left(1+\frac {k-1}n\right)\right)\\\\ &+\sum_{k=1}^n\left(\frac kn\log\left(1+\frac kn\right)-\frac{k-1}{n}\log\left(1+\frac {k-1}n\right)\right)\\\\ &-\sum_{k=1}^n\frac1n\log\left(1+\frac {k-1}n\right) \\\\ &=2\log(2)-\frac1n\sum_{k=1}^n\log\left(1+\frac {k-1}n\right)\\\\ &=2\log(2)-\frac1n\sum_{k=1}^{n}\log\left(1+\frac {k}n\right)-\frac1n\log(2)\tag 2 \end{align}

Note that we could immediately evaluate the limit of $(2)$ in terms of the Riemann sum $\int_0^1 \log(1+x)\,dx=2\log(2)-1$. However, this tact is circular in nature inasmuch as we are using the sum of interest to evaluate an integral.

Hence, we proceed next by evaluating the sum on the right-hand side of $(2)$ without direct appeal to integration.

Using Stiling's Formula, we can write the sum in $(2)$ as

\begin{align} \sum_{k=1}^n\log\left(1+\frac {k}n\right)&=\log\left(\prod_{k=1}^n\frac{n+k}{n}\right)\\\\ &=\log\left(\frac{(2n)!}{n!\,n^n}\right)\\\\ &\sim \log\left(\frac{4^n\sqrt{n}}{e^n}\right)\\\\ &=n(2\log(2)-1)+\frac12\log(n) \tag 3 \end{align}

whence substituting $(3)$ into $(2)$ and letting $n\to \infty$ yields the coveted limit

$$\lim_{n\to \infty}(1+k/n)\left(\log\left(1+\frac kn\right)-\log\left(1+\frac {k-1}n\right)\right)=1$$

NOTE:

If the use of Stirling's Formula is prohibited, then we can make use of the relationship

$$\sum_{k=1}^n k^m=\frac{n^{m+1}}{m+1}+O(n^m) \tag 4$$

which can be shown using induction.

Using $(4)$, it is easy to see that

\begin{align} \frac1n\sum_{k=1}^{n}\log\left(1+\frac {k}n\right)&=\frac1n\sum_{k=1}^{n}\sum_{m=1}^\infty\frac{(-1)^{m-1}}{m} \left(\frac kn\right)^m\\\\ &=\frac1n\sum_{m=1}^\infty\frac{(-1)^{m-1}}{m} \left(\frac 1n\right)^m\sum_{k=1}^{n}k^m\\\\ &=\frac1n\sum_{m=1}^\infty\frac{(-1)^{m-1}}{m} \left(\frac 1n\right)^m\frac{n^{m+1}}{m+1}+O\left(\frac1n\right)\\\\ &=\sum_{m=1}^\infty\frac{(-1)^{m-1}}{m(m+1)}+ O\left(\frac1n\right)\\\\ &=2\log(2)-1+ O\left(\frac1n\right) \end{align}

and the result follows immediately as expected!