# Prove that $f(n)$ is in $\Theta(g(n))$

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.

-
How do you go from $C_1 n^{k+1} \leq 1^k + 2^k + \cdots + n^k$ to $C_1 \leq \frac{1}{n}$? –  Antonio Vargas Jan 24 at 21:44
@AntonioVargas, $C_1\le\frac{1}{n}[(\frac{1}{n})^k +...+(\frac{n}{n})^k]$ –  EggHead Jan 24 at 21:56
@EggHead The term inside your square brackets is not $\leq 1$; in fact, it's clearly greater than 1 (since the last term is 1). –  Steven Stadnicki Jan 24 at 22:15
@StevenStadnicki $C_1\le\frac{1}{n}\le\frac{1}{n}[(\frac{1}{n}^k+...+(\frac{n}{n})^k)]$ –  EggHead Jan 24 at 22:45
@EggHead You still haven't shown the first of those inequalities. You know that $C_1\leq \frac1n[((\frac1n)^k+\ldots+(\frac nk)^k)]$ and that $\frac1n$ is less than this same sum, but that doesn't yield $C_1\leq\frac1n$ at all. –  Steven Stadnicki Jan 24 at 22:48

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$.