Encontrar los asintóticos de una suma$\sum_{k=1}^{n}\frac{n-k+1}{k}$

Question

Deje$n\in\mathbb{Z}^{+}$ y$\displaystyle S_n = \sum_{k=1}^{n}\frac{n-k+1}{k}$. Hallazgo $\Theta(S_n)$

PD: encontré$\mathcal{O}(S_n) = n^2$. Por lo tanto, tener$(n-k+1)/k = (n+1)/k -1 \leq n$.

$\rightarrow S_n = \sum_{k = 1} ^ {n}n = n^2$. Pero no puedo encontrar$\mathcal{\Omega}(S_n)$, así que tampoco puedo encontrar$\mathcal{\Theta}(S_n)$.

Answer 1

Recordemos lo que$\Theta$ significa: "f es$\Theta(g)$" significa que hay constantes C, D, de manera tal que, para% suficiente$n$,$C g(n) \leq f(n) \leq Dg(n)$.

Su suma$S_n$ se divide en$A_n-B_n$ donde$A_n=(n+1)\sum_{k=1}^n 1/k $ y$B_n=\sum_{k=1}^n 1$.

$B_n=n$, así que no hay problema con los asintóticos:$B_n$ es$\Theta(n)$. ¿Qué pasa si te dije$\sum_{k=1}^n 1/k = \log(n) +\gamma_n$ donde$(\gamma_n)$ es una secuencia convergente? ¿Podrías encontrar los asintóticos de$A_n$ entonces?