Binomial inequality

Art of Problem Solving

AoPS Online

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

College Math Topics in undergraduate and graduate studies

Topics in undergraduate and graduate studies

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Binomial inequality

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

323 posts

#1 h Feb 2, 2025, 5:08 PM

Y by

Is it true? $\sum_{k=0}^n (2k-1)!!{n\choose k} >\left(\frac{2n}{e}\right)^n\sqrt{2e}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

928 posts

#2 h Feb 5, 2025, 2:40 PM

Y by

Let us use induction to prove this inequality is true for all $n \in \mathbb{N}$ :

CASE I ( $n=1$ ):

$\sum_{j=0}^{1}(2j-1)!! {1 \choose j} > \frac{2}{e}\sqrt{2e} \Rightarrow 2 > 2\sqrt{\frac{2}{e}} \Rightarrow$ TRUE.

CASE II ( $n=k$ ):

$\sum_{j=0}^{k}(2j-1)!! {k \choose j} > \left(\frac{2k}{e}\right)^{k}\sqrt{2e} \Rightarrow$ ASSUME TRUE.

CASE III ( $n=k+1$ ):

Making the Stirling Approx substitution $n! = \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$ yields:

$\sum_{j=0}^{k}(2j-1)!! {k \choose j} > \frac{2^{k}k!}{\sqrt{2\pi k}} \cdot \sqrt{2e}$ ;

or $\frac{2(k+1)}{\sqrt{(k+1)/k}} \cdot \sum_{j=0}^{k}(2j-1)!! {k \choose j} > \frac{2^{k}k!}{\sqrt{2\pi k}} \cdot \frac{2(k+1)}{\sqrt{(k+1)/k}} \cdot \sqrt{2e}$ ;

or $\frac{\sum_{j=0}^{k+1}(2j-1)!! {k+1 \choose j}}{\sum_{j=0}^{k+1}(2j-1)!! {k+1 \choose j}} \cdot \left[ \frac{2(k+1)}{\sqrt{(k+1)/k}} \cdot \sum_{j=0}^{k}(2j-1)!! {k \choose j} \right]> \frac{2^{k+1}(k+1)!}{\sqrt{2\pi (k+1)}} \cdot \sqrt{2e}$ ;

or $\sum_{j=0}^{k+1}(2j-1)!! {k+1 \choose j} \cdot \left[2\sqrt{k(k+1)} \cdot \frac{\sum_{j=0}^{k}(2j-1)!! {k \choose j}}{\sum_{j=0}^{k+1}(2j-1)!! {k+1 \choose j}}\right]> \frac{2^{k+1}(k+1)!}{\sqrt{2\pi (k+1)}} \cdot \sqrt{2e}$ ;

or $\sum_{j=0}^{k+1}(2j-1)!! {k+1 \choose j} > \sum_{j=0}^{k+1}(2j-1)!! {k+1 \choose j} \cdot \left[2\sqrt{k(k+1)} \cdot \frac{\sum_{j=0}^{k}(2j-1)!! {k \choose j}}{\sum_{j=0}^{k+1}(2j-1)!! {k+1 \choose j}}\right] > \left[ \frac{2(k+1)} {e} \right]^{k+1} \cdot \sqrt{2e}$ ;

or $\sum_{j=0}^{k+1}(2j-1)!! {k+1 \choose j} > \left[\frac{2(k+1)} {e} \right]^{k+1} \cdot \sqrt{2e} \Rightarrow$ TRUE.

This post has been edited 10 times. Last edited by Mathzeus1024, Feb 6, 2025, 10:30 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

323 posts

#3 h Feb 5, 2025, 3:47 PM

Y by

Very good ! for CASE I and CASE II in your demonstration.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

323 posts

#4 h Feb 6, 2025, 8:23 AM

Y by

$\frac{2(k+1)}{\sqrt{(k+1)/k}}$ $\text{[math]}$ is not $\text{[math]}$ $2\sqrt{\frac{k}{k+1}}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

928 posts

#6 h Feb 6, 2025, 10:31 AM

Y by

Snoop76 wrote:

$\frac{2(k+1)}{\sqrt{(k+1)/k}}$ $\text{[math]}$ is not $\text{[math]}$ $2\sqrt{\frac{k}{k+1}}$

Correction made above.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

323 posts

#7 h Feb 6, 2025, 4:15 PM • 1 Y

Y by Filipjack

This is not a valid proof. You've just copying a crap of chatgpt. Somebody from stuff need to report this user.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1576 posts

Etkan

#8 h Feb 7, 2025, 2:27 AM • 2 Y

Y by anduran, smartvong

Snoop76 wrote:

This is not a valid proof. You've just copying a crap of chatgpt. Somebody from stuff need to report this user.

No. Zeus is a legitimate user, and has the right to be wrong (as well as everyone else).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

323 posts

#9 h Feb 7, 2025, 6:54 AM • 1 Y

Y by Filipjack

Ok but this AI generated "demonstrations" shoud be verified when you use them dozens of time.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

928 posts

#10 h Feb 7, 2025, 2:11 PM

Y by

Snoop76 wrote:

This is not a valid proof. You've just copying a crap of chatgpt. Somebody from stuff need to report this user.

Excuse me, Sir or Ma'am. If you have a different solution that does not involve induction (which is a viable tool in Discrete Math), then please share it with the AoPS Community at large.

For the record, I am a retired Principal Engineer from Microsoft, and I do not appreciate the accusation above.

Good day.

This post has been edited 1 time. Last edited by Mathzeus1024, Feb 7, 2025, 2:15 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

323 posts

#11 h Mar 3, 2025, 8:07 PM

Y by

Hint: $\displaystyle\int_0^\infty \frac{e^{-t/2}(1+t)^{n}}{\sqrt{t}}\,dt =\sqrt{2\pi}(2n-1)!!>\left(\frac{2n}{e}\right)^n2\sqrt{\pi}\sqrt\frac{n}{n+1/2}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

323 posts

#12 h Apr 3, 2025, 11:51 AM

Y by

For the left part we use the $\frac{(2n-1)!!}{(2n)!!} \leq\frac{(2k-1)!!}{(2k)!!}$ inequality for $k \leq n$ .

So we have $\text{[math]}$ $\sum_{k=0}^n (2k-1)!!{n\choose k}>\sum_{k=0}^n \frac{(2k)!!}{(2n)!!}{n\choose k}(2n-1)!!=\sum_{k=0}^n \frac{1}{2^k\cdot k!}(2n-1)!!$ .

using $\sum_{k=0}^n \frac{1}{2^k\cdot k!}>\sqrt{e}- \frac{1}{2^n\cdot n!}$ inequality from $\sqrt{e}$ expansion results:

$\sum_{k=0}^n (2k-1)!!{n\choose k}>\left(\sqrt{e}- \frac{1}{2^n\cdot n!}\right)(2n-1)!!$

However this inequality is too weak, so in order to get it stronger we use the summation until the term $n-2$ .

$\text{[math]}$ $\sum_{k=0}^{n} (2k-1)!!{n\choose k}>\sum_{k=0}^{n-2} \frac{(2k)!!}{(2n)!!}{n\choose k}(2n-1)!!+\sum_{k=n-1}^{n} (2k-1)!!{n\choose k}$ or

$\sum_{k=0}^{n} (2k-1)!!{n\choose k}>\sum_{k=0}^n \frac{1}{2^k\cdot k!}(2n-1)!!-\frac 3 2(2n-1)!!+n(2n-3)!!+(2n-1)!!$ or

$\sum_{k=0}^{n} (2k-1)!!{n\choose k}>(2n-1)!!\left(\sqrt{e}- \frac{1}{2^n\cdot n!}-\frac 1 2+\frac{n}{2n-1}\right)$

For the right part we create a stronger inequality as well, wich includes the term $(2n-1)!!$ .

We use here the Robbins inequality: $\mathrm e^{1/(12n+1)} \leq \frac{n!}{\sqrt{2\pi n}\cdot(\frac n{\mathrm e})^n} \leq \mathrm e^{1/(12n)}$ (Stirling's formula with two terms, see Wikipedia).

$(2n-1)!!=\frac{(2n)!}{2^n \cdot n!}=\sqrt{2} \cdot \left(\frac{2n}{e}\right)^n\left(1-\frac 1 {24n}+O(n)\right)$ and using $\frac 1 {12n}>\frac 1 {24n}$ results:

$\sqrt{e}(2n-1)!!\left(1+\frac 1 {12n}\right)>\sqrt{2e}\left(\frac{2n}{e}\right)^n$

Now we only have to prove that:

$(2n-1)!!\left(\sqrt{e}- \frac{1}{2^n\cdot n!}-\frac 1 2+\frac{n}{2n-1}\right)>\sqrt{e}(2n-1)!!\left(1+\frac 1 {12n}\right)$ wich is true after a few calculations ( for $n>2$ ).

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a