 mersenneforum.org Range of Inequality
 Register FAQ Search Today's Posts Mark Forums Read 2007-08-07, 16:24 #1 davar55   May 2004 New York City 2×2,099 Posts Range of Inequality For what (natural number) values of n is this inequality true: 99n + 100n > 101n   2007-08-07, 17:22   #2
R.D. Silverman

Nov 2003

26·113 Posts Quote:
 Originally Posted by davar55 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.   2007-08-07, 17:35 #3 alpertron   Aug 2002 Buenos Aires, Argentina 133310 Posts 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   2007-08-07, 17:42   #4
R.D. Silverman

Nov 2003

26×113 Posts Quote:
 Originally Posted by alpertron 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.   2007-08-07, 20:28 #5 ewmayer ∂2ω=0   Sep 2002 República de California 2×59×83 Posts 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.]   2007-08-07, 21:06 #6 alpertron   Aug 2002 Buenos Aires, Argentina 31·43 Posts 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   2007-08-07, 21:48   #7
ewmayer
2ω=0

Sep 2002
República de California

2·59·83 Posts 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 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  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post a1call Miscellaneous Math 4 2017-02-08 09:25 Primeinator Math 13 2009-11-05 17:30 thechickenman Lone Mersenne Hunters 4 2008-12-01 10:45 edorajh Lone Mersenne Hunters 2 2003-12-31 16:04 tom11784 Lone Mersenne Hunters 1 2003-08-29 18:56

All times are UTC. The time now is 23:58.

Tue Oct 27 23:58:55 UTC 2020 up 47 days, 21:09, 2 users, load averages: 2.52, 2.01, 1.82