mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2007-08-07, 16:24   #1
davar55
 
davar55's Avatar
 
May 2004
New York City

3×1,409 Posts
Default Range of Inequality

For what (natural number) values of n is this inequality true:

99n + 100n > 101n
davar55 is offline   Reply With Quote
Old 2007-08-07, 17:22   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

25×233 Posts
Default

Quote:
Originally Posted by davar55 View Post
For what (natural number) values of n is this inequality true:

99n + 100n > 101n
Is there something more to this problem beyond a trivial calculation?

We can get an immediate approximation to the answer by observing that
(1 - a)^n ~ 1 - n*a for very small a. Whence (1-a)^n + (1-b)^n > 1
==> 2 - na - nb > 1 for a,b ~ .01 yields n ~ 50

Indeed, n < 49 is the answer.
R.D. Silverman is offline   Reply With Quote
Old 2007-08-07, 17:35   #3
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

23·3·5·11 Posts
Default

It appears that there is a problem with the immediate approximation.

99^n + 100^n > 101^n

(99/101)^n + (100/101)^n > 1

(1-2/101)^n + (1-1/101)^n > 1

Using Bob's approximation:

(1 - 2n/101) + (1 - n/101) > 1

2 - 3n/101 > 1

n < 101/3 = 33.667 Ouch!

It appears that the O(n^2) term is very high to discard it.

Last fiddled with by alpertron on 2007-08-07 at 17:38
alpertron is offline   Reply With Quote
Old 2007-08-07, 17:42   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

25×233 Posts
Default

Quote:
Originally Posted by alpertron View Post
It appears that there is a problem with the immediate approximation.

99^n + 100^n > 101^n

(99/101)^n + (100/101)^n > 1

(1-2/101)^n + (1-1/101)^n > 1

Using Bob's approximation:

(1 - 2n/101) + (1 - n/101) > 1

2 - 3n/101 > 1

n < 101/3 = 33.667 Ouch!

It appears that the O(n^2) term is very high to discard it.
The difference is that I took a ~ b and not a ~ 2b.
R.D. Silverman is offline   Reply With Quote
Old 2007-08-07, 20:28   #5
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

3×3,769 Posts
Default

I took a slightly different tack to obtain the same first-order estimate as Bob:
Code:
	[x-1]^n + x^n > [x+1]^n

==>	[x+1]^n - [x-1]^n < x^n

[x+1]^n = x^n + n*x^(n-1) + [n^2/2]*x^(n-2) + [n^3/2]*x^(n-3) + ...

[x-1]^n = x^n - n*x^(n-1) + [n^2/2]*x^(n-2) - [n^3/2]*x^(n-3) + ...

==>	[x+1]^n - [x-1]^n = 2*{n*x^(n-1) + [n^3/2]*x^(n-3) + ... } < x^n

==>	2*{n*x^(n-1) + [n^3/2]*x^(n-3) + ... } < x^n
x >> n: keep only 1st term of LHS expansion ==> 2n < x, if x = 100, gives n ~= 50 as breakover point.

Actual breakover occurs between n=48 and 49, so not bad, despite the fact that x ~= 2n means n is *not* small vs x. [That kind of "luck" is common in these kinds of regular-perturbation type problems, however.]
ewmayer is offline   Reply With Quote
Old 2007-08-07, 21:06   #6
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

52816 Posts
Default

The number 50 is actually a second-order estimate because you consider the error in O((1/x)^3). The first-order estimate is 33.67 as I showed above.

A small correction: [n^3/2]*x^(n-3) should be replaced by [n^3/6]*x^(n-3)

Last fiddled with by alpertron on 2007-08-07 at 21:06
alpertron is offline   Reply With Quote
Old 2007-08-07, 21:48   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

3×3,769 Posts
Default

I should have said "leading-order" - as you point out, since I am using what amounts to the analog of a central-diffference scheme [using the terminology of finite-difference approximations], that leads to a 2nd-order scheme.

Quote:
Originally Posted by alpertron View Post
A small correction: [n^3/2]*x^(n-3) should be replaced by [n^3/6]*x^(n-3)
Indeed. Copy/paste/modify ... the fastest way to propagate errors throughout one's analysis.

Anyway, retaining the leading *two* LHS terms in my analysis above gives the breakover point as

2*n*x^(n-1) + (n^3/3)*x^(n-3) = x^n

Plugging in x=100 and using a Newton-Raphson iteration [with f(n) as the function whose zeros we seek and n as the independent variable w.r.to which we take derivatives] converges to n = 48.14056..., which is quite close to the exact value of n = 48.2275...

Last fiddled with by ewmayer on 2007-08-07 at 22:03
ewmayer is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Bonse's inequality a1call Miscellaneous Math 4 2017-02-08 09:25
Exponential Inequality Primeinator Math 13 2009-11-05 17:30
OK, how can we get a range now? thechickenman Lone Mersenne Hunters 4 2008-12-01 10:45
Available range for TF to 2^60? edorajh Lone Mersenne Hunters 2 2003-12-31 16:04
getting a range? tom11784 Lone Mersenne Hunters 1 2003-08-29 18:56

All times are UTC. The time now is 17:29.

Mon Jul 13 17:29:42 UTC 2020 up 110 days, 15:02, 1 user, load averages: 1.45, 1.73, 1.71

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.