Show that $\displaystyle 1^k + 2^k + 3^k + ... + (n-1)^k + n^k $ is ORDER $\displaystyle n^(k+1).$
(where k is a positive integer)
The function of x...
$\displaystyle f(x) = x^{k} + (x-1)^{k} + (x-2)^{k} + \dots + (x-n+1)^{k}$ (1)
... is a polynomial of degree k and the coefficient of the term of degree k is $\displaystyle n$, i.e. is...
$\displaystyle f(x)= n\cdot x^{k} + \dots \rightarrow f(x)=\mathcal {O} \{x^{k}\} $ (2)
If we set in (2) $\displaystyle x=n$ we have...
$\displaystyle f(n)= n^{k+1} + \dots \rightarrow f(n)=\mathcal {O} \{n^{k+1}\} $ (3)
Kind regards
$\displaystyle \chi$ $\displaystyle \sigma$