1

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.

user127.0.0.1
  • 7,267
EggHead
  • 667
  • 1
    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 '14 at 21:44
  • @AntonioVargas, $C_1\le\frac{1}{n}[(\frac{1}{n})^k +...+(\frac{n}{n})^k]$ – EggHead Jan 24 '14 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 '14 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 '14 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 '14 at 22:48
  • @StevenStadnicki you're right \frac{1}{n} is a lower bound but not the greatest lower bound which was my mistake. Hence, Did's answer – EggHead Jan 24 '14 at 23:00

1 Answers1

1

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

Did
  • 279,727