wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Double Inequality
        
(Message started by: Barukh on Jan 17^th, 2006, 8:25am)

Title: Double Inequality
Post by Barukh on Jan 17^th, 2006, 8:25am

Find at least one natural number n for which the following double inequality holds:

1/2 * 6/7 * … * (5n+1)/(5n+2) < 1/2006 < 5/6 * 10/11 * … * (5n+5)/(5n+6)

Title: Re: Double Inequality
Post by Barukh on Jan 21^st, 2006, 9:06am

Sorry, but these days problems posted (especially in Easy section) leave the first page too fast... ;D

Title: Re: Double Inequality
Post by Eigenray on Jan 22^nd, 2006, 1:50am

Well, it's easy to show such an n exists. Let P_n be the LHS, and Q_n the RHS. Note Q_n > 5/3 P_n, so if P_n > 1/2006, then Q_n+1 > 5/3 (5n+10)/(5n+11) /2006 > 1/2006.

Finding n is a big trickier.
[hideb]First note -log(1-x) > x for x>0, so
-log P_n > log 2 + 1/7 + ... + 1/(5n+2)
> log 2 + 1/5 [int]₇⁵ⁿ⁺⁷ dx/x
= 1/5 log((5n+7)*32/7) > 1/5 log(4(5n+7))
> log 2006 when (5n+7) > 1/4 * 2006⁵.
On the other hand,
[int] -log(1-1/x)dx = log(x-1) + log (1-1/x)^-x,
and since the second term is decreasing in x,
[int]_a^b -log(1-1/x)dx < log((b-1)/(a-1)).
Since the integrand is also decreasing, it follows that
-log Q_n < log(6/5) + 1/5 [int]₆⁵ⁿ⁺⁶ -log(1-1/x)
< log(6/5) + 1/5 log((5n+5)/5)
< log 2006 when (5n+5) < 5(5/6*2006)⁵.
Thus both inequalities are satisfied when
(1/4) 2006⁵ < 5(n+1) < (5⁶/6⁵) 2006⁵.
As x^1/x is decreasing, 5⁶/6⁵ > 1 (in fact, > 2). So the difference between the two sides above is huge, and we may safely take, say,
n = [(1/10)*2006⁵].[/hideb]

I spent quite a while trying to get nice bounds I could easily compute by hand. At one point I had it down to noting e^121/120/6 < 1/2 (using, for example, -log(1-x) < x + 11/20 x² for x<1/11), but it still didn't feel quite right to me.

Title: Re: Double Inequality
Post by SWF on Jan 23^rd, 2006, 5:25pm

Rewriting trying to get 5*n in denominators gives: (5n+1)/(5n+2) = (1+1/(5n)) / (1+2/(5n)). After shifting index and being careful with n=0, (5n+5)/(5n+6) becomes 5m/(5m+1)= 1/(1+1/(5m)).

I used the following inequalities with 0<x<1:
x - x²/2 < ln(1+x) < x
[sum] for n= 1 to N of (1/n^2) < [pi]^2/6
gamma + ln(N) < [sum] for n= 1 to N of (1/n) < gamma + ln(N+1)

gamma is Euler's constant= 0.5772156649...

Taking ln() and using the inequalities gives

1003⁵*exp( [pi]²/15 - gamma ) < N < 2006⁵*exp(-gamma) - 2

or 1.1e15 < N < 1.82e16

Title: Re: Double Inequality
Post by Barukh on Jan 24^th, 2006, 2:07am

Hmm... The solution I am aware of does give an exact value...

Hint: [hide]Could you use even more inequalities[/hide]?

Title: Re: Double Inequality
Post by Aryabhatta on Jan 24^th, 2006, 10:21am

I think this should be moved to the medium section!

Title: Re: Double Inequality
Post by SWF on Jan 24^th, 2006, 9:08pm

Barukh, what do you mean by a solution with an exact value? Do you mean it give the exact value for the highest and lowest possible values of n, or do you mean there is a value that happens to be the same for both the upper and lower limit? I was trying to find a wide range of n that work. One way to improve on the range is to use x/(1+x/2) < ln(1+x). The following gives a fairly simple (although I had trouble discovering it) way to bring the upper and lower bounds together:

If you note that for n>0 the 1/2*...*(5n+1)/(5n+2) term is always less than 1/(10n)^.2, and the 5/6*...*(5n+5)/(5n+6) is always greater than 1/(10n)^.2 (show by induction), upper and lower bounds on n are exactly what Eigenray gave: 2006^5/10. One inequalty says n must be greater than 2006^5/10 and the other says n must be less, but 2006^5/10 is not an integer, so this is not quite right, but should not be hard to fix for sticklers.

Title: Re: Double Inequality
Post by Eigenray on Jan 24^th, 2006, 9:42pm

on 01/24/06 at 02:07:09, Barukh wrote:

Hmm... The solution I am aware of does give an exact value...

In fact, for any 0 < r < 1/2, we have
1/2 * 6/7 * … * (5n+1)/(5n+2) < r < 5/6 * 10/11 * … * (5n+5)/(5n+6),
where n=floor[ 1/(5r⁵) ].

Taking r=1/2006, this is exactly (2006⁵-1)/5.

Is that better?

Title: Re: Double Inequality
Post by Barukh on Jan 24^th, 2006, 11:19pm

on 01/24/06 at 21:42:36, Eigenray wrote:

Yes, it is. :D

But probably I ought to analyze your original post better.