An integral as an approximation of a sum.

[nobahar]

Hello!

I was wondering if the following statement is true for large n:

\sum_{i=1}^{n} \ \left( 1 \ - \ \frac{i}{(n+1)} \right) \ \approx \ \lim_{n \rightarrow \inf}\ \sum_{i=1}^{n} \ \left( 1 \ - \ \frac{i}{(n+1)} \right) \left( \frac{1}{(n+1)} \right)

Firstly, the RHS is an integral, right? the 1/(n+1)*i are the x values that mark out each segment to yield the f(x) value, and the 1/(n+1) is the number of segments 1 is divided into:
x = i/(n+1) and therefore dx = 1/(n+1), for large n: n is approximately n+1, and so the limits are 0 and 1 for the integral.

\int_{0}^{1}(1 \ - \ x)dx

Returning to the above statement. I don't think it is true. I figured that if it didn't asymptote for large n, then it wouldn't be true; if it did asymptote, then it would be true (Edit: I NO LONGER THINK THIS IS TRUE).
This is all confused by the fact that I had difficulty thinking about what happens to the 1/(n+1) on the RHS and its effect on the value. The LHS, kind of has a Deltax = 1. For large n, the 1/(n+1) tends to dx for the RHS. On this basis, the products constituting the various components of the sum look hugely different in value, since (1-(i/n+1))*1 retains its value, but (1-(i/n+1))*dx makes it 'infinitesimally' small. If the value converges, then since the RHS goes to infinity, whereas the LHS is merely a (extremely) large value of n, I figured that this second difference compensates for the dx on the RHS (Edit: AS ABOVE, I DON'T THINK THIS MAKES SENSE; I'M STARTING TO THINK THAT, IF ONE CONVERGES, THE OTHER WILL NOT: e.g. If the sum without 1/(n+1) converges, then the one with 1/(n+1) will not, and vice versa).

I worked through the sum on the LHS and got to 0.5n. As n gets large, 0.5n gets larger with no asymptote, so therefore the statement is false. The RHS gives 0.5.

How do I find out what the effect of the 1/(n+1) is, and is my claim true?

Any help appreciated.

 

[jambaugh]

The LHS defines (or relies upon) the unspecified value n and so it is not good form to use it with your limit on the RHS.

Try something like:
\sum_{i=1}^n \left(1 - \frac{i}{n+1}\right) \approx \lim_{m\to\infty} \sum_{i=1}^{m\cdot n}\left( ...\right)

OR you should compare two limits (using distinct limiting variables):

\lim_{n\to\infty}\sum_{i=1}^n \left(1 - \frac{i}{n+1}\right) \mathop{=}^{\text{?}} \lim_{m\to\infty} \sum_{i=1}^{m}\cdots

 

[nobahar]

The LHS defines (or relies upon) the unspecified value n and so it is not good form to use it with your limit on the RHS.

Thanks Jambaugh, my maths is self-taught, so I probably don't use correct notation a lot of the time! I'm guessing this one:

\sum_{i=1}^n \left(1 - \frac{i}{n+1}\right) \approx \lim_{m\to\infty} \sum_{i=1}^{m\cdot n}\left( ...\right)

would be the most appropriate/better one?

Concerning the issue of convergence:
I figured that, if one converges, then the other doesn't, or it goes to zero, because:
If this converges:
\lim_{n \rightarrow \infty} \left( \sum_{i=1}^{n} \ f(i) \right) \ = \ A

Then with 1/(n+1) it goes to 0:
\lim_{n \rightarrow \infty} \left( \sum_{i=1}^{n} \ f(i) \ \frac{1}{(n+1)} \right) \ = \ \lim_{n \rightarrow \infty} \left( \sum_{i=1}^{n} \ f(i) \right) \ \lim_{n \rightarrow \infty} \left( \frac{1}{(n+1)} \right) \ = \ A \ \lim_{n \rightarrow \infty} \left( \frac{1}{(n+1)} \right) \ = \ 0

Alternatively, if this (with 1/(n+1)) converges:
\lim_{n \rightarrow \infty} \left( \sum_{i=1}^{n} \ f(i) \ \frac{1}{(n+1)} \right) \ = \ B

Then without 1/(n+1) it wouldn't because:
\lim_{n \rightarrow \infty} \left( \sum_{i=1}^{n} \ f(i) \right) \ = \ \lim_{n \rightarrow \infty} \left( \sum_{i=1}^{n} f(i) \ \frac{1}{(n+1)} \frac{(n+1)}{1} \right) \ = \ \lim_{n \rightarrow \infty} \left( \sum_{i=1}^{n} f(i) \ \frac{1}{(n+1)} \right) \ \lim_{n \rightarrow \infty} \left( \frac{(n+1)}{1} \right) \ = \ B \ \lim_{n \rightarrow \infty} \left( \frac{(n+1)}{1} \right) \ = \rightarrow \infty

 

[jambaugh]

As far as which is appropriate, I still am unclear as to what you are trying to accomplish.

Let me first mention some things about your original sums:

Your LHS by the way diverges as n-> infinity, and in fact is exactly equal to n/2. The act of summing is linear so we can break the sum up and factor out any multiples which do not depend on the index:
S = \sum_{i=1}^{n} \ \left( 1 \ - \ \frac{i}{(n+1)} \right) = \sum_{i=1}^{n} 1 -\sum_{i=1}^n \frac{i}{(n+1)} = \sum_{i=1}^{n} 1 -\frac{1}{(n+1)} \sum_{i=1}^n i
These simple sums have simple formulas:
\sum_{i=1}^{n} 1 = n,\quad \text{ and }\quad \sum_{i=1}^{n} i = \frac{n(n+1)}{2}
So
S = n - \frac{1}{(n+1)}\frac{n(n+1)}{2} =n - n/2 = n/2
Your RHS is just (the limit of) \frac{1}{n+1} times your LHS and so is the limit of..
\frac{n}{2(n+1)}\to \frac{1}{2} \text{ as } n\to \infty
Now as to integral approximations of sums, there are two ways to approach them, the first is to manipulate the sum so that it is a Riemann sum for an integral in which case for large n the sum approaches the integral:
\int_0^1 f(x)dx \approx \sum_{k=1}^n f(k/n)\cdot \frac{1}{n}
You can even allow the function f to depend on n
This way your LHS rewritten as:
\sum_{i=1}^n \left(n -\frac{i}{n}\frac{n^2}{n+1}\right)\frac{1}{n}
is approximated for large n by the integral:
\int_0^1 (n-\frac{n^2}{n+1} x)dx = n - \frac{1}{2}\frac{n^2}{n+1}

Now another related approach is to actually rewrite the sum as an integral using : floor and ceiling functions
\lfloor x \rfloor is the greatest integer below x, i.e. it rounds down and \lceil x \rceil is the least integer above x, i.e. it rounds up.
You can then rewrite a sum as an integral given that the area under the curves y=f(\lfloor x \rfloor) and y=f(\lceil x \rceil ) are sums of areas under unit width rectangles and thus the sums of their heights between the integer values.
S=\sum_{k=1}^N f(k)=\int_0^N f(\lceil x \rceil)dx = \int_1^{N+1}f(\lfloor x \rfloor)dx

Now if the function f is monotone increasing you have f(\lfloor x\rfloor) \le f(x) \le f(\lceil x \rceil) and so by replacing floored and ceiling-ed version of the integrals with continuous integrals you have upper and lower bounds on your sum.
\int_{0}^{N} f(x) dx \le \int_0^N f(\lceil x \rceil)dx= \sum_{k=1}^N f(k) = \int_1^{N+1}f(\lfloor x \rfloor)dx\le \int_{1}^{N+1} f(x)dx

Note that if the function is monotone decreasing you reverse the upper and lower bounds and if it is not monotone you can write it as sum of an increasing and decreasing function and work out the corresponding upper and lower bounds in terms of these halves.
(To be super accurate it is sufficient the function is monotone non-decreasing or monotone non-increasing respectively.)

Let's consider the example:
S=\sum_{k=1}^N 2^{-k}
f(x) = 2^{-x} so we approximate with...
\int_0^N f(x) dx = \int_{0}^N 2^{-x} dx = \int_{0}^N e^{-x\ln(2)}dx=
= \left[-\frac{1}{\ln(2)} e^{-\ln(2)x}\right]^N_0 = \frac{1}{\ln(2)}[ 1-2^{-N}]
Since our function is monotone decreasing this is a upper bound. The lower bound is the same integral evaluated from 1 to N+1 which we note is 1/2 the above.
\frac{1}{2\ln(2)}[ 1-2^{-N}]\le S \le \frac{1}{\ln(2)} [1-2^{-N}]
And we note that this sum is calculable and is:S = 1-2^{-N}. With 1/\ln(2) \simeq 1.44 we have bounds of 0.72S \le S \le 1.44 S.
Not great (and not converging to the sum for large N) but the bounds converge with the sum to give us boundaries on its limit.

 

[nobahar]

Thanks for the response, and the examples, they are really helpful (and considering how long Latex takes!).
Okay, I've worked through it and I think I understand most of it, but I have a couple of things I'm not clear about.

Now as to integral approximations of sums, there are two ways to approach them, the first is to manipulate the sum so that it is a Riemann sum for an integral in which case for large n the sum approaches the integral:
\int_0^1 f(x)dx \approx \sum_{k=1}^n f(k/n)\cdot \frac{1}{n}
You can even allow the function f to depend on n
This way your LHS rewritten as:
\sum_{i=1}^n \left(n -\frac{i}{n}\frac{n^2}{n+1}\right)\frac{1}{n}
is approximated for large n by the integral:
\int_0^1 (n-\frac{n^2}{n+1} x)dx = n - \frac{1}{2}\frac{n^2}{n+1}

In the function, you added n/n so that we get n²/n+1. I'm guessing this is so we get i/n, as suggested by the way it written separately. Why can't we just use i/(n+1)? Since for large n the 1 is negligible, or n \approx n+1?

Let's consider the example:
S=\sum_{k=1}^N 2^{-k}
f(x) = 2^{-x} so we approximate with...
\int_0^N f(x) dx = \int_{0}^N 2^{-x} dx = \int_{0}^N e^{-x\ln(2)}dx=
= \left[-\frac{1}{\ln(2)} e^{-\ln(2)x}\right]^N_0 = \frac{1}{\ln(2)}[ 1-2^{-N}]
Since our function is monotone decreasing this is a upper bound. The lower bound is the same integral evaluated from 1 to N+1 which we note is 1/2 the above.
\frac{1}{2\ln(2)}[ 1-2^{-N}]\le S \le \frac{1}{\ln(2)} [1-2^{-N}]
And we note that this sum is calculable and is:S = 1-2^{-N}. With 1/\ln(2) \simeq 1.44 we have bounds of 0.72S \le S \le 1.44 S.
Not great (and not converging to the sum for large N) but the bounds converge with the sum to give us boundaries on its limit.

Initially K is used, so its a function of k, then we switch to x as the variable. Is there a reason for this? I also do not understand why S = 1-2^-N.

Any further help appreciated.

 

[jambaugh]

Thanks for the response, and the examples, they are really helpful (and considering how long Latex takes!).
Okay, I've worked through it and I think I understand most of it, but I have a couple of things I'm not clear about.


In the function, you added n/n so that we get n²/n+1. I'm guessing this is so we get i/n, as suggested by the way it written separately. Why can't we just use i/(n+1)? Since for large n the 1 is negligible, or n \approx n+1?

Fine, for an approximation. But I was trying to get the sum in the form of a Riemann integral and the intervals must be of width 1/n since you are adding up n terms in the sum.

The integral as a limit of a Riemann sum is:
\int_a^b f(x)dx = \lim_{n\to \infty} \sum_{k=1}^n f(x_k)\Delta x
where x_k = a+ k \Delta x and \Delta x = (b-a)/n.
That way x_0 = a and x_n = b. (This is a Riemann sum using the value of the function at the right of each interval. You can also evaluate at the left or middle, defining x^*_k = x_k - \Delta x or x^*_k = x_k - \Delta x/2. It doesn't matter in the limit as n goes to infinity.)

Initially K is used, so its a function of k, then we switch to x as the variable. Is there a reason for this?

That's just to emphasize the transition from a integer valued variable k to a continuous variable x. Nothing more than that.

I also do not understand why S = 1-2^-N.

That is a standard formula for geometric sums. It is based on the "telescoping sum"
(1-a)(1+a+a^2+...+a^{n-1})=1-a^{n}
multiply it out and you see all but the two terms cancel. Solve this equation for the long sum as a ratio of binomials. In the case I used it a = 1/2 = 2^{-1}, also since the first term is 2^{-1} you must subtract out that 1 term from your answer. Then simplify.