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

  • 2
    $\begingroup$ 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). $\endgroup$ – richrow Jan 5 at 13:10
  • $\begingroup$ @leoli1 $(n+1)^{n+1} = (n+1)^n(n+1)^1$. How you obtain the result above? $\endgroup$ – Cindy Jan 5 at 13:14
  • $\begingroup$ $(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) $\endgroup$ – leoli1 Jan 5 at 13:17
  • $\begingroup$ @leoli1 still I don't get the last step. Where did you take $n\cdot(n+1)^n + n + 1$? $\endgroup$ – Cindy Jan 5 at 13:47
  • $\begingroup$ $(n+1)^{n}\geq n+1.$ $\endgroup$ – 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$


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.