I would like to know what is the true output, and what is the way of solving it? To me, I have got solution to be exact as Q1.
- Consider the following “proof” that $$ 1^k+2^k+\cdots+n^k\in O(n ^{k+1}). $$ proof. Let $f(n)=1^k+2^k+\cdots+n^k$ and $g(n)=n^{k+1}$. Then we have that $$ \eqalign{ \lim_{n\to\infty}\dfrac{f(n)}{g(n)} & = \lim_{n\to\infty}\dfrac{1^k+2^k+3^k+\cdots+n^k}{n^{k+1}} \\ & = \lim_{n\to\infty}\left[\dfrac{1^k}{n^{k+1}}+\dfrac{2^k}{n^{k+1}}+\dfrac{3^k}{n^{k+1}}+\cdots+\dfrac{n^k}{n^{k+1}}\right] \\ & = \lim_{n\to\infty}\dfrac{1^k}{n^{k+1}}+\lim_{n\to\infty}\dfrac{2^k}{n^{k+1}}+\lim_{n\to\infty}\dfrac{3^k}{n^{k+1}}+\cdots+\lim_{n\to\infty}\dfrac{n^k}{n^{k+1}} \\ &=0+0+0+\cdots+0 \\&=0. } $$
Therefore, $f(n)\in O(g(n))$.
$\qquad$ (a) The proof is wrong: run through the proof for $k-1$ and indicate why it fails.
$\qquad$ (b) Prove (using the definition) that $$1^k+2^k+\cdots+n^k\in O(n^{k+1}).$$
If you can use calculus, use the fact that $$\int_2^{n + 1} {{{(x - 1)}^k}dx} \leqslant {1^k} + {2^k} + \cdots + {n^k} \leqslant \int_1^{n + 1} {{x^k}dx} $$
(since function $x^k$ is increasing) to get limits that clearly show the order of the sum.