# Finding the asymptotics of a summation $\sum_{k=1}^{n}\frac{n-k+1}{k}$

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)$.

-
The $i$ should be a $k$, right? Try writing it as $(n+1) \sum 1/k$ minus $\sum k/k = \sum 1$. You can deal with those sums separately... –  mt_ Dec 28 '11 at 16:39
@mt_: I'm sorry. I typed not correct. I editted. Thanks! –  qwerty89 Dec 28 '11 at 16:46
@mt_ : perhaps you should make it an answer, asymptotics for $H_n$ are well-known, are they? –  Patrick Da Silva Dec 28 '11 at 16:47
I found $\mathcal{O}(S_n) = n^2$. Thus, having $(n-k+1)/k = (n+1)/k -1 \leq n$. ==> $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)$ –  qwerty89 Dec 28 '11 at 16:50
qwerty89: Did you read the comments above? They suggest to first get/use a simple asymptotics of $H_n=\sum\limits_{k=1}^n\frac1k$. Did you do that? –  Did Dec 28 '11 at 17:01

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?
Nice answer. You might consider replacing thrice $\backslash$sum by $\backslash$sum$\backslash$limits. –  Did Dec 28 '11 at 17:51
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}$. –  Frank Science Jun 8 '12 at 11:14