0
$\begingroup$

Compute $\lim_{n\rightarrow\infty} H_n-H_{\frac{n}{2}}$ where $H_n=\sum_{i=1}^n\frac{1}{i}$.

Alternatively, we can rewrite $H_n-H_{\frac{n}{2}}$ as $\sum_{i=\frac{n}{2}+1}^n\frac{1}{i}$ if this form is easier to manipulate.

I really have no idea where to begin with this problem. Any help/hints would be greatly appreciated!

$\endgroup$
1
  • $\begingroup$ Welcome to our site! $\endgroup$ Aug 26, 2015 at 19:52

3 Answers 3

4
$\begingroup$

One idea would be to use $H_n \sim \ln n+\gamma$ where $\gamma$ is the Euler-Mascheroni Constant. Hence $H_{2n}-H_n \sim \ln (2n)-\ln n=\ln 2$. But if you want to keep working with this sum then you might better write it as $$H_{2n}-H_n=\left( 1+\frac{1}{2}+\frac{1}{3}+\dotsc+\frac{1}{2n} \right)-\left(\frac{2}{2}+\frac{2}{4}+\frac{2}{6}+\dotsc+\frac{2}{2n}\right)$$$$=1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\dotsc-\frac{1}{2n}$$ So you basically want to prove that $$1-\frac{1}{2}+\frac{1}{3}-\frac{1}{4}+\dotsc=\ln 2$$ One way to do this is to use the following Taylor series: $$\ln (1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}-\frac{x^4}{4}+\dotsc$$ where the RHS converges for $-1<x \le 1$.

$\endgroup$
3
$\begingroup$

We have $$H_{n}\sim\log\left(n\right)+\gamma+O\left(\frac{1}{n}\right) $$ and $$H_{n/2}\sim\log\left(\frac{n}{2}\right)+O\left(\frac{1}{n}\right) $$ then $$H_{n}-H_{n/2}\longrightarrow\log\left(2\right) $$ at $n\longrightarrow\infty $.

$\endgroup$
1
  • 1
    $\begingroup$ You forgot $\gamma$ in the second asymptotic formula. $\endgroup$
    – Dominik
    Aug 28, 2015 at 8:12
2
$\begingroup$

Hint: $$\log\left(\frac{2n}{n+2}\right)=\int_{\frac{n}{2}+1}^{n}\frac{1}{x}\mathrm{d}x\leq\sum_{i=\frac{n}{2}+1}^{n}\frac{1}{i}\leq \int_{\frac{n}{2}-1}^{n}\frac{1}{x}\mathrm{d}x=\log\left(\frac{2n}{n-2}\right).$$

$\endgroup$

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