# Proof by induction: inequalities

I need to prove by induction the following inequality: $$\sum_{i=1}^{n} i \leq n^n \text{ for all } n \geq 1$$

Base case is proved. In the inductive case I can sum both sides of the inequality by $$(n+1)$$ as $$\sum_{i=1}^{n+1} i = \sum_{i=1}^{n} i + (n+1)$$ Then? How can I obtain $$\sum\limits_{i=1}^{n+1} i \leq (n+1)^{n+1}$$ from $$\sum\limits_{i=1}^{n} i + (n+1) \leq n^n + (n+1)$$ ?

• By the way, it's easier to prove it without induction: $\sum\limits_{i=1}^{n}i\le \sum\limits_{i=1}^{n}n=n^2\le n^n$ for $n\ge 2$. For $n=1$ the inequality is trivial (ans it's an equality). – richrow Jan 5 at 13:10
• @leoli1 $(n+1)^{n+1} = (n+1)^n(n+1)^1$. How you obtain the result above? – Cindy Jan 5 at 13:14
• $(n+1)^{n+1}=(n+1)^n(n+1)=n\cdot (n+1)^n+(n+1)^n\geq n\cdot(n+1)^n+n+1$ (there was typo in my earlier comment) – leoli1 Jan 5 at 13:17
• @leoli1 still I don't get the last step. Where did you take $n\cdot(n+1)^n + n + 1$? – Cindy Jan 5 at 13:47
• $(n+1)^{n}\geq n+1.$ – leoli1 Jan 5 at 13:54

$$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$$
$$n^n \ge \sum_{i=1}^{n} i$$ for some n
$$(n+1)^{n+1} \ge n^{n+1}=n^n \cdot n$$ and $$\sum_{i=1}^{n+1} i = \frac{(n+1)(n+2)}{2}=\frac{n(n+1)}{2}\frac{(n+2)}{n}$$
You just have to prove that $$n \ge \frac{(n+2)}{n}$$ for $$n \ge 2$$