13
$\begingroup$

I am going to approximate $\sum_{i=0}^{n-1}(\frac{n}{n-i})^{\frac{1}{\beta -1}}$ by $\int_{0}^{n-1}(\frac{n}{n-x})^{\frac{1}{\beta -1}}dx$, such that $n$ is sufficiently large.

  1. Is the above approximation true?
  2. If the above approximation is true, by which theorem or method (like Newton's method) it can be holds? What is the error of approximation?
$\endgroup$
4
  • 4
    $\begingroup$ Euler-MacLaurin formula might interest you. $\endgroup$ Commented Jan 26, 2017 at 5:56
  • $\begingroup$ Is this method has the minimum error in comparison to other methods? $\endgroup$ Commented Jan 26, 2017 at 6:02
  • $\begingroup$ You can't really discuss "minimum error" in an absolute sense without discussing the function. // The gist is that one formulation of calculus is derived doing the reverse. Using sums to evaluate integrals. $\endgroup$
    – MaxW
    Commented Jan 26, 2017 at 6:12
  • $\begingroup$ I think I am not following you, since it seems to me that the error between the sum and the integral is just a fixed function of $n$. Euler-Maclaurin formula provides a systematical way of approximating this error, but I see no reason that this approach is always the most efficient for this pursuit (especially thinking that the formal sum describing the asymptotic expansion often do not converge, and is only meaningful as truncated sense). $\endgroup$ Commented Jan 26, 2017 at 6:18

3 Answers 3

8
$\begingroup$

One way to visualize what your are doing is with Riemann Sums. Assuming your function is increasing (it depends on $n$ and $\beta$) we have that $$\int_{a-1}^{b} f(x) dx \leq \sum_{k=a}^b f(k) \leq \int_{a}^{b+1} f(x) dx$$ From a more general perspective, we can apply the Euler-MacLaurin Formula, which says that $$\sum_{n=a}^b f(n) = \int_a^b f(x) dx + \frac{f(a)+f(b)}{2} + \sum_{k=1}^\infty \frac{B_{2k}}{(2k)!}(f^{(2k-1)}(b)-f^{(2k-1)}(a))+R$$ or that $$\sum_{n=a}^b f(n) \sim \int_a^b f(x) dx + \frac{f(a)+f(b)}{2} + \sum_{k=1}^\infty \frac{B_{2k}}{(2k)!}(f^{(2k-1)}(b)-f^{(2k-1)}(a))$$ Where $B_{k}$ is the $k$th Bernoulli Number (all the odd Bernoulli numbers are just zero)

The error term $R$ is very small (and depends on $a,b,$ and $f$) so we can usually ignore it unless you absolutely need it. See the linked page for an explicit formula.

Edit:
Per the OP's request, the reason we can neglect the error term is that we have the general form of the Euler-MacLaurin Formula as such: $$\sum_{n=a}^b f(n) = \int_a^b f(x) dx + \frac{f(a)+f(b)}{2} + \sum_{k=1}^{\color{red}{\left\lfloor \frac p2 \right\rfloor}} \frac{B_{2k}}{(2k)!}(f^{(2k-1)}(b)-f^{(2k-1)}(a))+R$$ In the formula I wrote above we take $p \to \infty$. We further note (see the Wikipedia page) that the remainder $R$ is bounded as such: $$|R| \leq \frac{2 \zeta(p)}{(2 \pi)^p}\int_a^b |f^{(p)}(x)|dx$$
Now, there are two parts of this. The fraction clearly goes to zero as $p \to \infty$, because the Riemann Zeta function is decreasing and bounded while the denominator grows without bounds. Thus, all we have to be able to say is that the integral doesn't blow up to $+$ or $-$ infinity as we differentiate more and more (i.e. let $p \to \infty$). Most functions you work with will satisfy this criteria, but you can check this explicitly if you so desire.

Edit 2:
As noted by @SangchulLee in the comments, for fixed $\beta$ and fixed $x$ the integral in the OP's error term appears to grow super-exponentially. While the fraction $\frac{2\zeta(p)}{(2\pi)^p}$ definitely helps decrease this growth a bit, the error term might need to be watched carefully here.

$\endgroup$
8
  • $\begingroup$ In my question, the error will tend to zero when $n\rightarrow \infty$? $\endgroup$ Commented Jan 26, 2017 at 6:18
  • $\begingroup$ @HasanHeydari The source on Wikipedia says "Usually". I will edit this into my answer with a little explanation on why this is $\endgroup$ Commented Jan 26, 2017 at 6:23
  • $\begingroup$ @HasanHeydari I included an edit which explicitly states the remainder formula and explains why we can ignore the remainder for "most" functions $\endgroup$ Commented Jan 26, 2017 at 6:32
  • 1
    $\begingroup$ I would say the opposite. With OP's $f$ and for each fixed $x$, we can check that $|f^{(p)}(x)|$ grows super-exponentially as $p \to \infty$. For instance, if we choose $\beta = 2$ so that $f(x) = \frac{n}{n-x}$, then $f^{(p)}(x) = \frac{p!n}{(n-x)^{p+1}}$. $\endgroup$ Commented Jan 26, 2017 at 6:39
  • 1
    $\begingroup$ @SangchulLee Huh. You are right. For the record, I never say that we should ignore the error term, just that we usually can. I didn't check the condition here per-se (I was leaving it to the OP) but you are absolutely right as far as I can tell.\ $\endgroup$ Commented Jan 26, 2017 at 6:41
7
$\begingroup$

If we write $s = 1/(\beta-1)$, your sum and integral can be re-written as

$$ \sum_{i=0}^{n-1} \left( \frac{n}{n-i} \right)^s = n^s \sum_{k=1}^n \frac{1}{k^s}, \qquad \int_{0}^{n-1} \left( \frac{n}{n-x} \right)^s \, dx = n^s \int_{1}^{n} \frac{dx}{x^s}. $$

In this case, the Euler-Maclaurin formula provides a way of estimating the difference within $\mathcal{O}(n^{-K})$ for any prescribed exponent $K$. To see this, let $\tilde{B}_k(x) = B_k(x - \lfloor x \rfloor)$ be the periodic Bernoulli polynomials. Then

\begin{align*} \int_{1}^{n} \frac{dx}{x^s} &= \left( \int_{[1,n]} \frac{d\lfloor x \rfloor}{x^s} + \int_{[1,n]} \frac{d\tilde{B}_1(x)}{x^s} \right) \\ &= \sum_{k=1}^{n} \frac{1}{k^s} + \int_{[1,n]} \frac{d\tilde{B}_1(x)}{x^s} \\ &= \sum_{k=1}^{n} \frac{1}{k^s} + \left[ \frac{\tilde{B}_1(x)}{x^s} \right]_{1^-}^{n} + s \int_{1}^{n} \frac{\tilde{B}_1(x)}{x^{s+1}} \, dx \\ &= \sum_{k=1}^{n} \frac{1}{k^s} - \frac{1 + n^{-s}}{2} + s \int_{1}^{n} \frac{\tilde{B}_1(x)}{x^{s+1}} \, dx \end{align*}

However, there is an issue with this form. Indeed, if we keep using $[1, n]$ as the domain of integration, the error term of the Euler-Maclaurin formula never vanishes as $n \to \infty$. This is because for each fixed $K$,

$$ \int_{1}^{n} \frac{\tilde{B}_1(x)}{x^{s+K}} \, dx = \Theta(1) \qquad \text{as } n \to \infty $$

To resolve issue, let us assume $s > 0$ and we split the last integral as the difference of two:

\begin{align*} \int_{1}^{n} \frac{dx}{x^s} &= \sum_{k=1}^{n} \frac{1}{k^s} -\frac{1 + n^{-s}}{2} + s \int_{1}^{\infty} \frac{\tilde{B}_1(x)}{x^{s+1}} \, dx - s \int_{n}^{\infty} \frac{\tilde{B}_1(x)}{x^{s+1}} \, dx \end{align*}

We note that integration by parts easily checks the asymptotics $\int_{n}^{\infty} \frac{\tilde{B}_K(x)}{x^{s+K}} \, dx = \mathcal{O}(n^{-s-K})$ for each fixed $K$. Then letting $n \to \infty$ together with the extra assumption $s > 1$, this yields

\begin{align*} s \int_{1}^{\infty} \frac{\tilde{B}_1(x)}{x^{s+1}} \, dx = \frac{1}{2} + \frac{1}{s-1} - \zeta(s). \end{align*}

This continues to hold for $s > 0$ by the principle of analytic continuation. Plugging this back and simplifying in terms of the sum,

\begin{align*} \sum_{k=1}^{n} \frac{1}{k^s} &= \int_{1}^{n} \frac{dx}{x^s} + \frac{1 + n^{-s}}{2} + s \left( \zeta(s) - \frac{1}{2} - \frac{1}{s-1} \right) + s \int_{n}^{\infty} \frac{\tilde{B}_1(x)}{x^{s+1}} \, dx. \end{align*}

Then we can continue the procedure to extract more terms: for each fixed $K$,

\begin{align*} \sum_{k=1}^{n} \frac{1}{k^s} &= \int_{1}^{n} \frac{dx}{x^s} + \frac{1 + n^{-s}}{2} + s \left( \zeta(s) - \frac{1}{2} - \frac{1}{s-1} \right)\\ &\qquad - \sum_{j=2}^{K} \frac{\Gamma(s+j-1)}{\Gamma(s)} \frac{B_j}{j!} \frac{1}{n^{s+j-1}} + \underbrace{\frac{\Gamma(s+K)}{K!\Gamma(s)} \int_{n}^{\infty} \frac{\tilde{B}_K(x)}{x^{s+K}} \, dx}_{\mathcal{O}(n^{-s-K-1})} \end{align*}

as $n \to \infty$.

$\endgroup$
3
  • $\begingroup$ Snagchul Lee: Note that $\sum_{i=0}^{n-1}(\frac{n}{n-i})^s \neq n^s \sum_{k=1}^n \frac{1}{k^s}$ $\endgroup$ Commented Jan 26, 2017 at 7:30
  • 1
    $\begingroup$ @HasanHeydari, With the change of index $n-i = k$ you can prove the equality. $\endgroup$ Commented Jan 26, 2017 at 7:31
  • $\begingroup$ Absolutely gorgeous answer. My answer simply explained what the Euler-MacLaurin formula is... Your answer beats the OP's formula to a pulp and makes everything work. Bravo. Hopefully the OP makes your's the accepted answer instead of mine $\endgroup$ Commented Jan 26, 2017 at 14:25
2
$\begingroup$

Using Riemann Siegel formula you can approximate $\sum_{i=0}^{n-1} \left( \frac{n}{n-i} \right)^s =\simeq n^s\left\{\zeta(s)-1/(s-1)(n+1/2)^{1-s}\right\}.$

This gives very accurate values for real $s>1$ even for very small $n$. For instance, for $n=2$ and $s=3$, one obtains $\zeta(3)\simeq 241/200= 1.205$.

$\endgroup$

You must log in to answer this question.

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