# Proof by Induction of an inequality with a sum

Prove using induction on k that for any natural number 'n' $$\sum_{i=1}^n i^k \le \frac{n^k(n+1)}{2}$$ I know I first need to start off with a base case, which I think will be $k=0$ $$\sum_{i=1}^n i^0 \le \frac{n^0(n+1)}{2}$$ But I'm not quite sure how to prove this base case, honestly. And beyond that, I know I need an induction hypothesis and induction step where I increase k by 1. I'm a bit lost on how to solve this problem. If anyone could point me in the right direction, I'd be grateful.

## 1 Answer

Hint (without induction): for $k=1$ the equality holds:

$$\sum_{i=1}^n \;i \;=\; \frac{n(n+1)}{2} \quad \iff \quad \sum_{i=1}^n \;\frac{i}{n} \;=\; \frac{n+1}{2}$$

Note that $\;\cfrac{i}{n} \le 1\,$ for $1 \le i \le n\,$, which implies $\;\left(\cfrac{i}{n}\right)^k \le \cfrac{i}{n}\;$ for all $\;k \ge 1\,$. Then:

$$\frac{1}{n^k}\;\sum_{i=1}^n \;i^k \;=\; \sum_{i=1}^n \left(\frac{i}{n}\right)^k \;\le\; \sum_{i=1}^n \frac{i}{n} \;=\; \frac{n+1}{2}$$