Which side do I apply AM-GM on?

n!n≥n\sqrt[n]{n!} \geq \sqrt{n}

Prove the above for all positive integers nn.

  • Try to give a non-inductive, non-calculus proof
#Algebra

Note by Sharky Kesa
5 years, 2 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list
  • bulleted
  • list

1. numbered
2. list
  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai−1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 ∑i=13 \sum_{i=1}^3
\sin \theta sin⁡θ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Try to give a non-inductive, non-calculus proof

So I will give an inductive, calculus-requiring proof.

Lemma 1: (1+1n)n≤e\left( 1 + \frac{1}{n} \right)^n \le e for all positive integer nn.

One way to prove it is to observe that 1+1n≤1+22n+14n2=(1+12n)21 + \frac{1}{n} \le 1 + \frac{2}{2n} + \frac{1}{4n^2} = \left( 1 + \frac{1}{2n} \right)^2, thus by induction,

(1+1n)n≤(1+12n)2n≤(1+14n)4n≤…≤lim⁡k→∞(1+12kn)2kn=lim⁡n→∞(1+1n)n=e\displaystyle\begin{aligned} \left(1 + \frac{1}{n} \right)^n &\le \left(1 + \frac{1}{2n} \right)^{2n} \\ &\le \left(1 + \frac{1}{4n} \right)^{4n} \\ &\le \ldots \\ &\le \lim_{k \to \infty} \left(1 + \frac{1}{2^k n} \right)^{2^k n} \\ &= \lim_{n \to \infty} \left(1 + \frac{1}{n} \right)^n \\ &= e \end{aligned}

Lemma 2: e<3e < 3

e=10!+11!+12!+13!+14!+15!+16!+…<1+11+12+14+18+116+132+…=1+2=3\displaystyle\begin{aligned} e &= \frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} + \frac{1}{5!} + \frac{1}{6!} + \ldots \\ &< 1 + \frac{1}{1} + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \frac{1}{32} + \ldots \\ &= 1 + 2 \\ &= 3 \end{aligned}

Now, the claim n!n≥n\sqrt[n]{n!} \ge \sqrt{n} is equivalent to (n!)2≥nn(n!)^2 \ge n^n. We will prove this by induction. The base cases are n=1,2,3n = 1, 2, 3 in which it is true. Now suppose that it's true for some n≥3n \ge 3, and we'll prove the claim for n←n+1n \gets n+1.

((n+1)!)2=(n!)2⋅(n+1)2≥nn⋅(n+1)2≥nn⋅(n+1)⋅eby Lemma 2, because $n \ge3 > e$≥nn⋅(n+1)⋅(1+1n)nby Lemma 1=(n+nn)n⋅(n+1)=(n+1)n⋅(n+1)=(n+1)n+1\displaystyle\begin{aligned} ((n+1)!)^2 &= (n!)^2 \cdot (n+1)^2 \\ &\ge n^n \cdot (n+1)^2 \\ &\ge n^n \cdot (n+1) \cdot e & \text{by Lemma 2, because \$n \ge 3 > e\$} \\ &\ge n^n \cdot (n+1) \cdot \left( 1 + \frac{1}{n} \right)^n & \text{by Lemma 1} \\ &= \left(n + \frac{n}{n} \right)^n \cdot (n+1) \\ &= (n+1)^n \cdot (n+1) \\ &= (n+1)^{n+1} \end{aligned}

Ivan Koswara - 5 years, 2 months ago

We have to prove (n!)2≥nn(n!)^2 \ge n^n. Instead of proving it using Sterling's approximation or induction here is a solution on AM-GM. I found a nice form of (n!)2(n!)^2 recently. (n!)2=[1⋅n][2⋅(n−1)]…[n⋅1](n!)^2=[1 \cdot n][2 \cdot (n-1)]\ldots[n \cdot1](there are nn terms). Now, for some variable mm, such that 1≤m≤n1 \le m \le n we have m(n−m+1)≥nm(n-m+1) \ge n. The result follows.

A Former Brilliant Member - 5 years, 2 months ago

Log in to reply

Wise solution!

Nihar Mahajan - 5 years, 2 months ago

Nice solution

Anirudh Chandramouli - 5 years, 2 months ago

Why is it that for a variable mm
1≤m≤n1\leq m\leq n is m(n−m+1)≥n m(n-m+1)\geq n ?

Upamanyu Mukharji - 5 years, 2 months ago

Log in to reply

Take n=m+kn=m+k where k≥0k \ge 0. The inequality simplifies to m(k+1)≥m+km(k+1) \ge m+k or mk+m≥m+kmk+m \ge m+k or m≥1m \ge 1 which is true.

A Former Brilliant Member - 5 years, 2 months ago

Log in to reply

@A Former Brilliant Member – OK.. Thanks!

Upamanyu Mukharji - 5 years, 2 months ago

n!n≥n\sqrt[n]{n!} \geq \sqrt{n}

n!≥nn{n!} \geq {\sqrt{n}}^n

(n)⋅(n−1)⋅(n−2)⋅⋯⋅(1)≥nn(n) \cdot (n-1) \cdot (n-2) \cdot \dots \cdot (1) \geq {\sqrt{n}}^n

(n)(1)⋅(n−1)(1+1)⋅(n−2)(1+2)⋅⋯⋅(n+12)(n−12)≥nn(n)(1) \cdot (n-1)(1+1) \cdot (n-2)(1+2) \cdot \dots \cdot (\frac{n+1}{2})(\frac{n-1}{2}) \geq {\sqrt{n}}^n or (n)(1)⋅(n−1)(1+1)⋅(n−2)(1+2)⋅⋯⋅(n2)≥nn(n)(1) \cdot (n-1)(1+1) \cdot (n-2)(1+2) \cdot \dots \cdot (\frac{n}{2}) \geq {\sqrt{n}}^n

We note that (n-k)(1+k) > n for all -1<k<n+1. So the result follows. By the way, i was sniped by Svatejas Shivakumar.

Aloysius Ng - 5 years, 2 months ago

Log in to reply

Ninja'ed haha tfs

Nihar Mahajan - 5 years, 2 months ago

Well what about n-1?

Oscar Oquelí - 5 years, 2 months ago
×

Problem Loading...

Note Loading...

Set Loading...