# How to find the asymptotic behavior of these sums?

Let $$X(n) = \displaystyle\sum_{k=1}^{n}\dfrac{1}{k}.$$ $$Y(n) = \displaystyle\sum_{k=1}^{n}k^{1/k}.$$ $$Z(n) = \displaystyle\sum_{k=1}^{n}k^{k}.$$

For the first, I don't have a formal proof but I know that $X(n)\in \cal{O}(\log n)$. For the rest, I think $Y(n)\in \cal{O}(n)$ and $Z(n)\in \cal{O}(n)$.

How to determine the asymptotic behavior of theses summations?

How to calculate the complexities with a formal proof?

• Note that $Z(n)\ge n^n.$ – mfl Jul 10 '14 at 14:58
• The integral test should give you upper and lower bounds on $X(n)$. You should be able to upper and lower bound (with constants) the terms in $Y(n)$. As mfl has observed, the last term in $Z(n)$ dominates -- all you have to do is show this. – Eric Towers Jul 10 '14 at 15:02
• The first is easy to compare with $\int_{1}^n \frac{dx}{x} = \log n$. It's basically a Reimann sum of this integral. – Thomas Andrews Jul 10 '14 at 15:11
• I suspect it is not hard to show that $Z(n)=O(n^n)$. – Thomas Andrews Jul 10 '14 at 15:13

Assuming $k,n \in \mathbb{Z}_{>0}$ throughout.

## X(n)

$$\ln n = \int_{1}^n \frac{\mathrm{d}x}{x} \leq \sum_{k=1}^n \frac{1}{k} \leq 1+\int_{1}^{n-1}\frac{\mathrm{d}x}{x} = 1+ \ln (n-1) < 1+\ln(n)$$

Therefore $X(n) \in O(\log n)$.

## Y(n)

We find the largest possible value of the summand by finding the largest possible value of the expression as if the variable were a real number. $D_x(x^{1/x}) = 0 \implies x = \mathrm{e}^{1/\mathrm{e}} < 3/2$ and since the second derivative is negative here, this is a maximum. There is also no challenge in using the binomial theorem to show that the summands approach 1 from above as $k$ increases. We have $1 \leq k^{1/k} \leq 3/2$.

$$(1)n \leq \sum_{k=1}^n k^{1/k} \leq (3/2) n$$

Therefore $Y(n) \in O(n)$.

## Z(n)

$$n^n \leq \sum_{k=1}^n k^k \leq n^n + (n-1)(n-1)^{n-1} = n^n + (n-1)^n < 2 n^n$$

Therefore $Z(n) \in O(n^n)$.

• +1, nice. @x.y.z..., note that these arguments additionally show that $X(n) \in \Theta(\log n)$, $Y(n) \in \Theta(n)$, and $Z(n) \in \Theta(n^n)$. – Antonio Vargas Jul 10 '14 at 16:49

I don't know how to use the integral test. As suggested by @Eric and others, I am trying to answer my question.

$$\begin{equation}\begin{split}1\leqslant k\leqslant n&\Leftrightarrow\dfrac{1}{n}\leqslant \dfrac{1}{k}\leqslant 1\\&\Leftrightarrow1\leqslant X(n)\leqslant n\\&\Rightarrow X(n)\in\cal{O}(n).\end{split}\end{equation}$$ which is not a tight approximation.

$$\begin{equation}\begin{split}1\leqslant k\leqslant n&\Leftrightarrow1\leqslant k^{1/k}\leqslant n^{1/k}\\&\Leftrightarrow n\leqslant Y(n)\leqslant \sum_{k=1}^{n}n^{1/k}=n+o(n)\\&\Rightarrow X(n)\in\Theta(n).\end{split}\end{equation}$$

I don't know what to do with $Z(n)$ because I will get $\displaystyle\sum_{k=1}^{n}n^k$.