Section 6.1: Sequential Searching

Exercise 8. [HM22] [HM22] Find an asymptotic series for H® asn, co, when « Al.

Verified: yes
Solve time: 1m03s

---

Solution

Let

$$ H_N^{(\theta)}=\sum_{k=1}^{N} k^{-\theta}, \qquad \theta \neq 1. $$

Apply Euler–Maclaurin summation to $f(x)=x^{-\theta}$. For any integer $m\ge 1$,

$$ \sum_{k=1}^{N} f(k)

\int_{1}^{N} f(x),dx +\frac{f(N)+f(1)}{2} +\sum_{r=1}^{m-1}\frac{B_{2r}}{(2r)!}\bigl(f^{(2r-1)}(N)-f^{(2r-1)}(1)\bigr) +R_m, $$

where $B_{2r}$ are Bernoulli numbers and $R_m$ is the remainder term.

For $f(x)=x^{-\theta}$,

$$ \int_{1}^{N} x^{-\theta},dx=\frac{N^{1-\theta}-1}{1-\theta}. $$

Also,

$$ f^{(j)}(x)=(-1)^j (\theta)_j x^{-\theta-j}, $$

where $(\theta)_j=\theta(\theta+1)\cdots(\theta+j-1)$.

Hence,

$$ f^{(2r-1)}(x)=-(\theta)_{2r-1} x^{-\theta-(2r-1)}. $$

Substituting into Euler–Maclaurin gives

$$ H_N^{(\theta)}

\frac{N^{1-\theta}-1}{1-\theta} +\frac{1+N^{-\theta}}{2} +\sum_{r=1}^{m-1}\frac{B_{2r}}{(2r)!}(\theta)_{2r-1}\left(N^{1-\theta-2r+1}-1\right) +R_m. $$

Collecting the constant terms (independent of $N$) defines the analytic continuation constant

$$ \zeta(\theta)

\frac{1}{\theta-1} +\frac{1}{2} +\sum_{r=1}^{\infty}\frac{B_{2r}}{(2r)!}(\theta)_{2r-1}, $$

so that the expansion can be rewritten in standard asymptotic form.

Rearranging terms yields, as $N\to\infty$,

$$ H_N^{(\theta)}

\zeta(\theta) +\frac{N^{1-\theta}}{1-\theta} +\frac{1}{2}N^{-\theta} +\sum_{r=1}^{m-1}\frac{B_{2r}}{(2r)!}(\theta)_{2r-1}N^{1-\theta-2r} +R_m. $$

The remainder satisfies

$$ R_m = O!\left(N^{-\theta-2m+1}\right). $$

Thus the asymptotic series is

$$ H_N^{(\theta)} \sim \zeta(\theta) +\frac{N^{1-\theta}}{1-\theta} +\frac{1}{2}N^{-\theta} +\sum_{r\ge 1}\frac{B_{2r}}{(2r)!}(\theta)_{2r-1}N^{1-\theta-2r}. $$

This completes the proof. ∎

$$ \boxed{ H_N^{(\theta)} \sim \zeta(\theta) +\frac{N^{1-\theta}}{1-\theta} +\frac{1}{2}N^{-\theta} +\sum_{r\ge 1}\frac{B_{2r}}{(2r)!}(\theta)_{2r-1}N^{1-\theta-2r} } $$