Proving $1^k+2^k+ \dots + n^k = O(n^{k+1})$ I have to prove that : $1^k+2^k+ \dots + n^k = O(n^{k+1})$, where $k \in \mathbb{Z}^+$ . I followed a technique different from the book , and I want to check if my way is correct. I approach the problem using Induction.
Let $P(n)$ be the statement "$1^k+2^k+ \dots + n^k = \sum_{i = 1}^ni^k =  O(n^{k+1})$ ".
Induction basis: I will show that $P(1)$ is true. That equals: $1^k = O(1^{k+1})$. In other words, I have to prove that $\lim_{x\to \infty}\frac{1^x}{1^{x+1}} = L \geq 0$.
$\lim_{x\to \infty}\frac{1^x}{1^{x+1}} = \lim_{x\to \infty}\frac{1^x}{1^{x}1^1} = 1 \in \mathbb{R}$ so the Induction basis is proved.
Induction step: Let $P(l)$ be true, for some $l>1$. I will prove that $P(l) \rightarrow P(l+1)$.
As $P(l)$ is true, that means that $\sum_{i=1}^{l} = O(l^{k+1})$. Let's prove that $P(l+1)$ is true. I want to prove that $\sum_{i=1}^{l+1} = O((l+1)^{k+1})$ is true, so: $1^k + 2^k + \dots + l^k + (l+1)^k = O((l+1)^{k+1})$
I have to prove that: $\lim_{x \to \infty}\frac{ 1^x + 2^x + \dots + l^x + (l+1)^x  }{(l+1)^{x+1}} = L \geq 0$
$
\begin{align}
\\
\lim_{x \to \infty}\frac{ 1^x + 2^x + \dots + l^x + (l+1)^x  }{(l+1)^{x+1}} 
 &= \lim_{x \to \infty}\frac{ 1^x + 2^x + \dots + l^x + (l+1)^x  }{(l+1)^x \times (l+1)} \\
& = \frac{1}{l+1} \lim_{x \to \infty} \frac{ 1^x + 2^x + \dots + l^x + (l+1)^x  }{(l+1)^{x}} \\
& = \frac{1}{l+1} [\lim_{x \to \infty} (\frac{1}{l+1})^x+ (\frac{2}{l+1})^x + \dots (\frac{l}{l+1})^x + 1 ]
\end{align}$ .
As $l > 1 \rightarrow l+1 > 2$ the above limit equals $0 + 0 + \dots + 0 + 1 = 1$. So $\frac{1}{1+l} \in \mathbb{R}$, and thus the induction step is proven, and the proof is concluded. $\blacksquare$
Is this way correct?
 A: Why not simply
$$\sum_{j=1}^nj^k\le \sum_{j=1}^nn^k =n\cdot n^k=n^{k+1}$$
A: The claim $$\sum_{k=1}^n k^r=O(n^{r+1})\qquad(n\to\infty)\tag{1}$$ cannot be proven by induction with respect to $n$, because $n$ is a dummy variable which is burnt after the claim has been spoken out, because we have said $n\to\infty$ within the claim. That $(1)$ is true for $n:=5$ is absurd: Write $5$ for $n$ in the formula, and you obtain
$$1^r+2^r+3^r+4^r+5^r=O(5^{r+1})\qquad(5\to\infty)\ .$$
We all know from high school that
$$\eqalign{\sum_{k=1}^n k^0&=n=O(n^1),\cr
\sum_{k=1}^n k^1&={n(n+1)\over2}=O(n^2),\cr
\sum_{k=1}^n k^2&={n(n+1)(2n+1)\over6}=O(n^3)\ .\cr}$$
Following this one could maybe set up an induction proof with respect to the variable $r$ in $(1)$.
A: I suppose $ k $ is a fixed integer, that was the first thing you've said. So we wanna prove this : $$ \sum_{p=1}^{n}{p^{k}}=\underset{\overset{n\to +\infty}{}}{\mathcal{O}}\left(n^{k+1}\right) $$
If we wanted to use induction, we must do it on $ k $, not on $ n $ which is the variable of the asymptotic developpement. I suggest to following method though :
Notice that, for any $ k\in\mathbb{N} $ : $$ \frac{1}{n^{k+1}}\sum_{p=1}^{n}{p^{k}}=\frac{1}{n}\sum_{p=1}^{n}{\left(\frac{p}{n}\right)^{k}}\underset{n\to +\infty}{\longrightarrow}\int_{0}^{1}{x^{k}\,\mathrm{d}x}=\frac{1}{k+1} $$
Thus : $$ \sum_{p=1}^{n}{p^{k}}=\underset{\overset{n\to +\infty}{}}{\mathcal{O}}\left(n^{k+1}\right) $$
That is due to the fact that any convergent sequence is bounded, since $ \left(\frac{1}{n^{k+1}}\sum\limits_{p=1}^{n}{p^{k}}\right)_{n} $ converges, $ \frac{1}{n^{k+1}}\sum\limits_{p=1}^{n}{p^{k}}=\underset{\overset{n\to +\infty}{}}{\mathcal{O}}\left(1\right) $, hence the result.
A: Each term in the sum is $\le n^k$, and there are $n$ terms.  So clearly
$$1^k + 2^k + \ldots + n^k \le n \cdot n^k = n^{k+1}.$$
Your proof appears to correctly show that the sum grows as $n^{k+1}$ as $k\rightarrow\infty$ for each fixed value of $n$.  This isn’t what you were asked to show: you want to prove that the sum grows (no faster than) $n^{k+1}$ as $n\rightarrow\infty$ for each fixed $k$..... and in general you can’t conclude one of these facts from the other.  (For instance, which grows faster, $n^k$ or $k^n$?  The answer depends on which variable is fixed and which is becoming large.)
