patternMinor
Asymptotic estimate for $\sum_{k=1}^{N} {\frac{1}{k^2 H_k}}$
Viewed 0 times
estimatefracsum_h_kasymptoticfor
Problem
I am working on finding the asymptotic estimate for $$ \sum_{k=1}^{N} {\frac{1}{k^2 H_k}}.$$
All I know is that ${\frac{1}{k^2 H_k}}$ is convergent because $${\frac{1}{k^2 H_k}}<\frac{1}{k^2}$$ and $\frac{1}{k^2}$ is convergent.
Am I right to conclude that the asymptotic estimate for this is $O(\frac{1}{k^2})$?
All I know is that ${\frac{1}{k^2 H_k}}$ is convergent because $${\frac{1}{k^2 H_k}}<\frac{1}{k^2}$$ and $\frac{1}{k^2}$ is convergent.
Am I right to conclude that the asymptotic estimate for this is $O(\frac{1}{k^2})$?
Solution
Since the infinite series $\sum_{k=1}^\infty \frac{1}{k^2H_k}$ converges, an asymptotic estimate to your sum is simply $\Theta(1)$.
You can obtain a better estimate by estimating the tail:
$$
\sum_{k=1}^n \frac{1}{k^2H_k} = \sum_{k=1}^\infty \frac{1}{k^2}{H_k} - \sum_{k=n+1}^\infty \frac{1}{k^2H_k}.
$$
We can estimate the tail by
$$
\sum_{k=n+1}^\infty \frac{1}{k^2H_k} \leq
\sum_{k=n+1}^\infty \frac{1}{k(k+1)} = \frac{1}{n},
$$
and so
$$
\sum_{k=1}^n \frac{1}{k^2 H_k} = C - O\left(\frac{1}{n}\right),
$$
where $C = \sum_{k=1}^\infty 1/k^2H_k \approx 1.33275$.
You can obtain a better estimate by estimating the tail:
$$
\sum_{k=1}^n \frac{1}{k^2H_k} = \sum_{k=1}^\infty \frac{1}{k^2}{H_k} - \sum_{k=n+1}^\infty \frac{1}{k^2H_k}.
$$
We can estimate the tail by
$$
\sum_{k=n+1}^\infty \frac{1}{k^2H_k} \leq
\sum_{k=n+1}^\infty \frac{1}{k(k+1)} = \frac{1}{n},
$$
and so
$$
\sum_{k=1}^n \frac{1}{k^2 H_k} = C - O\left(\frac{1}{n}\right),
$$
where $C = \sum_{k=1}^\infty 1/k^2H_k \approx 1.33275$.
Context
StackExchange Computer Science Q#66629, answer score: 3
Revisions (0)
No revisions yet.