0
$\begingroup$

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

How would I find tight upper/lower bounds for this. Please help :-(

  • 0
    Sorry, I meant f(n)2012-05-14

1 Answers 1

1

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

  • 0
    Okay, I'm following your answer but it seems like a puzzle I wouldn't put together on my own... But I have a question. So for the upper limit I can say that sum(k^r)<=sum(n^r) and theres an easy upper limit. Is there also a way to do this for the lower limit?2012-05-14