Question

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

Answer 1

like I answered on the other one: $$\sum_{j=1}^n j^k\le \sum_{j=1}^n n^k\text{ since }1\le j\le n$$and $$\sum_{j=1}^n n^k=n^k\sum_{j=1}^n1=n^k\cdot n=n^{k+1}$$ so since we can bound our sum above by \(n^{k+1}\) always it follows that $$\sum_{j=1}^n j^k\in O(n^{k+1})$$