# CSE Blog - quant, math, computer science puzzles

Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

## Sep 11, 2012

### Inequality Problem

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)

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.

#### 13 comments:

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

2. Say P1=(3/2)(5/4)…(97/96)(99/98) // Has 49 fractions
and 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

1. correct solution Sarat. Thanks

3. Through 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

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

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

4. LHS = (2n Choose n)/4^n

Stirling'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.

5. Can be done using the sterling's Approximation
which 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

6. We have 3 solutions to the problem :)

Solution 1 - Induction: Thanks Sriram and Chetan
Solution 2 - Stirling Approximation - Thanks dvdreddy and insomniac
Solution 3 - Elementary Math - Thanks Sarat

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

7. You could use AM-GM to prove the same.

Let 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)

1. Minor correction:
S = 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

8. a/b < a+1/b+1

1/2.3/4.5/6.....99/100 < 2/3.4/5.6/7......100/101

multiplying both sides by 1/2.3/4.5/6.....99/100
sqare(1/2.3/4.5/6.....99/100) < 1/101<1/100