# Finding Asymptotic Bounds

I don't know how to find tight (aka asymptotic) bounds for a function. Consider the function $$f(n)=\sum_{k=1}^nk^r$$

Do you mean $f(n)$, or perhaps $f(r)$? There is no $x$ on the right-hand-side, so $f(x)$ would be constant. –  robjohn May 14 '12 at 11:05
Some trivial estimates: first of all, let's use $f(n)$ instead of $f(x)$ since there are no $x$'s so far. Let us Denote $a(x) = x^r$ for $x\geq 1$. Then your formula is $$f(n):=\sum\limits_{k=1}^n a(k).$$ In the case when $r\geq 0$ we obtain that $a(x)$ is a non-decreasing function and hence $$\int\limits_{n-1}^na(x)\mathrm dx\leq a(n)\leq\int\limits_n^{n+1}a(x)\mathrm dx\leq a(n+1)$$ for all $n\geq 2$. As a result, $$a(1)+\int\limits_1^n a(x)\mathrm dx\leq\sum\limits_{k=1}^n a(k)\leq a(1)+\int\limits_1^{n+1} a(x)\mathrm dx$$ where $a(1) = 1$. Clearly, for integrals you have $$\int\limits_1^n x^r\mathrm dx = \frac{n^{r+1}-1}{r+1}$$ so $$1+\frac{n^{r+1}-1}{r+1}\leq f(n)\leq \frac{(n+1)^{r+1}-1}{r+1}$$ for all $n\geq 1$.