I want to prove that $\sum_{i=1}^n{i^k}=O(n^{k+1})$ for all integers $k\geq1$. I'm attempting to prove this using mathematical induction over $n$. Here's what I've got:
For the base case, let $n=1$. We want to prove that there exists a constant $c>0$ such that $\sum_{i=1}^1{i^k}\leq cn^{k+1}$. Thus, we have that: $$ \sum_{i=1}^1{i^k}=1^k=1\leq{c}=c(1)^{k+1}, $$ which is true for any value for $k$ so long as $c\geq{1}$.
Now, suppose that $\sum_{i=1}^n{i^k}\leq cn^{k+1}$ for any integer $n$. We're now attempting to prove that such assumption implies that $\sum_{i=1}^{n+1}{i^k}\leq c(n+1)^{k+1}$. So, we have that: $$ \begin{aligned} \sum_{i=1}^{n+1}{i^k}&=\sum_{i=1}^{n}{i^k}+(n+1)^k\\ &\leq cn^{k+1}+(n+1)^k\\ &=c(n+1)^{k+1}\left[\left(\dfrac{n}{n+1}\right)^{k+1}+\dfrac{1}{c(n+1)}\right] \end{aligned} $$ ~~
And this is as far as I've got in the proof. I'm not really sure how I should continue this proof. I think the last relation is true as long as I can show that $$ (1)\qquad\left(\dfrac{n}{n+1}\right)^{k+1}+\dfrac{1}{c(n+1)}\geq1. $$
As far as my understanding goes, from here I should attempt to come up with a constant lower bound for $c$. However if I do algebra on (1), all I can come up with is with a bound for $c$ that depends on $n$; that is, $c$ wouldn't be a constant.
So my questions are the following:
- Is mathematical induction the appropiate approach for proving $\sum_{i=1}^n{i^k}=O(n^{k+1})$?
- If so, where did my proof went wrong? What corrections should I do in order to complete it?
- If not, what is a better approach?
Any corrections, hints or explanation will be appreciated.
EDIT: corrected some algebra and clarified what my questions were.
Surely the simplest way is
$$ \sum_{i=1}^n i^k \le \sum_{i=1}^n n^k = n^{k+1} $$