We had a course on elementary number theory in a postgraduate course. Our instructor started the course with arithmetic functions. He introduced Euler's summation formula which states that if $f$ is continuously differentiable, then for $0<y<x$, we have $$\sum\limits_{y<n<x}f(n)=\int_y^x f(t)dt+\int_y^x f'(t)\{t\}dt-f(x)\{x\}+f(y)\{y\}.$$
He also introduced big-O notation which is defined as follows:
Let $g(x)>0$, then $f(x)=O(g(x))$ if $|f(x)|\leq Mg(x)$ for all $x\geq x_0$.
Then he gave us an exercise to prove the following:
$$\sum\limits_{n\leq x} \frac{1}{n^k}=O(x^{1-k}),\;\; k>1$$ and $$\sum\limits_{n\leq x}n^k=\frac{x^{k+1}}{k+1}+O(x^k),\;\; k\geq 0.$$
I have no idea how to prove this, could someone give me a detailed proof and explanation of the two results?
The first one is wrong... (Typo?)... because the LHS is bounded below by $1$ but $x^{1-k}\to 0$ as $x\to\infty$.
Heuristically,$\sum_{n=1}^xn^k$ resembles $\int_0^xt^kdt.$ Comparison of sums with integrals is a common technique.
For $k\ge 0$ and $x\in\Bbb N$ we have $$\frac {x^{k+1}}{k+1}-\sum_{n=1}^xn^k=\int_0^xt^kdt-\sum_{n=1}^x\int_{n-1}^nn^kdt=$$ $$=\sum_{n=1}^x\int_{n-1}^nt^kdt-\sum_{n=1}^x\int_{n-1}^nn^kdt=$$ $$=\sum_{n=1}^x\int_{n-1}^n(x^k-n^k)dt.$$ Now $0\ge \int_{n-1}^n(x^k-n^k)dt>\int_{n-1}^n((n-1)^k-n^k)dt=(n-1)^k-n^k.$
Therefore $$0\ge \frac {x^{k+1}}{k+1}-\sum_{n=1}^xn^k>$$ $$>\sum_{n=1}^x(n-1)^k-n^k= -x^k.$$