10
$\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$
  • 3
    $\begingroup$ Euler-MacLaurin formula might interest you. $\endgroup$ – Sangchul Lee Jan 26 '17 at 5:56
  • $\begingroup$ Is this method has the minimum error in comparison to other methods? $\endgroup$ – Hasan Heydari Jan 26 '17 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 Jan 26 '17 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$ – Sangchul Lee Jan 26 '17 at 6:18
5
$\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$
  • $\begingroup$ In my question, the error will tend to zero when $n\rightarrow \infty$? $\endgroup$ – Hasan Heydari Jan 26 '17 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$ – Brevan Ellefsen Jan 26 '17 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$ – Brevan Ellefsen Jan 26 '17 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$ – Sangchul Lee Jan 26 '17 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$ – Brevan Ellefsen Jan 26 '17 at 6:41
6
$\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$
  • $\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$ – Hasan Heydari Jan 26 '17 at 7:30
  • 1
    $\begingroup$ @HasanHeydari, With the change of index $n-i = k$ you can prove the equality. $\endgroup$ – Sangchul Lee Jan 26 '17 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$ – Brevan Ellefsen Jan 26 '17 at 14:25
1
$\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$

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.