Why does the equation follow?

Question

From the inequalities $$\sum_{k=1}^N\int_{k-1 }^k v^r dv\leq\sum_{1\leq t\leq N}t^r\leq \sum_{k=1}^N\int_{k }^{k+1} v^r dv $$ it follows $$\sum_{1\leq t\leq N}t^r=\int_{1}^N v^r dv+\mathcal{O}(N^r) .$$ I do not understand the term $\mathcal O(N^r)$ . Should it not be $\mathcal O(N^{r+1})=\int_N^{N+1}v^r dv?$

Answer 1

That term is actually of the order $(N+1)^{r+1} - N^{r+1} \asymp N^r$. \begin{align} \frac{1}{r+1} = \int_0^1 v^r \, dv \le \sum_{t=1}^N t^r - \int_1^N v^r \, dv &\le\int_N^{N+1} v^r \, dv \\ &= \frac{1}{r+1}((N+1)^{r+1} - N^{r+1} ) \\ &= \frac{1}{r+1} \sum_{k=1}^{r} \binom{r+1}{k} N^k \\ &= O(N^r) \end{align}

Answer 2

I would use another identity: rewriting the inequalities as $$\int_{0}^N v^r\,\mathrm dv=\int_{0}^1 v^r\,\mathrm dv+\int_{1}^N v^r\,\mathrm dv\leq\sum_{1\leq t\leq N}t^r\leq \int_{1}^{N+1}v^r\,\mathrm dv=\int_1^N v^r\,\mathrm dv+\int_N^{N+1}v^r\,\mathrm dv, $$ whence $$\int_{0}^1 v^r\,\mathrm dv \leq\sum_{1\leq t\leq N}t^r-\int_{1}^N v^r\,\mathrm dv\leq \int_{N}^{N+1} v^r\,\mathrm dv. $$ Now, by a high-school formula \begin{align} \int_{N}^{N+1}\!\!\! v^r\,\mathrm dv&=\frac{(N+1)^{r+1}-N^{r+1}}{r+1}=\frac{N+1-N}{r+1}\bigl((N+1)^r+(N+1)^{r-1}N+\dots+(N+1)N^{r-1}+N^r\bigr)\\ &=\frac1{r+1} \,O(N^r)\quad\text{since each}\quad (N+1)^{r-i}N^i\sim_\infty N^r \\ &=O(N^r). \end{align}