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

    ReplyDelete
  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

    ReplyDelete
  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

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

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

      Delete
  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.

    ReplyDelete
  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

    ReplyDelete
  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

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

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

    ReplyDelete
    Replies
    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

      Delete
  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

    ReplyDelete