11
$\begingroup$

$$ \lim _{n \rightarrow \infty} \frac{1}{1+n^{2}}+\frac{2}{2+n^{2}}+\cdots+\frac{n}{n+n^{2}} $$

I want to find the limit of this infinite series which I found in a book. The answer is $1/2$.

The solution to this limit was given by Sandwich/Squeeze Theorem, which was basically that the above function lies between: $$ \frac{1}{n+n^{2}}+\frac{2}{n+n^{2}}+\frac{3}{n+n^{2}}+\cdots+\frac{n}{n+n^{2}} $$ And, $$ \frac{1}{1+n^{2}}+\frac{2}{1+n^{2}}+\cdots+\frac{n}{1+n^{2}} $$ series and the limit of both of these series tend to $1/2$ as $n \to \infty$.

I fully understood the solution, but I find that this isn't something that naturally/intuitively comes to your mind. I mean we need to find two different series by trial and error, both of which need to converge to a single number.

Is there any different solution to this limit problem, like dividing by powers of n, or maybe telescoping sums?

$\endgroup$
1
  • 5
    $\begingroup$ "... two different series by trial and error..." No trial and error required. Upper and lower bounds are natural and intuitive. $\endgroup$ Feb 20, 2022 at 9:55

6 Answers 6

18
$\begingroup$

I want to argue how you could have found the solution given.

The natural thing you want to do with the fractions is add them, but they have different denominators. Now, you could try to start multiplying the terms to get a common denominator $\left (\frac{1(2+n^2)\cdots (n+n^2)}{(1+n^2)(2+n^2)\cdots (n+n^2)}+\cdots\right)$, and you might start off by doing so and then give up when you see that the answer is not going to be easily found this way.

So, let's ask, what is the closest sequence where the denominators are the same (so we can just add the fractions)?

Well, there's two answers: what if we take the denominator to be the first term's, $1+n^2$, and what if we take the denominator to be the last term's, $n+n^2$? It happens to be that the first case reduces each denominator (except the first), so it's an upper bound, and the second case is a lower bound.

There's no trial and error here: there's not really any other values you can choose. You could try a middle term, $k+n^2,1<k<n$, but I don't think it's a natural choice and you'll quickly see it can't easily be compared as greater or less than the initial series.

It's also a standard technique. Think about similar series where the denominator is changing e.g. $\frac{n^2}{1^2+n^3}+\frac{n^2}{2^2+n^3}+\cdots+\frac{n^2}{n^2+n^3}$. You can always replace each denominator by the smallest or the largest denominator in the series and compare what the two limits of those sequences are.

The method will not work in every case, as you might get different limits in some cases. However, no method will work in every case, and this sandwiching attempt is always a reasonable option to start with when you see a limit involving sums of terms with slow-growing denominators ($1+n^2,\dots,n+n^2$ are dominated by the $n^2$ term, so changing the values of $1,\dots,n$ is unlikely to change the value in the limit).

$\endgroup$
4
  • 1
    $\begingroup$ Even if you do get different limits for the upper bound and lower bound, these two limits can still be useful. They give you an upper and lower bound on the value of the limit if you already know that the sequence converges; and perhaps the existence of these bounds can be used to prove that the sequence converges. $\endgroup$
    – Stef
    Feb 20, 2022 at 15:34
  • 1
    $\begingroup$ I think this is the most natural way to think about the problem. A lot of problems can be solved if you wonder "what easier problem similar to this can I solve?" and then trying to relate your problem to that one. In this case, the similar problem is the one where the denominator is constant, so you can sum up the terms. $\endgroup$
    – Zanzag
    Feb 24, 2022 at 15:22
  • $\begingroup$ Hmmm, okay. But at the end it's still trial and error. It worked for this question because the question was manufactured specifically to be solved this way. I was looking for a general way of doing the same thing. $\endgroup$ Feb 28, 2022 at 2:31
  • 1
    $\begingroup$ @batchcoding____s there is no general way to solve a limit problem. The method selection is trial and error, regardless of what methods you choose to attempt in what order. Once you have decided to attempt sandwiching, however, there is no other (sensible) option of the upper and lower bound. With more practice, sandwiching via the denominator becomes your immediate idea when you notice that the denominators of each term grow slowly. $\endgroup$
    – A.M.
    Feb 28, 2022 at 17:22
9
$\begingroup$

Uses series of integer powers.

Find $\lim_{n\to\infty} \sum_{k=1}^n \frac{k}{k+n^2}$.

This can be expressed as an absolutely convergent geometric series and rearranged as a sum of Faulhaber's Polynomials.

$\frac{k}{k+n^2}=1-\frac{n^2}{k+n^2}=1-\frac{1}{1+\frac{k}{n^2}}=1-(1-\frac{k}{n^2}+\frac{k^2}{n^4}-\frac{k^3}{n^6}+...)=\frac{k}{n^2}-\frac{k^2}{n^4}+...$

$\sum_{k=1}^n k^p=O(n^{p+1})$ by Faulhaber's Formulas.

So our sum is $\frac{1}{n^2}\frac{n(n+1)}{2}-\frac{1}{n^4}\frac{n(n+1)(2n+1)}{6}+...$ with the limit of the first term going to $1/2$ and the sum of the remaining terms going to $0$ by The Alternating Series Test.

$\endgroup$
5
  • 5
    $\begingroup$ Uh, you need to take good care of the convergence issues, otherwise you are just giving a handwaving argument. Not saying intuition is bad, but you should make your answer properly rigorous! =) $\endgroup$
    – user21820
    Feb 19, 2022 at 17:59
  • $\begingroup$ Do you mean mentioning explicitly $|k/n^2|<1$ so the geometric series converges, and filling out the details of the delta epsilon proof for the terms that go to zero? Hmm, maybe there's a hole, an infinite sum of finite sums could throw things off. So I guess reference to uniform continuity is needed? $\endgroup$ Feb 19, 2022 at 22:05
  • 2
    $\begingroup$ That's why I said it pays to be careful. Please fix your post, since other people do not even have the basic mathematical background to recognize the hole. If you cannot fix it, you should explicitly state so in your post. Thanks! (I don't think it's as easy as you think, since I don't know what you mean by "uniform continuity", so don't handwave some more.) $\endgroup$
    – user21820
    Feb 20, 2022 at 7:20
  • 1
    $\begingroup$ The answer is great but I don't know how the OP will be able to use the result after finding the much more simple sandwich argument exotic. $\endgroup$
    – Zanzag
    Feb 24, 2022 at 15:24
  • $\begingroup$ @Zanzag. Good points. Yeah, I haven't been sure what to add without over complicating things. I seem to recall after a counterintuitive step, the proof Faulhaber's Formulas are $O(n^{p+1})$ isn't too bad. That the power of $n$ in the denominator doubles while the power in the numerator goes up by one in the final series allows for a simple proof terms go to zero perhaps without need of the AST. Not sure what's simpler between the two. $\endgroup$ Feb 24, 2022 at 15:40
8
$\begingroup$

This answer uses the same idea as the answers of TurlocTheRed and Koro, but shows that one doesn't need infinite series or big-$O$ notation. Each denominator is extremely close to $n^2$, so let's compare explicitly: \begin{align*} \sum_{k=1}^n \frac{k}{k+n^2} &= \sum_{k=1}^n \frac{k}{n^2} - \sum_{k=1}^n \bigg( \frac{k}{n^2} - \frac{k}{k+n^2} \bigg) \\ &= \frac1{n^2} \sum_{k=1}^n k - \sum_{k=1}^n \frac{k^2}{n^2(k+n^2)}. \end{align*} By standard formulas, the first sum is exactly $\frac12(1+\frac1n)$; while the second sum is positive and bounded above by the sum $$ 0 < \sum_{k=1}^n \frac{k^2}{n^2(k+n^2)} < \sum_{k=1}^n \frac{k^2}{n^2(0+n^2)} = \frac1{n^4} \sum_{k=1}^n k^2 = \frac1{6n}\bigg(1+\frac1n\bigg)\bigg(2+\frac1n\bigg). $$ The desired limit now follows from the squeeze theorem.

$\endgroup$
7
$\begingroup$

$$S_n=\sum_{r=1}^n \frac r{r+n^2}=\sum_{r=1}^n \frac{\frac r{n^2}}{ 1+\frac{r}{n^2}}=\sum_{r=1}^n \frac{1+\frac r{n^2}-1}{ 1+\frac{r}{n^2}}=\sum_{r=1}^n 1-\sum_{r=1}^n \frac{1}{ 1+\frac{r}{n^2}}=n-\sum_{r=1}^n \frac{1}{ 1+\frac{r}{n^2}}$$ $$\sum_{r=1}^n \frac{1}{ 1+\frac{r}{n^2}}=n^2\Bigg[\sum_{r=1}^{n^2+n}\frac 1r -\sum_{r=1}^{n^2}\frac 1r\Bigg]$$ So, using harmonic numbers $$S_n=n+n^2 \left(H_{n^2}-H_{n^2+n}\right)$$ Using the asymptotics $$H_p=\log (p)+\gamma +\frac{1}{2 p}-\frac{1}{12 p^2}+\frac{1}{120 p^4}+O\left(\frac{1}{p^{6}}\right)$$ apply it twice and continue with Taylor series to simplify. $$H_{n^2}-H_{n^2+n}=-\frac{1}{n}+\frac{1}{2 n^2}+\frac{1}{6 n^3}-\frac{1}{4 n^4}+\frac{2}{15 n^5}+O\left(\frac{1}{n^{6}}\right)$$ $$S_n=\frac{1}{2}+\frac{1}{6 n}-\frac{1}{4 n^2}+\frac{2}{15 n^3}+O\left(\frac{1}{n^{4}}\right)$$ which is a quite good approximation. For example, $$S_{10}=\frac{3039003639041255}{5909102214621606}=0.514292$$ while the truncated series gives exactly $0.5143$

$\endgroup$
3
$\begingroup$

Note that \begin{align*}\sum_r \frac r{r+n^2}=\frac 1{n^2}\sum\frac r{1+\frac r {n^2}}&=\frac 1{n^2}\sum r(1-r/{n^2}+O(1/n^3))\\&=\frac 1{n^2}(\sum r-\frac 1{n^2}\sum r+(\sum r)O(\frac 1{n^3}))\to \frac 12 \end{align*}

Here, the identity $\sum r=\sum_{r=1}^nr=\frac {n(n+1)}2$ has been used.

The second equality is due to binomial theorem.

$\endgroup$
1
$\begingroup$

A limit of such a sum can often be interpreted as a Riemann sum. So set $\frac1n=\Delta x$ and $x_k=\frac{k}{n}$, then $$ \frac{k}{k^2+k}=\frac{x_k\,Δx}{1+x_k\,Δx}. $$ The fraction $\hat x_k=\frac{x_k}{1+x_kΔx}$ can be seen as a point inside the interval $[x_{k-1}, x_k]$, so that indeed the given sum $$ \sum_{k=1}^n\hat x_k\,Δx $$ is a valid Riemann sum for $$ \int_0^1x\,dx=\frac12. $$ As this is indeed Riemann integrable, any sequence of Riemann sums converges to the integral value if the maximal step size goes to zero.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .