Big O notation for summation

Question

Consider the summation $$S(n)=1^c+2^c+3^c+...+n^c,$$ where c is some fixed positive integer.

(a) Show that $S(n)$ is $O(n^{c+1})$

I did this part the following way, $S(n)$ is $O(n^{c+1})$ because $n^c \leq n^{c+1}$ for $n \geq 1$. Is this correct? Can someone concur?

The second part is giving me trouble

(b) Show that $S(n)$ is $\Omega(n^{c+1})$

Do i do this the same way i solved the first part except now $n\leq 1$

Answer 1

For a), use the fact that $\sum_{k=1}^n k^c < \sum_{k=1}^n n^c = n^{c+1}$ for $n \ge 2$. This fact proves that $S(n) = O(n^{c+1})$, since you have found an $n_0$ and $M$ for which the inequality $S(n) < Mn^{c+1}$ always holds for $n \ge n_0$.

You can't just use the fact $n^c \le n^{c+1}$ and argue that the other terms are dominated, since it is exactly this you are supposed to prove.

Answer 2

Hint: Using the Stolz–Cesàro theorem prove $$\lim_{n\to \infty}\frac{S(n)}{n^{c+1}}=\frac1{c+1},$$ which answers both your questions.