1

Prove by induction that: $$n^n \le (n!)^2\ \ , \ \forall n\in \mathbb{N}^+$$

my attempt was: $$(n+1)^{n-1} \le n^n \le (n!)^2\ \ , \ \forall n\in \mathbb{N}^+$$ which comes down to $$\ \ \ \ \ (n+1)^{n-1} \le n^n \ , \ \forall n\in \mathbb{N}^+$$ which i still can't figure out a proof for.

David
  • 13
  • 2
  • How would knowing $(n+1)^{n-1} \le n^n$ help you in any way to show that $n^n \le (n!)^2$. Showing that some things are less than X can not in any way tell us whether different things are larger than X. – fleablood Jul 19 '17 at 19:57
  • I wouldn't do that by induction, personally. It's a lot easier to show that $m(n-m)\geq n$ for $1\leq m\leq n$, and thus the squared factorial is larger. – Arthur Jul 19 '17 at 20:02
  • @fleablood I know by inductive hypothesis that $n^n \le (n!)^2\ $ so we have to prove that $(n+1)^{n+1}\le (n+1)! \ $ which equals to $(n+1)^2 (n+1)^{n-1}\le (n+1)^2(n!)^2 \ $ simplified $(n+1)^{n-1}\le (n!)^2 \ $ so proving the stricter condition that $(n+1)^{n-1}\le n^n$ implies the inductive step. – David Jul 20 '17 at 12:05
  • I suppose you could prove that by induction. If course if it is true you have $(2n)^0 \le 2n-1 \le (2n-1)^2 \le ...... \le (n+2)^{n-2} \le (n+1)^{n-1} \le n^n$ which may or may not be useful and may or may not be easy. Actually that mean it'd suffice to show $m^{n+1} \ge (m+1)^n$ – fleablood Jul 20 '17 at 18:21

2 Answers2

3

Hint: look at the ratios

$$\frac{(n+1)^{n+1}}{n^n} \\ \frac{(n+1)!^2}{(n!)^2}.$$

Upon checking the base case (easy), induction tells us that it is enough to show the first ratio is smaller than the second. But these two both simplify nicely.

Ian
  • 101,645
0

To prove $$\ \ \ \ \ (n+1)^{n-1} \le n^n \ , \ \forall n\in \mathbb{N}^+$$ it is equivalent to prove $$ \frac{1}{n+1}(1+\frac{1}{n})^n\le1,\ \forall n\in \mathbb{N}^+$$ which is a decreasing function of $n$. As $n$ increases from 1 to infinity, $\frac{1}{n+1}$ goes to $0$ and $(1+\frac{1}{n})^n$ goes to constant $e$.

The last argument can be proved as follows: Let $a_n=\frac{1}{n+1}(1+\frac{1}{n})^n$, and take the ratio of series terms $$\frac{a_{n+1}}{a_n}=\frac{\frac{1}{n+1}(1+\frac{1}{n})^n}{\frac{1}{n+2}(1+\frac{1}{n+1})^{n+1}}=\left(\frac{(n+2)n}{(n+1)(n+1)}\right)^n=\left(\frac{n^2+n}{n^2+2n+1}\right)^n<1.$$

MathArt
  • 1,053
  • It is trivial to prove that $\frac{1}{n+1}(1+\frac{1}{n})^n\le1,\ \forall n\in \mathbb{N}^+$ by taking log of it: – MathArt Jul 20 '17 at 07:41
  • Correction: by taking log is not directly helping the proof but for the transformation of the expression forms. – MathArt Jul 20 '17 at 08:28
  • This conclusion is very useful. The variants are: $(1+\frac{1}{n})^n\le n+1$ or $(n-1)\ln(n+1)-n\ln{n}\le0$, $\forall n\in \mathbb{N}^+$ – MathArt Jul 20 '17 at 08:34
  • thank, i've come to the same conclusion yesterday that since $(1+\frac{1}{n})^n\le 4$ and for every $n \le 3$ the statement is true – David Jul 20 '17 at 11:12
  • 1
    Thanks for the answer,
    I've come to the same conclusion yesterday that since $(1+\frac{1}{n})^n\le n+1$ for all $n \le 3$ and $(1+\frac{1}{n})^n \le 4\ $ is true $\ \forall n\in\mathbb{N} \ $.
    As for the conclusion i needed it to prove that $\ \lim_{n\to \infty} \sqrt[n]{n!} = \infty$ (i didn't know you could only edit for 5 min and shift+enter would post)     – David Jul 20 '17 at 11:41