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

        riddles >> putnam exam (pure math) >> Inequality: A_(n+1)^(n+1) >= A_n^n * x_(n+1)
        
(Message started by: anonymous on Jun 11th, 2003, 5:42am)
Title: Inequality: A_(n+1)^(n+1) >= A_n^n * x_(n+1)
Post by anonymous on Jun 11th, 2003, 5:42am
Let x1,x2,x3,... be positive real numbers. For positive integer n, denote An=(x1+x2+...+xn)/n.

Use the inequaltiy (a+b)n >= an + nan-1b to prove that
(An+1)n+1 >= (An)n . xn+1

for all positive integer n.

// title modified by William Wu on 3:47 AM 8/31/2003; please use slightly more descriptive titles, thank you
Title: Re: Inequality: A_(n+1)^(n+1) >= A_n^n * x_(n+1)
Post by william wu on Aug 31st, 2003, 3:51am
an attempt at the solution: http://www.ocf.berkeley.edu/~wwu/riddles/inequality.pdf
Title: Re: Inequality: A_(n+1)^(n+1) >= A_n^n * x_(n+1)
Post by TenaliRaman on Sep 6th, 2003, 11:38pm
Following wu's approach and a bit of modification i arrived at this,

[edit]P.S -> the image looks a bit tarnished.hopefully its readable![/edit]
Title: Re: Inequality: A_(n+1)^(n+1) >= A_n^n * x_(n+1)
Post by Icarus on Sep 7th, 2003, 1:15pm

on 09/06/03 at 23:38:19, TenaliRaman wrote:
[edit]P.S -> the image looks a bit tarnished.hopefully its readable![/edit]


Unfortunately, no it is not. Can you recreate it using the new math symbolry?
Title: Re: Inequality: A_(n+1)^(n+1) >= A_n^n * x_(n+1)
Post by Pietro K.C. on Sep 7th, 2003, 1:52pm
The first thing I tried was Wu's approach, which is the most immediate, given the hint. I got to the same place as him, and also got stuck. But then I noticed that it is IMPOSSIBLE to demonstrate the theorem in this fashion, i.e. applying the hint in just such a manner. I'll try to show why.
[Below, n/n+1 wil denote n/(n+1), which, although correct, clutters the formulas with parentheses]

We both started by noticing that

An+1  =  (n/n+1) An + xn+1/(n+1)

and using the

(1) (a + b)n [ge] an + nan-1b

inequality on it in the obvious way. We both got

(2) An+1n+1  [ge]  (n/n+1)n+1Ann+1 + (n/n+1)nAnn xn+1.

To use this formula in the demonstratin that

(3) An+1n+1 [ge] Ann xn+1 ,

we would have to show that the right side of (2) is greater than, or equal to, the right side of (3).

But that is just not the case. See, unless b = 0 in (1), the left side is strictly larger than the right; however, there are cases where

An+1n+1 = Ann xn+1  exactly.

For instance, if all the xi are equal to the same positive constant c, then Ai = c for all natural i. Therefore, the needed inequality is false in general, and this particular use of the hint will get us nowhere.

I was able to demonstrate the formula without (1), and it turned out to be pretty simple. Is the requirement of using (1) part of the challenge? My proof is hidden below.
[hide]
Start by noticing that An+1 is the arithmetic mean of the set { An, ... , An, xn+1 }, where An appears n times. Using the well-known inequality between arithmetic and geometric means, we get

An+1 [ge] (Ann xn+1)1/(n+1), whence

An+1n+1 [ge] Ann xn+1.
[/hide]
Title: Re: Inequality: A_(n+1)^(n+1) >= A_n^n * x_(n+1)
Post by TenaliRaman on Sep 8th, 2003, 10:08am
hmm lemme see,
is this any helpful in proving the inequality??(i tried some way of relating this RHS with the original RHS but haven't found anyway so far.....)
Title: Re: Inequality: A_(n+1)^(n+1) >= A_n^n * x_(n+1)
Post by Aryabhatta on Jun 8th, 2004, 3:46pm

on 09/07/03 at 13:52:03, Pietro K.C. wrote:
I was able to demonstrate the formula without (1), and it turned out to be pretty simple. Is the requirement of using (1) part of the challenge? My proof is hidden below.

Start by noticing that An+1 is the arithmetic mean of the set { An, ... , An, xn+1 }, where An appears n times. Using the well-known inequality between arithmetic and geometric means, we get

An+1 [ge] (Ann xn+1)1/(n+1), whence

An+1n+1 [ge] Ann xn+1.


I guess the motivation for proving this inequality was to prove that AM [ge] GM, as AM [ge] GM follows immediately from it by induction on n.


We can prove the inequality An+1n+1 [ge] Ann xn+1 under the assumption that x1 [le] x2 [le] ... [le] xn [le] xn+1

If we assume that the xi's are non-decreasing, it follows that An+1 [ge] An. The case when An+1 = An is easy. So assume An+1 > An.

Let An+1/An = 1 + h. h > 0.

By applying (a+b)[supn] [ge] a[supn] + nan-1b, we get

(An+1/An)n+1 = (1+h)n+1 [ge] 1 + (n+1)h = 1 + (n+1)(An+1/An - 1) = xn+1/An which implies

An+1n+1 [ge] Ann xn+1

This proves AM [ge] GM for arbitrary positive xi's since we can arrange them in nondecreasing order and relabel them as y1 [le] y2 [le] ... [le] yn [le] yn+1. For these yi's we have just shown that AM [ge] GM. This implies AM [ge] GM  for the xi's as (y1,...,yn+1) is just a permutation of (x1,...,xn+1).

Incidentally, once we have proved AM [ge] GM, we can use this to show that(using Pietro's post)
An+1n+1 [ge] Ann xn+1  for any positive xi's i.e. without the restriction that x1 [le] x2 [le] ... [le] xn [le] xn+1


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board