0

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)$ ?

Cindy
  • 35
  • 2
    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 05 '21 at 13:10
  • @leoli1 $(n+1)^{n+1} = (n+1)^n(n+1)^1$. How you obtain the result above? – Cindy Jan 05 '21 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 05 '21 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 05 '21 at 13:47
  • $(n+1)^{n}\geq n+1.$ – leoli1 Jan 05 '21 at 13:54

1 Answers1

1

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