1

...where k is a positive integer. The Big Oh case is not so hard. But how do I show that $1^k+2^k+\cdots+n^k$ is $\Omega (n^{k+1})$?

Community
  • 1
Isa Hassen
  • 179

2 Answers2

3

Suppose $n$ is even. Bound each term of the "upper half" from below by $(n/2)^{k}$. You have $n/2$ such terms. For a lower bound of $(n/2)(n/2)^{k}= n^{k+1}/2^{k+1}$.

The general case can be handled in the same way.

quid
  • 42,135
1

$\frac{n^{k+1}}{k+1}=\int\limits_{0}^nx^kdx\leq1^k+2^k+\dots +n^k\leq \int\limits_{1}^{n+1}x^{k}dx=\frac{(n+1)^{k+1}-1}{k+1}$.

It is clear all monic polynomials of degree $k+1$ are asymptotically equivalent, so the result follows.

Asinomás
  • 105,651
  • Can you explain why $\int\limits_{0}^nx^kdx\leq1^k+2^k+\dots +n^k$ ? I'm stumped after many hours and asking my math peers. – Isa Hassen Feb 08 '16 at 22:16
  • because $1^k+2^k+3^k+\dots+n^k=\int\limits_0^n\lceil x \rceil ^kdx\leq\int\limits_0^n x ^kdx$ – Asinomás Feb 08 '16 at 23:55