0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.