Question

Let k be a positive integer.
Show that 1^k + 2^k +... + n^k is O(n^k+1)

Answer 1

@ganeshie8 we like this proof

Answer 2

$$1^k+2^k+\dots+n^k\le\underbrace{n^k+n^k+\dots+n^k}_{n\text{ terms}}=n^{k+1}$$

Answer 3

since we can bound \(1^k+\dots+n^k\) above by \(n^{k+1}\) always (and bound below by \(0\)) then it follows that \(1^k+\dots+n^k\in O(n^{k+1})\)