-1
$\begingroup$

Suppose that $p>0$ and $n>0$ is a natural number. How do I prove that

$$ \sum_{k=1}^n k^p = 1^p + 2^p + \dots +n^p \sim \frac{1}{p+1}n^{p+1}=\Theta(n^{p+1})$$

for $n \rightarrow \infty$?

$\endgroup$

closed as off-topic by David Richerby, Kyle Jones, Evil, Yuval Filmus, fade2black Jan 3 '18 at 20:45

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question does not appear to be about computer science, within the scope defined in the help center." – David Richerby, Kyle Jones, Evil, Yuval Filmus, fade2black
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ This seems to be a question about pure mathematics with no computational content, so I'm voting to close as off-topic. $\endgroup$ – David Richerby Dec 27 '17 at 18:30
2
$\begingroup$

You can show this by estimating the sum using an integral: on the one hand, $$ \sum_{k=1}^n k^p = \int_1^{n+1} \lfloor x \rfloor^p \, dx \leq \int_1^{n+1} x^p \, dx = \left. \frac{x^{p+1}}{p+1} \right|_1^{n+1} = \\\frac{(n+1)^{p+1}-1}{p+1} = \frac{n^{p+1}}{p+1} + O(n^p). $$ On the other hand, $$ \sum_{k=1}^n k^p = \int_0^n \lceil x \rceil^p \, dx \geq \int_0^n x^p \, dx = \left. \frac{x^{p+1}}{p+1} \right|_0^n = \frac{n^{p+1}}{p+1}. $$ You can also calculate the sum explicitly, using Faulhaber's formula.

$\endgroup$
2
$\begingroup$

$$\sum_{k=1}^{n}k^p<\sum_{k=1}^{n}\color{red}n^p=n\times n^p=n^{p+1}$$

$\endgroup$
  • $\begingroup$ However, this misses the constant in front of $n^{p+1}$. $\endgroup$ – Yuval Filmus Dec 30 '17 at 10:12

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