4
$\begingroup$

Let $n\in\mathbb{Z}^{+}$ and $\displaystyle S_n = \sum_{k=1}^{n}\frac{n-k+1}{k}$. Finding $\Theta(S_n)$

PS: I found $\mathcal{O}(S_n) = n^2$. Thus, having $(n-k+1)/k = (n+1)/k -1 \leq n$.

$\rightarrow S_n = \sum_{k = 1} ^ {n}n = n^2$. But I cant find $\mathcal{\Omega}(S_n)$, so I cant also find $\mathcal{\Theta}(S_n)$.

  • 0
    The estimate $O(n^2)$ is a very pessimistic one, you are giving too much away.2011-12-28

1 Answers 1

4

Let's recall what $\Theta$ means: "f is $\Theta(g)$" means that there are constants C,D such that for large enough $n$, $C g(n) \leq f(n) \leq Dg(n)$.

Your sum $S_n$ splits into $A_n-B_n$ where $A_n=(n+1)\sum_{k=1}^n 1/k $ and $B_n=\sum_{k=1}^n 1$.

$B_n=n$, so no problem with the asymptotics there: $B_n$ is $\Theta(n)$. What if I told you $\sum_{k=1}^n 1/k = \log(n) +\gamma_n$ where $(\gamma_n)$ is a convergent sequence. Could you find the asymptotics of $A_n$ then?

  • 0
    Well, as *Concrete Mathematics* points out, $H_n = \ln n + \gamma + (2n)^{-1} - (12n^2)^{-1} + (120n^4)^{-1} + O(n^{-6})$, where $H_n = \sum_{k=1}^n k^{-1}$.2012-06-08