**Source:**

Posted by Shubham Agarwal (B.Tech CSE, NIT Raipur) on his blog

**Problem:**

Prove the following inequality:

1/2 . 3/4 . 5/6 . .... 99/100 < 1/10

**Bonus:**Prove the generalized inequality:

1/2 . 3/4 . 5/6 . .... (2n-1)/2n < 1 / sqrt(2n)

3 different solutions posted in comments by sriram, chetan, dvdreddy, insomniac and sarat

Solution by Sriram and Chetan needs explanation. So, we have 2 different solutions by dvdreddy, insomniac and sarat.

**Update:**(12 Sep 2012)3 different solutions posted in comments by sriram, chetan, dvdreddy, insomniac and sarat

**Update: (**4 Feb 2013)Solution by Sriram and Chetan needs explanation. So, we have 2 different solutions by dvdreddy, insomniac and sarat.

Straightforward proof, by induction!!! for all n>=2

ReplyDeleteSay P1=(3/2)(5/4)…(97/96)(99/98) // Has 49 fractions

ReplyDeleteand P2=(2/1)(4/3)(6/5)…(98/97)(100/99) // Has 50 fractions

Now you can see P1*P2= 100 and you can see that P2 > P1 and so P2 > sqrt(100) = 10

and so 1/P2 < 1/10 which is the required result.

You can see that it can be easily extended to the general inequality.

Hope its correct.

Thanks,

Saratchand

correct solution Sarat. Thanks

DeleteThrough induction... it can be assumed right till n-1 cases since the base case is true, then we need to prove 1/sqrt(2n-2) . 2n-1/2n<1 / sqrt(2n) implying a^2<(a-1)*(a+1) which is trivial

ReplyDeletehow is a^2 < a^2 - 1? I think your final statement is false

DeleteI agree. Thanks for pointing that out Sriram. Can you please provide your induction argument please? Thanks

DeleteLHS = (2n Choose n)/4^n

ReplyDeleteStirling's formula will be used to simplify the LHS. In particular, [1] and [2] provide bounds in the form of a double inequality for n!

n! < sqrt(2*pi) n^(n + 0.5) e^(-n + 1/12n)

n! > sqrt(2*pi) n^(n + 0.5) e^(-n + 1/(12n + 1))

These bounds are motivated from the Stirling's formula. Since we want to prove an inequality, we can't directly use Stirling's formula as it's only an approximation.

Using these bounds, we have,

LHS

= (2n Choose n)/ 4^n

< [1/sqrt(2*pi)](2n)^(2n + 0.5) e^(-2n + 1/24n) n^(-2n -1) e^(2n -2/(12n + 1))

< [1/sqrt(pi*n)] e^(1/24n - 2/(12n+1))

< [1/sqrt(pi*n)] for n>=1

< [1/sqrt(2*n)] since pi > 2

DONE.

PEACE.

References.

[1] Robbins, H. "A Remark of Stirling's Formula." Amer. Math. Monthly 62, 26-29, 1955.

[2] Feller, W. "Stirling's Formula." §2.9 in An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed. New York: Wiley, pp. 50-53, 1968.

Can be done using the sterling's Approximation

ReplyDeletewhich also gives the lower and upper bounds

http://en.wikipedia.org/wiki/Stirling's_approximation

1/2 . 3/4 . 5/6 . .... (2n-1)/2n

can be written as below

(2n)! / (pow(2, 2n) * n! * n1)

now take log for the above expression

we get ln(2n!) - 2n ln2 - 2 * ln(n!)

now for 2n! use upper bound and n! use lower bound

We have 3 solutions to the problem :)

ReplyDeleteSolution 1 - Induction: Thanks Sriram and Chetan

Solution 2 - Stirling Approximation - Thanks dvdreddy and insomniac

Solution 3 - Elementary Math - Thanks Sarat

Correction. We do not have the induction solution by Sriram and Chetan

DeleteYou could use AM-GM to prove the same.

ReplyDeleteLet P be the product of 1/2, 3/4, ..., 2n-1/2n and S be their sum. AM-GM implies (S/n)^n > P.

Now, S = sum (2i-1/2) = n - H(n)/2 where H(n): nth harmonic sum

S/n = 1 - H(n)/2n < 1 - 1/2n since H(n) > 1

P < (S/n)^n < (1 - 1/2n)^n < 1/sqrt (2n)

Minor correction:

DeleteS = sum (2i-1/2i) and not sum (2i-1/2)

Please explain the statement (1 - 1/2n)^n < 1/sqrt (2n) in more detail. Thanks