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 am looking to prove that for every fixed value of $k$, $$ n^{k+1}= O(1^k + 2^k + \cdots + n^k) $$

I have already proved that $1^k + 2^k +\cdots + n^k =O(n^{k+1})$ but I don't know how to make the jump to proving the opposite is true. I was thinking that induction might be the way to go (i.e. adding $(n+1)^k$ to each side and simplifying, but the way I did it didn't make anything obvious).

Any help will be very much appreciated.

Thanks, Nolan

share|improve this question
1  
Can you please define precisely $f=O(g)$? I think you are using a non-standard definition. The standard one says that $f=O(g)$ if the quotient $|f/g|$ is bounded from above by a constant. –  Siminore Sep 24 '12 at 8:53

2 Answers 2

Lower bound without integrals: $$\sum_{i=1}^n i^k \ge \sum_{i=\lfloor n/2 \rfloor }^n i^k \ge \frac{n-1}{ 2} \left( \frac{n-1}{ 2} \right)^k =\Omega(n^{k+1})$$

share|improve this answer

$$n\cdot n^k\geqslant\sum_{i=1}^ni^k\geqslant\sum_{i=1}^n\int_{i-1}^it^k\,\mathrm dt=\int_{0}^nt^k\,\mathrm dt=\frac{n^{k+1}}{k+1}.$$ Hence, indeed $n^{k+1}=O(1^k+2^k+\cdots+n^k)$ when $n\to\infty$, and in fact, $$ 1^k+2^k+\cdots+n^k=\Theta(n^k).$$

share|improve this answer
    
This makes partial sense to me, but can you explain what the final integral means or implies? I'd like to understand this stuff, and I've been trying to make sense of it for quite a long time. –  BadAtGraphs Sep 24 '12 at 9:02
    
The integral of $t\mapsto t^k$ on $[0,n]$? Well, this is just the value at $n$ minus the value at $0$ of any primitive of $t^k$, for example $t^{k+1}/(k+1)$. The result is that your sum is between $n^{k+1}/(k+1)$ and $n^{k+1}$, hence the asymptotics you are after. –  Did Sep 24 '12 at 9:05
    
I've been looking at it further, and it makes more sense after the formatting edit and the n*n^k term at the beginning. Thanks so much for your help! –  BadAtGraphs Sep 24 '12 at 9:06
    
The crucial step is that, for each $i$, $i^k\geqslant t^k$ for every $t$ in $[i-1,i]$ hence $i^k$ is at least the integral of $t^k$ on the interval $[i-1,i]$, divided by the length $1$ of the interval. –  Did Sep 24 '12 at 9:07

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.