Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 :-(

share|improve this question
    
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
    
Sorry, I meant f(n) –  canton May 14 '12 at 11:07

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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? –  canton May 14 '12 at 10:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.