# Determining n in sigma ($\Sigma_{x=0}^n$)

I'm not entirely sure if this question falls under MathOverflow but neither of my Calculus AP teachers in high school could help me with this:

Given $\Sigma_{x=0}^n {f(x)\over2}$ and the output of the summation, how would you find $n$? I've learned how to determine the $n$ given an arithmetic or geometric sequence, but not for an arbitrary function.

Specifically, when $f(x) = 40 + 6\sqrt{x}$.

12 Oct 2010. Edit: It seems like I need to explain the entire situation for finding $n$, the number of trapezoids, for trapezoidal rule. It started on a simple review question for Calc AP and a TI-83 program that my calc teacher gave to me to solve the definite integral with trapezoidal rules. Aiming to major in Computer Science, I took it a bit further and completely took apart the program resulting in my original question on StackOverflow: http://stackoverflow.com/questions/3886899/determining-the-input-of-a-function-given-an-output-calculus-involved

Since there were tumbleweeds for a response, I took it as a personal challenge to reverse engineer the trapezoidal program into an algebraic form with my notes found on my forum: http://www.zerozaku.com/viewtopic.php?f=19&t=6041

After reverse engineering the code into some algebra, I derived the formula: $$TrapRule(A, B, N) = {(B-A)\over N}({F(A)\over2}+\sum_{k=1}^NF(k)+{F(B)\over2})$$

Given the values of A and B are constant for the definite integral, I should be able to isolate and solve for $N$. The problem, however, was determining $N$ in $sum_{k=1}^N$ and I came to the conclusion that it was an issue that I called recursive complexity because it was impossible to determine without recursively adding for the summation.

Eventually, I found MathOverflow and they referred me here. I was hoping only to get help on the issue for a summation because its beyond my skill as a high school student. Now that others have proposed other solutions for my dilemma, I guess I can throw out my thesis Dx

Thanks for the help though, I'll definitely be returning for more.

-

An approximation to $\displaystyle \sum_{k=1}^{n} \sqrt{k}$ can be found here (on this very site): http://math.stackexchange.com/questions/5676/how-closely-can-we-estimate-sum-i0n-sqrti/5728#5728

It was shown that $\displaystyle \frac{2n\sqrt{n}}{3} + \frac{\sqrt{n}}{2} -\frac{2}{3} < \sum_{k=1}^{n} \sqrt{k} < \frac{2n\sqrt{n}}{3} + \frac{\sqrt{n}}{2}$

Thus if $\displaystyle S = \sum_{k=0}^{n} f(x)/2$, then

$$\sum_{k=0}^{n} \sqrt{n} = \frac{S - 10n(n+1)}{3}$$

Using the approximation above

$$\frac{2n\sqrt{n}}{3} + \frac{\sqrt{n}}{2} = \frac{S - 10n(n+1)}{3}$$

This is a fourth degree equation in $\sqrt{n}$ which can be solved exactly (closed formula) in terms of $S$ and would give you a value of $n$ which is close to $n$.

My guess is that taking the integer part of the square of an appropriate root will be sufficient to give $n$ or $n-1$ (and so a formula might exist, after all!)

If you are not looking for a formula, but a procedure, you can always try binary search.

Hope that helps.

-
Yes, if you can get usable lower and upper bounds for $n$, bisection would be the ticket. –  Ｊ. Ｍ. Oct 11 '10 at 22:28

You are trying to calculate the inverse of the function $$S(n)=\sum_{x=0}^n f(x)/2$$

In general the inverse would not exist (think $f(x)=0$).

If the inverse exists, a trivial way to solve your problem would be to start calculating the sum for $n=0,1,2,\ldots$ and stop when the result matches the number provided.

If you are looking for a formula for $S^{-1}(n)$, there is no reason for there to be such a formula for every $f(x)$. The arithmetic and geometric progression examples you gave were lucky exceptions.

-

This was supposed to be a comment to reply to Gio's comment in Matt's answer, but it got too long.

Gio, you should have mentioned that little detail about your application to determining the number of panels needed for the trapezoidal rule in your question, because it now looks to me that you're going about it the wrong way. what you actually need here is an estimate of the truncation error of the trapezoidal rule.

One expression you can use for the error estimate is

$$\frac{h^2}{12}\left(f^{\prime}(b)-f^{\prime}(a)\right)$$

where $a$ and $b$ are the upper and lower limits, $h=\frac{b-a}{n}$ is the panel size, and $f^{\prime}$ is the derivative of your integrand. To use this, suppose you want the error to be around $10^{-11}$. Equate the error estimate to your desired tolerance, and solve for $n$. This error estimate assumes that $f$ is continuous up to the second derivative ($C^2$); otherwise, the estimate can fail badly. Apart from this, the other possible way the error estimate can fail is if $f^{\prime}$ vanishes at the endpoints (e.g. when integrating a periodic function over one period); for this particular case, the trapezoidal rule is actually more accurate than usual.

-
Here the derivatives blow up at the left endpoint (zero). Does one cut the interval strategically, or is there a more principled approach? –  T.. Oct 12 '10 at 18:03
@T: Both of your suggestions are used in practice. For the first, that leads to adaptive quadrature; for the second, the Romberg method on which the trapezoidal rule is built is modified to take into account terms of the asymptotic expansion of the error that appear in functions with algebraic singularities. However, still the best approach is to do a change of variable so that the integrand is singularity-free. –  Ｊ. Ｍ. Oct 17 '10 at 5:39

Further to Jyotirmoy's answer, for the $f(x)$ you have given

$$S(n)=\sum_{x=0}^{n}\frac{f(x)}{2}$$

$$=\sum_{x=0}^{n}\frac{(40+6\sqrt{x})}{2}$$

$$=\sum_{x=0}^{n}(20+3\sqrt{x})$$

$$=\sum_{x=0}^{n}20+3\sum_{x=0}^{n}\sqrt{x}$$

The second sum is a generalised harmonic number, which doesn't have a nice closed form expression

-
Couldn't you easily get pretty tight upper and lower bounds for the second term? If the equation is solvable by a natural n, that would give you one or two values to try out, I guess. –  yatima2975 Oct 11 '10 at 13:01

Perhaps you can also work it out by approximating (lower and upper bounding) the sum by an integral:

$$\int_0^N \sqrt{x} \; dx \le \sum_0^N \sqrt x \le \int_0^N \sqrt{x+1} \; dx$$

-

Following on from leonbloy's answer, one can use the Euler--Maclaurin summation formula to obtain a rather precise approximation of the sum via an integral. In particular, the error term in that formula involves higher derivatives of the function $f(x)$. Since the higher derivatives of your function tend to zero as $x \to \infty$, you should be able to obtain reasonably precise approximations by playing around a bit.

-
The ironic part about this is that I'm using this to find n, the number of trapezoids required in the trapezoidal rule given the definite integral. –  Gio Borje Oct 12 '10 at 2:54

If you don't require trapezoids of the same width, you can get a closed form by taking a partition of $[0,n]$ into intervals with endpoints $n,nq,nq^2,\dots nq^k$ for $q<1$ and $k$ large (or infinite), or by using $(i/n)^2, i=0 \dots n$ as the endpoints. The first approach leads to the sum of a geometric series and the second is the sum of values of a polynomial.

Better answers are possible if you specify what is the problem you are ultimately trying to solve. Is it finding the number of equal-width trapezoids needed to achieve a given accuracy in the integral $\int_0^n f(x) dx$?

-
Yeah, that's exactly what I'm trying to achieve but I was hoping to complete this myself with as little as help possible but I knew solving for the number of items in Sigma is out of my league. –  Gio Borje Oct 13 '10 at 1:14