0
$\begingroup$

Problem: calculate the sums of the form: $$\lim_{n\rightarrow\infty}\sum_{i=0}^{n}\left(\dfrac{i}{n}\right)^{f(n)}$$

Inspiration: one problem lets us prove that $\sum_{i=1}^{n}\left(\dfrac{2i-1}{2n}\right)^{n}<\dfrac{\sqrt{e}}{e-1}$. After using numeric tools I found that it seems to converge to the bound.

I tried to reduce it into a form of finite sums of sum integral, that is, write $nr^n$ in a form independent of $n$. But it seems impossible.

It is worth noting that $\sum_{i=1}^{n}\left(\dfrac{2i-1}{2n}\right)^{n}=\sum_{i=0}^{2n}\left(\dfrac{i}{2n}\right)^{n}-\sum_{i=0}^{n}\left(\dfrac{i}{n}\right)^{n}$. So it inspired me to calculate $$\lim_{n\rightarrow\infty}\sum_{i=0}^{n}\left(\dfrac{i}{n}\right)^{kn}$$ or more generally the form in the title.

$\endgroup$
  • 3
    $\begingroup$ For your last sum we should have something like $\lim_{n\to \infty}\sum_{i=1}^n\left(\frac{i}{n}\right)^{nk} = \lim_{n\to \infty}\sum_{i=0}^{n-1}\left(1 - \frac{i}{n}\right)^{nk} = \lim_{n\to\infty}\sum_{i=0}^{n-1}e^{-ki} = \frac{1}{1-e^{-k}}$ giving $\frac{\sqrt{e}}{e-1}$ for the problem you want to solve. I did skip a lot of details in the derivation though so it might be some work to rigorously establishing this. $\endgroup$ – Winther Jul 31 '15 at 5:21
2
$\begingroup$

There is most likely no general algorithm for evaluating expression on the form $\lim\limits_{n\to\infty}\sum_{i=1}^n \left(\frac{i}{n}\right)^{f(n)}$ for a completely general function $f(n)$ - it's simply to broad of a question. The best general answer you could hope to get is a way to determine if the sum converges or not based upon the asymptotic properties of $f(n)$. That being said we can solve in closed form for the example you presented and I have added a proof of this below.


We have

$$I_n = \sum_{i=1}^n\left(\frac{i}{n}\right)^{nk} = \sum_{i=0}^{n-1}\left(1-\frac{i}{n}\right)^{kn}$$

where I have made the substitution $i\to n-i$ to get the last sum. Since $\lim\limits_{n\to\infty}\left(1-\frac{x}{n}\right)^{kx} = e^{-kx}$ it seems natural to study the function $$g(x) = e^{-kx} - \left(1 - \frac{x}{n}\right)^{kn}.$$

This function is positive on $[0,n]$ and has a maximum for $e^{-kx} = \left(1 - \frac{x}{n}\right)^{kn-1}$. The maximum value satisfies $g(x) = \frac{xe^{-kx}}{n}$ and from this it follows that

$$0 \leq \sum_{i=0}^{n-1}e^{-ki} - I_n = \sum_{i=0}^{n-1}g(i) < \frac{1}{n}\sum_{i=0}^{n-1} ie^{-ki} < \frac{1}{n}\sum_{i=0}^{\infty} ie^{-ki}$$

Since $\sum_{i=0}^{\infty} ie^{-ki} < \infty$ for $k>0$ we can conclude that

$$\lim_{n\to\infty}I_n = \sum_{i=0}^{\infty}e^{-ik} = \frac{1}{1-e^{-k}}$$

Using this we get, using the formula you derived, that your first sum satisfies

$$\lim_{n\to\infty}\sum_{i=1}^n \left(\frac{2i-1}{2n}\right)^n = \frac{1}{1-e^{-1/2}} - \frac{1}{1-e^{-1}} = \frac{\sqrt{e}}{e-1}$$


It turns out this problem has been solved before on this site. See this related question for alternative proofs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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