Suppose $f(n) = 1^k + 2^k + \ldots + n^k \;$ and $\; g(n) = n^{k+1}.\;$ Prove that $\;f(n)\in \Theta(n^{k+1})$.
My understanding is that we have to find $C_1, C_2 \gt 0$ such that:
$$C_1(n^{k+1})\le 1^k + 2^k + ... + n^k \le C_2(n^{k+1})$$
which means: $$C_1 \le \frac{1}{n}\le \frac{f(n)}{g(n)} \le 1 \le C_2$$
But that means $C_1=0$ which does not satisfy $C_1\gt0$
I'd like to know where I went wrong.
The $n$ terms in the sum defining $f(n)$ are each at most $n^k$ hence $f(n)\leqslant n\cdot n^k=g(n)$. The $n/2$ last terms in $f(n)$ are each at least $(n/2)^k$ hence $f(n)\geqslant (n/2)\cdot (n/2)^k=g(n)/2^{k+1}$.
To sum up, consider $C_1=1/2^{k+1}$ and $C_2=1$.