I'm stuck on a difficult problem in my homework, I tried doing an induction proof but I got stuck on the inductive hypothesis.
The question is prove for all $k ∈ \mathbb{N}$ that $1^k+2^k+\ldots +n^k ∈ \mathcal{O}(n^{k+1})$.
I used induction on $k$, and the base case works out, but I have no clue how to simplify $1^{k+1}+2^{k+1}+\ldots+n^{k+1}$, or the right side $n^{k+2}$. I also considered using induction on $n$, but there's no way for me to simplify $(n+1)^{k+1}$.
On
I hope it can help you
If $k$ is a positive integer and replace each integer $1, 2, ..., n$ by $n$ We have
$$1^k+2^k+ .......+n^k ≤ n^k +n^k +...+n^k =n.n^k = n^{k+1}\qquad \text{for}\, n ≥ 1$$
Hence
$$f(n)=1^k+ 2^k+ .......+n^k \,\,\, \text{is} \,\,\,O(n^{k+1})$$
We can obtain the lower bound, throwing away the first half of the terms \begin{align} &1^k+2^k+ .......+n^k ≥ ⎡\frac{n}{2}⎤^ {k} +...+(n-1)^k +n^k \\ &\qquad\qquad\qquad\quad\,\,\,≥⎡\frac{n}{2}⎤^k+...+⎡\frac{n}{2}⎤^k+⎡\frac{n}{2}⎤^k \\ &\qquad\qquad\qquad\quad\,\,\,=⎡\frac{n+1}{2}⎤^k ⎡\frac{n}{2}⎤^k ≥ (\frac{n}{2})(\frac{n}{2})^k =\frac{n^{k+1}}{2^{k+1}}\\ &\\ \end{align}
So we can conclude that
$$f(n)=1^k+ 2^k+ .......+n^k \,\,\,\text{is} \,\,\, Ω (n^{k+1})$$
Hence
$$f(n)=1^k+ 2^k+ .......+n^k \,\,\,\text{is} \,\,\, Θ (n^{k+1})$$
The proof is actually much simpler than you think and doesn't need induction at all, I'll give you a hint:
$$\forall i<n: i^k < n^k$$