<a name="docA001">
2009-06-08-19-10 start
This file http://freeman2.com/tute0008.htm
is Freeman's reading notes. Although Freeman
always keep correct view point. But Freeman's
capability is limited, plus no one proofread
this file. Then you can still find wrong view
point. When read, please put question mark as
often as possible. If you suspect any view 
point wrong, please ask a math expert near by.

<a name="docA002">,<a name="textbook">
This file is a note for reading inequality
book written by Professor J. Michael Steele
The Cauchy-Schwarz Master Class  　★★★★★
Below use 'textbook' as abbreviation.
Freeman also read web pages online, and will 
indicate the source URL at discussion point.

<a name="docA003">
Freeman study mechanical engineering. 
Engineering mathematics do not teach 
inequality. Above book is first inequality
book. First time read, it was very hard.
Although high school time learned
  a*a + b*b >= 2*a*b
But this little knowledge do not help.

<a name="docA004">
This file follow textbook chapter section
order, but not continuous, Freeman skip 
those uncertain sections/problems.

This file first function is to learn 
inequality. Second function is to learn
how to use html code to write math 
equations.

<a name="docA005">　Index begin　Index this file
On 2009-01-27-10-08 Freeman accessed
the next page
http://www.sftw.umac.mo/~fstitl/10mmo/inequality.html
save as sftw.umac.mo_text_math_eqn_good.htm
Above page is the main reference for html
math equation.

In order to let reader to build  html math
equation, previous file tute0007.htm page 
end has math symbol and internal code.

This file third function is to display how
to draw curves in web page. The main engine
is XYGraph v2.3 - Technical Figures

Thank you for read Freeman's inequality page.
2009-06-08-19-47 stop

<a name="docA006">
2009-08-23-15-00 start
□　Exercise 1.14 solution

Exercise 1.14 problem (a) is solved by hint
Exercise 1.14 problem (b) is out of LiuHH's
reach. What is "cardinality of a set B⊂Z3" ?
Without clear understand the definition, 
LiuHH is unable to solve problem (b)
LiuHH major in mechanical engineering.
LiuHH is mathematics admirer and outsider.

<a name="docA007">
To solve problems in
The Cauchy-Schwarz Master Class
LiuHH's goal is to solve 50% of the exercise
problems. In reality, solve 40% is good enough.
Please do not be surprise that LiuHH skip some
text section, skip some problems.
2009-08-23-15-12 stop

<a name="ch05b001">　Index begin　Index this file

2009-11-22-18-09 start
■　Sequence order example

<a name="ch05b002">
Chapter five study Consequences of Order.
Here use simplest example to illustrate.
Assume sequence_a1=[2,1,3] ---eqn.AN001
 and   sequence_b1=[6,4,5] ---eqn.AN002
compare with
Assume sequence_a0=[1,3,2] ---eqn.AN003
 and   sequence_b0=[5,6,4] ---eqn.AN004
If order is not important (combination),
then 
eqn.AN001 and eqn.AN003 are same thing.
eqn.AN002 and eqn.AN004 are same thing.
But if order is important (permutation),
then they are different.

<a name="ch05b003">
The following use eqn.AN001 and eqn.AN002
as given. Apply addition (sum) and 
multiplication (product) to seq_a and seq_b 
get different results as following
Since we study sequence order. There are
three possible order relations.

<a name="ch05b004">
First, "same order", it mean 
re-write seq_a1=[2,1,3] as seq_a2=[3,2,1] ---eqn.AN005
re-write seq_b1=[6,4,5] as seq_b2=[6,5,4] ---eqn.AN006
seq_a2 and seq_b2 are same, both monotone
decrease. Or we can 
re-write seq_a1=[2,1,3] as seq_a3=[1,2,3] ---eqn.AN007
re-write seq_b1=[6,4,5] as seq_b3=[4,5,6] ---eqn.AN008
seq_a3 and seq_b3 are same, both monotone
increase.

<a name="ch05b005">
Second, "random order"
 seq_a1=[2,1,3] or  seq_a0=[1,3,2]
 seq_b1=[6,4,5] or  seq_b0=[5,6,4]
are both random order, no monotone 
decrease, no monotone increase.

<a name="ch05b006">　Index begin　Index this file
Third, "reverse order"
re-write seq_a1=[2,1,3] as seq_a4=[1,2,3] ---eqn.AN009
re-write seq_b1=[6,4,5] as seq_b4=[6,5,4] ---eqn.AN010
or
re-write seq_a1=[2,1,3] as seq_a5=[3,2,1] ---eqn.AN011
re-write seq_b1=[6,4,5] as seq_b5=[4,5,6] ---eqn.AN012
a4, b4 set is one increase, one decrease
a5, b5 set is one increase, one decrease
Either set is called "reverse order".

<a name="ch05b007">
Above is order, next is operation.
We can apply product first, sum second
or     apply sum first, product second

Two different operation and three possible
order method get different answer. Chapter
five find out the inequality among these
possibilities.

<a name="ch05b008">
"Same order product sum" mean use
same order two sequences
seq_a2=[3,2,1], seq_b2=[6,5,4]
do product first, then sum them.

"Rand order product sum" mean use
random order two sequences
seq_a1=[2,1,3], seq_b1=[6,4,5]
do product first, then sum them.

<a name="ch05b009">
"Revs order product sum" mean use
reverse order two sequences
seq_a4=[1,2,3], seq_b4=[6,5,4]
do product first, then sum them.

The result is
Same order product sum=3*6+2*5+1*4=32
Rand order product sum=2*6+1*4+3*5=31
Revs order product sum=1*6+2*5+3*4=28

<a name="ch05b010">
Above result suggest for 
product first and sum second method
Same order ≧ Rand order ≧ Revs order
Above negative number OK

Below is sum first and product second 
method. Must use non-negative numbers.

<a name="ch05b011">
Same order sum product=(3+6)*(2+5)*(1+4)=315
Rand order sum product=(2+6)*(1+4)*(3+5)=320
Revs order sum product=(1+6)*(2+5)*(3+4)=343

Second result suggest for 
sum first and product second method
Same order ≦ Rand order ≦ Revs order
If input sequence has negative elements
sum first and product second method the
inequality direction is not ensured.

Above is observation. Textbook chapter
five prove above results.
2009-11-22-18-51 here

<a name="ch05b012">
2009-11-22-19-00
monotone decrease or monotone increase has
no variation. But random order has many
variation. The study pay attention to 
random order / same order / reverse order
The study do not pay attention to different
random orders.
2009-11-22-19-03

<a name="ch05b013">　Index begin　Index this file
2009-11-22-19-07 start
■　Chebyshev's Order Inequality
Text page 76, problem 5.2
If two functions
 f: from real to real
 g: from real to real
are both non-decreasing.
Suppose pj≧0 , j=1,2,...,n ---eqn.AN013
 and p1+p2+...+pn=1 ---eqn.AN014
(pj≧0 and ∑pj=1 suggest pj is
 probability)
 if  x1≦x2≦...≦xn ---eqn.AN015
Prove next inequality exist

<a name="ch05b015">
2009-11-22-19-25 here
eqn.5.8 left side
 f(xk) product with one pk
 g(xk) product with one pk
eqn.5.8 right side
both f(xk) and g(xk) product with one pk
lost one pk, yet right side is greater
than left side.

<a name="ch05b016">
In the language of probability, eqn.5.8 
says that if X is a random variable for
which one has
 P(X=xk)=pk for k=1,2,...,n ---eqn.AN016
then
 E[f(X)]*E[g(X)] ≦ E[f(X)g(X)] ---eqn.AN017
here P(X) is probability function
 and E[f(X)] represent expectation.

<a name="ch05b017">
Problem given condition is that
both f(x) and g(x) are non-decreasing

Monotone increase function satisfy 
non-decreasing condition, for example
 f(x)=log(x) ---eqn.AN018
 f(x)=exp(x) ---eqn.AN019
both function increase value with 
increasing x

<a name="ch05b018">
Increase function value in domain, but
one point not-increase and not-decrease
function also qualify as non-decreasing
for example
 f(x)=(x-1)^3 ---eqn.AN020
at x=1, function (x-1)^3 is stationary.

<a name="ch05b019">
Now, assume xk≦xj ---eqn.AN021
then non-decreasing function must have
  f(xk)≦f(xj) ---eqn.AN022
  g(xk)≦g(xj) ---eqn.AN023
that is
  0≦-f(xk)+f(xj) ---eqn.AN024
  0≦-g(xk)+g(xj) ---eqn.AN025
then
  0≦{f(xj)-f(xk)}*{g(xj)-g(xk)} ---eqn.AN026
<a name="ch05b020">
Expand eqn.AN026 we find
  0≦f(xj)*g(xj)+f(xk)*g(xk)-f(xk)*g(xj)-f(xj)*g(xk)
or
  f(xk)*g(xj)+f(xj)*g(xk)
 ≦f(xj)*g(xj)+f(xk)*g(xk) ---eqn.5.11
Left  side f,g have different index j,k
Right side f,g have same index j,j or k,k

<a name="ch05b021">　Index begin　Index this file
Now multiply pjpk to eqn.5.11
and sum over 1≦j≦n and 1≦k≦n
eqn.5.11 left side become
  ∑[j,k=1,n]{f(xk)*g(xj)+f(xj)*g(xk)}*pjpk
 =∑[j,k=1,n]{f(xk)pk*g(xj)pj+f(xj)pj*g(xk)pk}
j and k both sum from 1 to n, both are
dummy index, we can choose one to switch
j and k role. Above equation become next
 =∑[j,k=1,n]{f(xk)pk*g(xj)pj+f(xk)pk*g(xj)pj}
 =2∑[j,k=1,n]{f(xk)pk*g(xj)pj}
<a name="ch05b022">
Next write j-sum and k-sum separately
get eqn.5.11 left side
 =2∑[k=1,n]{f(xk)pk}*∑[j=1,n]{g(xj)pj} ---eqn.AN027
This is textbook page 77, last line 
equation.

<a name="ch05b023">
eqn.5.11 right hand side sum become
 =∑[j,k=1,n]{f(xj)g(xj)pj*pk+f(xk)g(xk)pk*pj}
 =∑[j=1,n]{f(xj)g(xj)pj}*∑[k=1,n]{pk}
 +∑[k=1,n]{f(xk)g(xk)pk}*∑[j=1,n]{pj}
red terms are one, see eqn.AN014. Two
black terms are equal, j,k both dummy.
<a name="ch05b024">
then eqn.5.11 right side sum become
 =2∑[j=1,n]{f(xj)g(xj)pj} ---eqn.AN028
This is textbook page 78, second line 
equation. Put eqn.AN027 and eqn.AN028
into eqn.5.11 get eqn.5.8 Chebyshev's
Order Inequality.

<a name="ch05b025">
"lost one pk" is actually sit there 
with value one (red term). No one 
bother to write a one in a equation.
2009-11-22-20-36 stop

<a name="ch05b026">　Index begin　Index this file
2009-11-23-14-27 start
■　The Rearrangement Inequality
Text page 78, problem 5.3
Show that for each pair of ordered real
sequences
 -∞＜a1≦a2≦...≦an＜∞ ---eqn.AN029
and
 -∞＜b1≦b2≦...≦bn＜∞ ---eqn.AN030
and for each permutation
  σ: [n] → [n] ---eqn.AN031
one has

<a name="ch05b028">　Index begin　Index this file
2009-11-23-14-46 here
■　Numerical example, five elements
eqn.AN029 and eqn.AN030 tell us that the
given sequence_a and seq_b6 are ALREADY
SORTED in increase order. The following
use a numerical example to explain.
Assume
  seq_a6=[1,2,3,4,5]  ---eqn.AN032
  seq_b6=[6,7,8,9,10] ---eqn.AN033
we start from a pair of sorted, monotone
increase sequences. Each sequence has
five element. Here   n=5 ---eqn.AN034
k range from k=1 to k=n=5

<a name="ch05b029">
eqn.5.12 right end term
  ∑[k=1,5]{akbk}
  =a1b1+a2b2+a3b3+a4b4+a5b5
  =1*6+2*7+3*8+4*9+5*10=130 ---eqn.AN035
eqn.5.12 right end term
Same order sum product=130

<a name="ch05b030">
eqn.5.12 left end term
  ∑[k=1,5]{akbn-k+1}
  =a1b5-1+1+a2b5-2+1+a3b5-3+1+a4b5-4+1+a5b5-5+1
  =a1b5+a2b4+a3b3+a4b2+a5b1
  =1*10+2*9+3*8+4*7+5*6=110 ---eqn.AN036
eqn.5.12 left end term
Reverse order sum product=110

<a name="ch05b031">　Index begin　Index this file
■　What is σ: [n] → [n] ---eqn.AN031
function σ(i) create random order sequence.
Assume σ(i) defined as following
 σ(1)=3 ---eqn.AN037 (include five lines)
 σ(2)=2
 σ(3)=4
 σ(4)=5
 σ(5)=1
<a name="ch05b032">
then 
 bσ(1)=b3=8 ---eqn.AN038 (include five lines)
 bσ(2)=b2=7
 bσ(3)=b4=9  // find seq_b at eqn.AN033
 bσ(4)=b5=10
 bσ(5)=b1=6
Left column σ() is in 1,2,3,4,5 order.
Middle and right column are both random.

<a name="ch05b033">
eqn.5.12 middle term
  ∑[k=1,5]akbσ(k)
become
random product sum =
  a1bσ(1)+a2bσ(2)+a3bσ(3)+a4bσ(4)+a5bσ(5)
 =a1b3+a2b2+a3b4+a4b5+a5b1
 =1*8+2*7+3*9+4*10+5*6=119 ---eqn.AN039

<a name="ch05b034">　Index begin　Index this file
■　n*(n-1)/2 explained
The random permutation eqn.AN037 is 
not unique, there are many choices.
Permutation is exchange index number
between two elements in one sequence.
For example seq_b6 has five elements
  seq_b6=[6,7,8,9,10] ---eqn.AN033
exchange index between any two. 
<a name="ch05b035">
First element has n choices,
Second element has n-1 choices, 
(exclude first element)
Assume first element we choose is b3
index 3 is chosen out of [1,2,3,4,5]
five seq_b6 index.
<a name="ch05b036">
Assume second element we choose is
b5, index 5 is chosen out of 
[1,2,♫,4,5] four seq_b6 index. Second
index can not choose 3 which is first
choice. If we choose first and second
both to be index 3, b3 exchange with 
b3 ?! That is NO permutation. Not
allowed. 
<a name="ch05b037">
First  selection has  n=5  choices
Second selection has n-1=4 choices
Total is 5*4 or n*(n-1).
But b3 exchange with b5
and b5 exchange with b3
isn't it same thing? NO difference! 
then n*(n-1) divide by 2, get total
  n*(n-1)/2 different patterns.
2009-11-23-15-30 here

<a name="ch05b038">　Index begin　Index this file
2009-11-23-15-38
■　Prove Rearrangement Inequality
eqn.5.12 say that
 　seq_a and seq_b reverse order product_sum
 ≦seq_a and seq_b random order product_sum
 ≦seq_a and seq_b same order product_sum

<a name="ch05b039">
We prove above relation as following.
The permutation eqn.AN039 is very
different from same order eqn.AN035.
It is hard to handle many at one time.
Now exam two pair first. The following 
is "order-to-quadratic" process. We 
already applied "order-to-quadratic"
process at eqn.5.3 and at eqn.AN026
before.

<a name="ch05b040">
Assume
 a1≦a2 ---eqn.AN040
 b1≦b2 ---eqn.AN041
then
 0≦(a1-a2)(b1-b2)
expand get
 a1b2+a2b1≦a1b1+a2b2 ---eqn.AN042
Please pay attention to eqn.AN042
left  side a,b have different index 1,2
right side a,b have same index 1,1 or 2,2

<a name="ch05b041">
Above is two elements sequence.
How about general n element sequence?
  Sum(σ)=∑[k=1,n]{akbσ(k)} ---eqn.AN043
Here Sum(σ) is a function of permutation
pattern σ. Different σ get different sum.
One pattern σ is defined at eqn.AN037.

<a name="ch05b042">
A dull pattern is the identity permutation
 σ(1)=1 ---eqn.AN044 (include five lines)
 σ(2)=2
 σ(3)=3
 σ(4)=4
 σ(5)=5

<a name="ch05b043">
If σ is not the identity permutation, 
then there must exist some pair
   j ＜  k   such that
 σ(k)＜σ(j) ---eqn.AN045
please pay attention that j,k switch 
side relative to '＜' sign. 
For example in eqn.AN037 
         j =1 ＜ 5 = k
  σ(5)=σ(k)=1 ＜ 3=σ(j)=σ(1)

Such j,k pair (switch side relative to
 '＜' sign) is called inversion.

<a name="ch05b044">
If we switch the values of σ(k) and σ(j)
***** [σ(k) and σ(j) are index,
*****  bσ(k) and bσ(j) are value]
then the value of the associated sum will
increase or keep the same sum value. After
one inversion, one pair random-order-index
become same-order-index, and we know
 same-order-sum ≧ random-order-sum
Please see "order-to-quadratic" process
and see eqn.AN042 next line
 a1b2+a2b1≦a1b1+a2b2 ---eqn.AN042

<a name="ch05b045">　Index begin　Index this file
■　σ from order to random,
　　τ from random to order
〚 seq_b is in order, σ(i) make random 〛
We started at the assumption
[[
exist some pair j＜k such that
 σ(k)＜σ(j) ---eqn.AN045
]]
Because we need to know random ordered
product sum value, we created σ(k)＜σ(j)
represent random ordered sequence_b. 

<a name="ch05b046">
For sequence_b is initially random, or
the artificially random bσ(k)
We use permutation τ to put random
back to monotone increase order
  j ＜  k  :   bj ＜ bk ---eqn.AN048
σ(k)＜σ(j) : bσ(j)＜bσ(k) ---eqn.AN049
τ(j)＜τ(k) : bτ(j)＜bτ(k) ---eqn.AN050
(Please look at vertical j,k column
 and red text is out of order.)

<a name="ch05b047">
〚 seq_b is in order, σ(i) make random 〛
Now let us use permutation eqn.AN037
let j=1 and k=5 be two on-focus index.
let i=2 or 3 or 4 three other index.
Define permutation τ as following

<a name="ch05b048">
〚 seq_b is in order, σ(i) make random 〛
2009-11-23-18-08 add start
on-focus index, j=1 and k=5 
  j=1 ＜ k=5 → 6=b1 ＜ b5=10
above is monotone increase,
  index 1<5, value 6<10 this is order
<a name="ch05b048a">
below is σ created random order
  index 1<3, value 8>6  this is chaos
  1=σ(5)=σ(k) ＜ σ(j)=σ(1)=3 random
  8=b3=bσ(j=1) ＞ bσ(k=5)=b1=6 random
<a name="ch05b048b">
below is τ bring σ back to order
  index 1<3, value 6<8 this is order
  τ(j=1)=σ(k=5)=1 ＜ 3=σ(j=1)=τ(k=5) 
bτ(j=1)=bσ(k=5)=b1=6＜ 8=b3=bσ(j=1)=bτ(k=5)
2009-11-23-18-38 add stop

<a name="ch05b049">
〚 seq_b in order, σ(i) random, τ(i) to order 〛
2009-11-23-16-33 here
we find two sum difference
  S(τ)-S(σ)  ---eqn.AN046
   // red extend to red, blue extend to blue
 =ajbτ(j)+akbτ(k)-ajbσ(j)-akbσ(k)
   // here use eqn.5.13. See bold τ below
   // τ bring one pair of σ back to order.
 =ajbτ(j)+akbτ(k)-ajbτ(k)-akbτ(j)
 =-aj(bτ(k)-bτ(j))
  +ak(bτ(k)-bτ(j))
 =(ak-aj)(bτ(k)-bτ(j)) ≧ 0

<a name="ch05b050">
That is
  S(τ)-S(σ)=  ---eqn.AN046
  (ak-aj)(bτ(k)-bτ(j)) ≧ 0 
Why eqn.AN046 has ≧ 0 conclusion?
Because we started at the assumption
[[
For sequence_a
we start from a pair of sorted, monotone
increase sequences.
]]
sequence_a is monotone increase.
and k＞j, then 
ak-aj ≧ 0 ---eqn.AN047

<a name="ch05b051">　Index begin　Index this file
〚 seq_b in order, σ(i) random, τ(i) to order 〛
we have ak-aj ≧ 0  (assumed j＜k)
and bτ(k)-bτ(j) ≧ 0 (...=6＜ 8=...)
then we know
eqn.AN046 has ≧ 0 is a result of
"order-to-quadratic" process.
This process is explained from 
eqn.AN040 to eqn.AN042. Very simple
proof.

<a name="ch05b052">
The transformation from σ to τ achieve
two goals.
First from σ to τ let summation increase
or at least keep same value as before.
  Sum(σ) ≦ Sum(τ) ---eqn.AN051
Second, the number of inversion reduced.
σ to τ transformed random_b sequence is 
more close to monotone increase b sequence.

Repeat σ to τ transformation until 
sequence is in increase order, then done.
2009-11-23-17-38 stop

<a name="ch05b053">
2009-11-23-19-02 start
■　Please read textbook
If you read textbook, you will find
different words, better English explain
same topic. LiuHH write above reading 
notes, they come from textbook after all.

Be careful, LiuHH notes may contain error
concept. No one proofread this page.

Textbook page 80 fig.5.1 is not present
in this file tute0020.htm. Please read 
textbook.
2009-11-23-19-06 stop

<a name="ch05b054">　Index begin　Index this file
2009-11-24-12-01 start
■　Program Rearrangement Inequality
2009-11-21 and 2009-11-22, LiuHH write a
program function ProductSum() calculate
two sequences Rearrangement Inequality.
Page URL is next
http://freeman2.com/cauchy6e.htm#prodSum
This page has four functions
1. Cauchy's Inequality
2. Cauchy Converse 
3. Product Sum = Rearrangement Inequality
4. Sort number 

<a name="ch05b055">
Here introduce Product Sum program.
Input is box21 for sequence_a
  and    box22 for sequence_b 
Output to box23
Run button is [ProdSum] and [testDoc]
Auxiliary button is [random#3]

<a name="ch05b056">
Program assume both seq_a and seq_b 
are random arranged.
Assume input are
sequence_a=[2,1,3]=[a1,a2,a3]
sequence_b=[6,4,5]=[b1,b2,b3]
both are random arranged.
Program calculate random order product 
sum first, get
Rand order product sum=2*6+1*4+3*5=31
2*6 come from a1*b1
1*4 come from a2*b2
3*5 come from a3*b3
product first, then sum get 31

<a name="ch05b057">
Next, program sort seq_a and seq_b, get
sequence_c=[3,2,1]=[c1,c2,c3]
sequence_d=[6,5,4]=[d1,d2,d3]
Both seq_c and seq_d are monotone decrease.
Use 'same' in 'Same order product sum'
Do product sum for seq_c and seq_d, get
Same order product sum=3*6+2*5+1*4=32

<a name="ch05b058">
Next, program reverse seq_d, get
sequence_e=[3,2,1]=[e1,e2,e3]
sequence_f=[4,5,6]=[f1,f2,f3]
seq_e=seq_c are monotone decrease.
seq_f is monotone increase.
One increase, one decrease,
Use 'Revs' in 'Revs order product sum'
Do product sum for seq_e and seq_f, get
Revs order product sum=1*6+2*5+3*4=28

<a name="ch05b059">　Index begin　Index this file
Above result suggest that
Product 1st, sum 2nd get Same≧Rand≧Revs

Above product first, sum second
Above negative number OK,
Below sum first, product second
Below non-negative only.

<a name="ch05b060">
Start from random sequence
sequence_a=[2,1,3]=[a1,a2,a3]
sequence_b=[6,4,5]=[b1,b2,b3]
Here a1+b1 first (not a1*b1)
get
Rand order sum product=(2+6)*(1+4)*(3+5)=320

<a name="ch05b061">
Do same thing for same order
Same order sum product=(3+6)*(2+5)*(1+4)=315

Do same thing for reverse order
Revs order sum product=(1+6)*(2+5)*(3+4)=343

Above result suggest that
Sum 1st, product 2nd get Same≦Rand≦Revs

<a name="ch05b062">
Now put result of two method side by side
Product 1st, sum 2nd get Same≧Rand≧Revs
Sum 1st, product 2nd get Same≦Rand≦Revs

This is just observation.
Product 1st, sum 2nd get Same≧Rand≧Revs
is proved at ch05b038

<a name="ch05b063">
Click [ProdSum] button, allow arbitrary
defined seq_a and seq_b inputs
Click [testDoc] button, program use
sequence_a=[2,1,3]
sequence_b=[6,4,5]
and include short document.

Sum 1st, product 2nd get Same≦Rand≦Revs
will be proved at problem 5.4
2009-11-24-12-40 stop

<a name="ch05b064">　Index begin　Index this file
2009-11-24-16-12 start
■　Random in pace
Here explain
"ak is always monotone increase, bk has three cases."
Assume seq_a7=[1,2,3,4,5]
  and  seq_b7=[7,9,6,10,8]
seq_a7 is monotone increase and seq_b7
is random order. Program cauchy6e.htm
give the following answer
[[
Same order product sum=130
Rand order product sum=123
Revs order product sum=110
9811212301
Same order sum product=135135
Rand order sum product=144144
Revs order sum product=161051
9811220756
]]
<a name="ch05b065">
Now the question is
seq_a7 is monotone increase, seq_b7 is 
random. What if seq_a7 is random and in
pace with seq_b7, that is if we have
two sequences "random" in pace
 seq_a8=[2,4,1,5,3]
 seq_b8=[7,9,6,10,8]
a[2] and b[2] both have smallest element
  1 in [2,4,1,5,3] and 6 in [7,9,6,10,8]
a[0] and b[0] both have second smaller
  2 in [2,4,1,5,3] and 7 in [7,9,6,10,8]
a[4] and b[4] both have third smaller
  3 in [2,4,1,5,3] and 8 in [7,9,6,10,8]
a[1] and b[1] both have second greater
  4 in [2,4,1,5,3] and 9 in [7,9,6,10,8]
a[3] and b[3] both have greatest element
  5 in [2,4,1,5,3] and 10 in [7,9,6,10,8]
seq_a8 and seq_b8 index are in pace !

<a name="ch05b066">
Program output next answer
[[
Same order product sum=130
Rand order product sum=130
Revs order product sum=110
9811212301
Same order sum product=135135
Rand order sum product=135135
Revs order sum product=161051
9811220756
]]
<a name="ch05b067">
Random order and monotone increase get 
same result 130 and 135135. Then
random in pace and monotone increase
are same thing! That means
"random" is seq_b relative to seq_a.
With this observation, we set seq_a 
at monotone increase order initially
that will not loss generality.
2009-11-24-16-29 stop

<a name="ch05b068">　Index begin　Index this file
2009-11-24-17-39 start
■　A nonlinear rearrangement inequality
Text page 81, problem 5.4
Let f1,f2,...,fn be functions from
the interval I into real R such that
  fk+1(x)-fk(x) is nondecreasing
         for all 1≦k≦n ---eqn.5.14
<a name="ch05b069">
Let b1≦b2≦...≦bn be an ordered
sequence of elements of I, and show 
that for each permutation σ:[n]→[n]
one has the bound
  ∑[k=1,n]fk(bn-k+1)
 ≦∑[k=1,n]fk(bσ(k))
 ≦∑[k=1,n]fk(bk) ---eqn.5.15
2009-11-24-17-51 here

<a name="ch05b069a">
Alert: 
sequence ak not show up in problem 
statement. ak is part of fk(x).
sequence ak is ALWAYS monotone increase
sequence bk is defined monotone increase
sequence bk change to random & decrease

<a name="ch05b070">
The goal of nonlinear rearrangement 
inequality is to prove
sum product inequality
  ∏(ak+bk)≦∏(ak+bσ(k))≦∏(ak+bn-k+1) ---eqn.5.16 aux1
using the method of product sum 
  ∑akbn-k+1≦∑akbσ(k)≦∑akbk ---eqn.5.12 aux1
above ∏ represent ∏[k=1,n]
above ∑ represent ∑[k=1,n]
∏(ak+bk) is sum product,
     sum first, product second.
∑akbk is product sum,
     product first, sum second.

<a name="ch05b071">
Compare eqn.5.15 with eqn.5.12 
fk(bn-k+1) similar to akbn-k+1, reverse
fk(bσ(k)) similar to akbσ(k), random
fk(bk) similar to akbk, same order
We can expect that fk() definition
contains ak
We can expect function parameter fk(x) 
use bk as x.

<a name="ch05b072">　Index begin　Index this file
We use product sum method to prove 
sum product equation eqn.5.16 aux1.
Second step of 'product sum' is sum
Second step of 'sum product' is product
How to convert second step sum to
second step product ?
<a name="ch05b073">
We know
  log(a)+log(b)+log(c)=log(a*b*c) ---eqn.AN052
Function fk() can use log function.
eqn.5.15 sum of log() become log of
product.
If we use fk(x) = log(x) ---eqn.AN053
where is k at right hand side?

<a name="ch05b074">
***** Please do not complain, this
***** file is thinking process record.
***** If you want one step to solution
***** Please read textbook
***** 2009-11-24-18-31 here

<a name="ch05b075">
Our goal is sum product, sum first
that is ak+bk first.
bk is parameter x, then ak
must mold into fk(x) = log(x)
Next try
  fk(x) = log(ak+x) ---eqn.AN054
this one look better, ak is constant
and defined in function. Try
  fk(bk) = log(ak+bk) ---eqn.AN055
<a name="ch05b076">
Log function is monotone increase 
function, it is "nondecreasing".
Look wonderful, so far so happy.
But, 
peek at textbook page 81 line -8
It says
  fk(x) = MINUS log(ak+x) ---eqn.AN056
Why ??!! 
-log(x) is monotone decreasing !!
Wondering!, puzzle! dizzy !!
2009-11-24-18-50 stop

<a name="ch05b077">　Index begin　Index this file
2009-11-24-22-06 start
■　Hidden ak is monotone increase
From the section Random in pace we know
that the order between seq_a and seq_b 
is relative. For example
let seq_a9 = [1,2,3] = [a1,a2,a3]
and seq_b9 = [4,5,6] = [b1,b2,b3]
now they are both monotone increase
<a name="ch05b078">
We lock each column
 a1 always pair with b1
 a2 always pair with b2
 a3 always pair with b3
let seq_a10 = [2,3,1] = [a2,a3,a1]
and seq_b10 = [5,6,4] = [b2,b3,b1]
<a name="ch05b079">
Look at [2,3,1] and [5,6,4], both are
NOT monotone increase/decrease. But the
sum product and product sum calculation
tell us they are both monotone increase.
We do not want to get confuse, we assign
seq_a be always monotone increase. Let
seq_b change pattern.

<a name="ch05b080">
The Rearrangement Inequality problem 
statement and prove process both state 
 -∞＜a1≦a2≦...≦an＜∞ ---eqn.AN029
clearly. But
A nonlinear rearrangement inequality
problem statement do not even mention ak
seq_a be always monotone increase is 
still true in nonlinear problem. Instead
of require ak+1≧ak ---eqn.AN057
<a name="ch05b081">
problem say
  fk+1(x)-fk(x) is nondecreasing
That is require fk+1(x)－fk(x)≧0 ---eqn.AN058
eqn.AN053 suggest use fk(x)=log(x)
eqn.AN054 suggest use fk(x)=log(ak+x)
ak is part of fk(x) and ak is hidden. 
Problem not mention ak !!

<a name="ch05b082">
Let us calculate
  fk+1(x)－fk(x)
  =log(ak+1+x)-log(ak+x)
  =log[(ak+1+x)/(ak+x)] ---eqn.AN059
We insist seq_a be monotone increase.
Will the condition ak+1 ＞ ak ---eqn.AN060
bring us  fk+1(x)－fk(x) ＞ 0  ---eqn.AN061
??

<a name="ch05b083">
Define r(x)=(ak+1+x)/(ak+x) ---eqn.AN062
Now we have
  fk+1(x)－fk(x)=log(r(x)) ---eqn.AN063
eqn.AN063 is a composite function !
A composite function bring us smooth?
 or
a composite function bring us crisis?
2009-11-24-22-56 stop

<a name="ch05b084">　Index begin　Index this file
2009-11-25-08-49 start
■　Composite function bring us crisis
We know log function log(x) is monotone
increase. Please go to Prob.5.4 drawing.
Click [Prob.5.4] button.
You must use MSIE to view figure.
Black dash curve is f(x)=log(ak+x). When 
x approach infinity, log(ak+x) approach 
infinity too.
variable x is log(x)'s direct parameter.

<a name="ch05b085">
If we have a composite function like
  f(x)=log(r(x)) ---eqn.AN064
what is the result?
variable still start from x=1 to x=inf
Whether log(r(x)) behave same as log(x)?
yes only if
  r(x)=x  ---eqn.AN065
in all other case
log(r(x)) behave different from log(x).
<a name="ch05b086">
Simplest example for other case is 
  r(x)=sin(x)+2  ---eqn.AN066
In eqn.AN066 x start from x=0 to x=inf
sin(x) oscillate between -1 and +1
sin(x)+2 oscillate between +1 and +3
x is log(r(x))'s indirect parameter.
r(x) is log(r(x))'s direct parameter.
<a name="ch05b087">
Although x start from x=0 to x=inf
but log(sin(x)+2) oscillate between
log(+1) and log(+3)
x is monotone increase, but
log(sin(x)+2) is oscillating!

<a name="ch05b088">
Our present problem has
  r(x)=(ak+1+x)/(ak+x) ---eqn.AN062
with ak+1 ＞ ak ---eqn.AN060
Whether our r(x) oscillating?
Please go to Prob.5.4 drawing.
Click [Prob.5.4] button. 
*** Thicker solid blue: (ak2+x)/(ak1+x)
<a name="ch05b089">
Thank God, thicker solid blue curve is 
NOT oscillating and r(x) is a monotone
curve. Now put eqn.AN062 into eqn.AN063
we find
  fk+1(x)－fk(x) ---eqn.AN067
  =log((ak+1+x)/(ak+x))
What is the curve log((ak+1+x)/(ak+x)) ?
This is Prob.5.4 drawing solid black
curve. 
At this point we should really worry !
solid black curve is monotone decreasing
BUT we expect a monotone increasing curve.
because given condition require
  fk+1(x)－fk(x) ＞ 0  ---eqn.AN061

<a name="ch05b090">　Index begin　Index this file
In eqn.AN067 log() direct parameter is
  r(x)=(ak+1+x)/(ak+x) ---eqn.AN062
direct parameter is NOT x in eqn.AN067. 
log(x) is monotone increase (see
Prob.5.4 drawing dash black curve)
But log(r(x)) become monotone decrease.
Must be r(x) cause reverse !! 

<a name="ch05b091">
At "Thank God" point we ignored r(x)'s
reverse property !
"reverse" mean change monotone increase
x to monotone decrease output. f(x)=1/x
is such an example.
Let us check
  r(x)=(ak+1+x)/(ak+x) ---eqn.AN062
curve slope. 
<a name="ch05b092">
Find d[r(x)]/dx as following
  d[r(x)]/dx
  = d[(ak+1+x)/(ak+x)]/dx
  = [1/(ak+x)]+[-(ak+1+x)/(ak+x)/(ak+x)]
  = [(ak+x)-(ak+1+x)]/[(ak+x)2]
  = [ak-ak+1]/[(ak+x)2] ---eqn.AN068
<a name="ch05b093">
[(ak+x)2] is always positive
[ak-ak+1] is always negative
because we have   ak+1 ＞ ak ---eqn.AN060
eqn.AN068 tell us dr(x)/dx is always
negative. r(x) is monotone decreasing.
Then log(r(x)) is monotone decreasing.

<a name="ch05b094">
We insist both ak+1 ＞ ak ---eqn.AN060
and   fk+1(x)－fk(x) ＞ 0  ---eqn.AN061
then who yield ? It is
  fk(x) = log(ak+x) ---eqn.AN054
yield. We re-write as
  fk(x) = MINUS log(ak+x) ---eqn.AN056
After this modification everything 
become smooth.
MINUS monotone decrease
  is  monotone increase
2009-11-25-10-11 stop

<a name="ch05b095">　Index begin　Index this file
2009-11-25-12-56 start
■　(ak+1+x)/(ak+x) vs (ak+1+bk+1)/(ak+bk)
Our final goal is
  ∏(ak+bk)≦∏(ak+bσ(k))≦∏(ak+bn-k+1) ---eqn.5.16 aux1
Above ∏ represent ∏[k=1,n]
If n=3, then the whole equation is
  (a1+b1)*(a2+b2)*(a3+b3) //same order
≦(a1+b3)*(a2+b1)*(a3+b2) //random order
≦(a1+b3)*(a2+b2)*(a3+b1) //reverse order
 ---eqn.5.16 aux2
<a name="ch05b096">
In eqn.5.16 aux2, when 'a' change index
the paired 'b' change index too. So
 (ak+1+bk+1)/(ak+bk) ---eqn.AN069
look reasonable, and
 (ak+1+x)/(ak+x) ---eqn.AN070
look suspicious.
<a name="ch05b097">
If let x=bk, the suspicious become
 (ak+1+bk)/(ak+bk) ---eqn.AN071
here 'a' change index, but 'b' not change!
Why ?!

<a name="ch05b098">
eqn.AN070 is r(x) definition eqn.AN062
r(x) definition main purpose is ensure
 ak+1 ＞ ak ---eqn.AN060
and  
 fk+1(x)－fk(x) ＞ 0  ---eqn.AN061
are both true.
<a name="ch05b099">
r(x) definition target at ak
r(x) definition has nothing to do 
     with bk, eqn.AN071 is not related.
This is LiuHH observed question and
fabricated answer. Need your thinking 
and your judgment.
2009-11-25-13-20 stop



<a name="ch05b100">　Index begin　Index this file
2009-11-25-13-31 start
■　Nonlinear problem assembled
With above discussion, we know
1. let f(x) be log function
   log(a)+log(b)+log(c)=log(a*b*c) ---eqn.AN052
   we can change addition to product.
2. define f(x) with this log
   fk(x) = － log(ak+x) ---eqn.AN056
<a name="ch05b101">
   here minus sign make sure 
   ak+1 ＞ ak ---eqn.AN060
   and  
   fk+1(x)－fk(x) ＞ 0  ---eqn.AN061
   are both true, please review 
   Random in pace Also －log(ak+x)
   include ak as part of f(x) definition.
<a name="ch05b102">
   log(x) is nonlinear, fk(x) use log(x)
   so it is called nonlinear problem.
3. apply the linear problem equation to
   current nonlinear problem.

<a name="ch05b103">
Based on above three points, use
same tool as linear problem
  Sum(σ) ≦ Sum(τ) ---eqn.AN051
we have
  ∑[k=1,n]fk(bn-k+1)
 ≦∑[k=1,n]fk(bσ(k))
 ≦∑[k=1,n]fk(bk) ---eqn.5.15
<a name="ch05b104">
Use
   log(a)+log(b)+log(c)=log(a*b*c) ---eqn.AN052
change from summation ∑[k=1,n]fk(bk)
to product 
  ∏(ak+bk)≦∏(ak+bσ(k))≦∏(ak+bn-k+1) ---eqn.5.16 aux1
<a name="ch05b105">
The minus sign in
   fk(x) = － log(ak+x) ---eqn.AN056
reverse inequality at the step of
change from summation to product.

<a name="ch05b106">
log(negative value) is undefined.
nonlinear rearrangement inequality
eqn.5.16 work with non-negative
seq_a and non-negative seq_b only.

Up to here, 
nonlinear rearrangement inequality
eqn.5.16 is proved.

2009-11-25-14-28 stop

2009-11-25-17-12 done proofread
2009-11-25-17-31 done spelling check



<a name="ch05b108">　Index begin　Index this file
2009-11-25-20-24 start
■　Exercise 5.1 problem statement
　　textbook page 82
（Baseball and Cauchy's Third Inequality）

In the remarkable Note II of 1821 where
Cauchy proved both his namesake 
inequality and the fundamental AM-GM 
bound, one finds a third inequality 
which is not as notable nor as deep 
but which is still handy from time to
time. The inequality asserts that for
any positive real numbers h1,h2,...,hn
and b1,b2,...,bn, one has the ratio 
bound

<a name="ch05b110">
2009-11-25-20-45 here
Sports enthusiasts may imagine, as 
Cauchy never would, that bj denotes
the number of times a baseball player
 j goes to bat, and hj denotes the
number of times he gets a hit. The 
inequality confirms the intuitive fact
that the batting average of a team is
never worse than that of its worst
hitter and never better than that of
its best hitter.

<a name="ch05b111">
Prove the inequality (5.17) and put it
to honest mathematical use by proving
that for any polynomial 
  P(x)=c0+c1x+c2x2+...+cnxn ---eqn.AN072
with positive coefficients one has the
monotonicity relation

2009-11-25-21-05 here



<a name="ch05b113">　Index begin　Index this file
2009-11-25-21-07
■　Exercise 5.1 hint
　　textbook page 243
The upper bound of (5.17) follows from

<a name="ch05b115">
2009-11-25-21-22 here
and the lower bound is analogous. For
application, if we 
set ak=ckxk ---eqn.AN076
and bk=ckyk ---eqn.AN077
then we have
  min{ak/bk}=(x/y)n ---eqn.AN078
and
  max{ak/bk}=1 ---eqn.AN079
2009-11-25-21-28 stop



<a name="ch05b116">
2009-11-26-09-01 start
■　Exercise 5.1 discussion
First present an example. We have a
calculation as next
  ans11=2*0.1+5*0.3+4*0.6 ---eqn.AN080
Problem allow us modify the fraction 
part. We do the next modification. 
Define
  b11=max{0.1, 0.3, 0.6}=0.6 ---eqn.AN081
<a name="ch05b117">
Rewrite eqn.AN080 as next
  ans11≦2*b11+5*b11+4*b11 ---eqn.AN082
Inequality in eqn.AN082 is due to 
fraction replacement. Since b11 is 
common factor, rewrite eqn.AN082 as
  ans11≦(2+5+4)*b11 ---eqn.AN083
Finally we have
  ans11=4.1≦(2+5+4)*0.6=6.6 ---eqn.AN084
The inequality 4.1≦6.6 is true.

<a name="ch05b118">　Index begin　Index this file
2009-11-26-09-16
■　Exercise 5.1 solution


eqn.AN074 in the hint section let hi 
multiply by one, this one is bi/bi
Then rewrite hibi/bi as (hi/bi)bi. 
Sum from i=1 to i=n, get eqn.AN074
From eqn.AN074 to eqn.AN075 is fraction
replacement, please see Exercise 5.1 
discussion. 
<a name="ch05b119">
eqn.AN075 divide by {b1+b2+...+bn}
get eqn.5.17 inequality high end.
Low end part is same, instead of 
taking max{fraction list}, change to
taking min{fraction list}.
Here answered eqn.5.17.
Next prove eqn.AN073.
Write P(x)/P(y) in expanded form

<a name="ch05b121">
2009-11-26-09-42 here
Compare eqn.AN085 and eqn.5.17 fraction
part.
set hk=ckxk ---eqn.AN086
set bk=ckyk ---eqn.AN087
Then
  min{hk/bk}=min{ckxk/ckyk} ---eqn.AN088
ck cancel out from eqn.AN088
Problem given 0＜x≦y ---eqn.AN073 left end
<a name="ch05b122">
Therefore x/y≦1. With 1≦k≦n
  min{xk/yk}=xn/yn ---eqn.AN089
eqn.AN089 is easy observed. Assume x/y=1/2
  min{(1/2)^1,(1/2)^2,(1/2)^3,(1/2)^4,(1/2)^5}
is highest power (1/2)^5. 
With 1≦k≦n, xn/yn is minimum.

<a name="ch05b123">
How about maximum? 
Problem given 0＜x≦y ---eqn.AN073 left end
x=y create maximum x/y=1. Who else?
  max{xk/yk}=1 ---eqn.AN090

With minimum and maximum in hand,
eqn.AN073 is solved.

<a name="ch05b124">
By the way, for k th player
  hk/bk≦1 ---eqn.AN091
is true.
Bat 100 times, hit  30 times is OK
Bat 100 times, hit 120 times is NO
2009-11-26-10-01 stop



<a name="ch05b125">　Index begin　Index this file
2009-11-26-12-53 start
■　Exercise 5.2 problem statement
　　textbook page 83
（Betweenness and an Inductive Proof
 of AM-GM）

One can build an inductive proof of
the basic AM-GM inequality (2.3) by
exploiting the conversion of an
order relation to a quadratic bound.
To get started, first consider
  0＜a1≦a2≦...≦an ---eqn.AN092
set
  A=(a1+a2+...+an)/n ---eqn.AN093
<a name="ch05b126">
and then show that one has
  a1an/A ≦ a1+an-A ---eqn.AN094
Now, complete the induction step of
the AM-GM proof by considering the 
n-1 elements set
  S={a2,a3,...,an-1}∪{a1+an-A} ---eqn.AN095
2009-11-26-13-03 stop




<a name="ch05b127">
2009-11-26-13-08
■　Exercise 5.2 hint
　　textbook page 243
The n-1 elements of S have mean A.
So by the induction hypothesis H(n-1)
we have
  a2*a3*...*an(a1+a2-A)≦An-1 ---eqn.AN096
The betweenness bound already gave us
  a1an/A ≦ a1+an-A ---eqn.AN094
and when we may apply this bound alone,
we get H(n) which completes the induction.

<a name="ch05b128">
This proof from Chong (1975) is closely
related to a "smoothing" proof of the
AM-GM which exploits the algorithm:

(1) if a1,a2,...,an are not all equal to
    the mean A, let aj and ak denotes the
    smallest  and largest, respectively.
<a name="ch05b129">
(2) replace aj by A and replace ak by
    aj+ak-A
(3) note that each step of the algorithm
    increases by one the number of terms
    equal to the mean, so the algorithm
    terminates in at most n steps.

<a name="ch05b130">
The betweenness bound gives us 
    ajak≦A(aj+ak-A) ---eqn.AN097
so each step of the algorithm increases 
the geometric mean of the current sequence.
Since we start with the sequence 
a1,a2,...,an and terminate with a
sequence of n copies of A, we see
   a1a2...an≦An ---eqn.AN098
2009-11-26-13-28 stop



<a name="ch05b131">　Index begin　Index this file
2009-11-26-13-36 start
■　Exercise 5.2 discussion
Arithmetic mean A
  A=[a1+a2+...+an]/n ---eqn.AE13
so
  n*A=[a1+a2+...+an] ---eqn.AN099

<a name="ch05b132">
Exercise 5.2 problem statement said
[[
n-1 elements set
  S={a2,a3,...,an-1}∪{a1+an-A} ---eqn.AN095
]]

Exercise 5.2 hint said
[[
The n-1 elements of S have mean A.
]]

<a name="ch05b133">
  mean(n-1)  ---eqn.AN100
  ={[a2+a3+...+an-1]+[a1+an-A]}/(n-2+1)
  ={[a1+a2+a3+...+an-1+an]+[-A]}/(n-2+1)
   // here use eqn.AN099
  ={n*A-A}/(n-1)
  =A
2009-11-26-13-41 

<a name="ch05b134">
2009-11-26-13-57
From eqn.AN095 find n-1 elements set
then by "induction hypothesis H(n-1)"
LiuHH expect
  a2*a3*...*an-1(a1+an-A)≦An-1 ---eqn.AN101
but hint give
  a2*a3*...*an(a1+a2-A)≦An-1 ---eqn.AN096
Why ?
LiuHH is thinking
2009-11-26-14-00

<a name="ch05b135">
2009-11-26-15-24
[[
consider
  0＜a1≦a2≦...≦an ---eqn.AN092
set
  A=(a1+a2+...+an)/n ---eqn.AN093
and then show that one has
  a1an/A ≦ a1+an-A ---eqn.AN094
]]
<a name="ch05b136">
  a1an/A =  ---eqn.AN102
  a1an*n/(a1+a2+...+an)

  a1+an-A=  ---eqn.AN103
  a1+an-(a1+a2+...+an)/n

<a name="ch05b137">　Index begin　Index this file
  a1+an-A - a1an/A   ---eqn.AN104
  =(a1*A+an*A-A2 - a1an)/A2
  =-(-a1*A-an*A + A2 + a1an)/A2
  =-(A-a1)*(A-an)/A2
Because given
  0＜a1≦a2≦...≦an ---eqn.AN092
and Arithmetic mean A 
  A=[a1+a2+...+an]/n ---eqn.AE13
<a name="ch05b138">
so we have
  0＜a1≦ A ≦an ---eqn.AN105
that is 
  (A-a1)*(A-an)≦0 ---eqn.AN106
***** eqn.AN105 and eqn.AN106 is 
***** order to quadratic.
<a name="ch05b139">
Substitute eqn.AN106 to eqn.AN104 
get
  a1+an-A - a1an/A   ---eqn.AN107
  =-(A-a1)*(A-an)/A2
  =-(negative or zero)/(positive) ≧ 0
eqn.AN107 confirmed eqn.AN094
  a1an/A ≦ a1+an-A ---eqn.AN094
2009-11-26-15-45 here

<a name="ch05b140">
2009-11-26-16-07 start
How do we use eqn.AN094?
rewrite eqn.AN094 as next
  a1an ≦ A*(a1+an-A) ---eqn.AN108
we have
  0＜a1≦ A ≦an ---eqn.AN105
<a name="ch05b141">
then review
[[
(1) if a1,a2,...,an are not all equal to
    the mean A, let aj and ak denotes the
    smallest  and largest, respectively.
]]
<a name="ch05b142">
Now // eqn.AN109 is betweenness
  0＜a1≦aj≦ A ≦ak≦an ---eqn.AN109
  a1an ≦ A*(a1+an-A) ---eqn.AN108
are true, and
  ajak ≦ A*(aj+ak-A) ---eqn.AN110
is also true.

<a name="ch05b143">　Index begin　Index this file
Next review
[[
(2) replace aj by A and replace ak by
    aj+ak-A
(3) note that each step of the algorithm
    increases by one the number of terms
    equal to the mean, so the algorithm
    terminates in at most n steps.
]]
<a name="ch05b144">
The action "replace aj by A" push
   ajaj+1aj+2AA...ak ---eqn.AN111
to 
   aj+1aj+2AAA...ap ---eqn.AN112
and eqn.AN112 ≧ eqn.AN111 
this inequality is a result of eqn.AN110
<a name="ch05b145">
The replace process take place at most n
steps (we have total n elements a1 to an)
At the end of this process, we have the
greatest value An
2009-11-26-16-24 here

<a name="ch05b146">
2009-11-26-16-36
[[
(1) if a1,a2,...,an are not all equal to
    the mean A, let aj and ak denotes the
    smallest  and largest, respectively.
(2) replace aj by A and replace ak by
    aj+ak-A
]]
<a name="ch05b147">
Before replacement, sum of smallest 
and largest two elements are aj+ak
After replacement, sum of new created
two elements are A + (aj+ak-A)
Total sum not change in replacement
process. But product value increase
step by step. Again the increase 
product value is result of eqn.AN110
2009-11-26-16-41 here




<a name="ch05b148">
■　Exercise 5.2 solution

LiuHH expect
  a2*a3*...*an-1(a1+an-A)≦An-1 ---eqn.AN101
but hint give
  a2*a3*...*an(a1+a2-A)≦An-1 ---eqn.AN096
Why ?
LiuHH is thinking
2009-11-26-14-01



<a name="ch05b149">　Index begin　Index this file
2009-11-26-18-12 start
■　Exercise 5.3 problem statement
　　textbook page 83
（Cauchy-Schwarz and the Cross Term Defect）

If u and v are elements of the real
number product space V for which one
has the upper bounds
  〈u,u〉 ≦ A2 ---eqn.AN113
  〈v,v〉 ≦ B2 ---eqn.AN114
<a name="ch05b150">
then Cauchy's inequality tell us
  〈u,v〉 ≦ AB ---eqn.AN115
Show that one then also has a lower
bound on the cross-term difference
  AB-〈u,v〉 ---eqn.AN116
namely
  {A2-〈u,u〉}1/2{B2-〈v,v〉}1/2
  ≦ AB-〈u,v〉 ---eqn.5.18
2009-11-26-18-22 here







<a name="ch05b151">
2009-11-26-18-26
■　Exercise 5.3 hint
　　textbook page 244
If one first consider V=R and sets
  a=u ---eqn.AN117
and
  b=v ---eqn.AN118
then the inequality in question asserts
that
  AB-ab≧(A2-a2)1/2(B2-b2)1/2 ---eqn.14.51
<a name="ch05b152">
By expansion and factorization, this
is equivalent to
  (aB-Ab)2≧0 ---eqn.AN119
and the bound (14.51) is true and
equality holds if and only if
  aB=Ab ---eqn.AN120
<a name="ch05b153">
To address the general problem, we
first note by the Cauchy-Schwarz
inequality
  AB-〈u,v〉≧ ---eqn.AN121
  AB-〈u,u〉1/2〈v,v〉1/2
so, by the bound (14.51) with
  a=〈u,u〉1/2 ---eqn.AN122
and
  b=〈v,v〉1/2 ---eqn.AN123
<a name="ch05b154">
one has
  AB-〈u,v〉≧  ---eqn.14.52
  (A2-〈u,u〉)1/2(B2-〈v,v〉)1/2
which was to be proved.
<a name="ch05b155">
If equality hold in the bound (14.52)
this argument shows that we have 
  〈u,v〉=〈u,u〉1/2〈v,v〉1/2 ---eqn.AN124
so, there is a constant λ such that
  u=λv ---eqn.AN125
By substitution one then finds that
  λ=A/B ---eqn.AN126

<a name="ch05b156">
The bound (14.52) is abstracted from 
an integral version given in Theorem
9 of Lyusternik (1966) which Lyusternik
used in his proof of the Brunn-
Minkowski inequality in two dimensions.
The idea viewing V=R as a special inner
product space is often useful, but
<a name="ch05b157">
seldom is it as decisive as it proved 
to be here. One should also notice the
easily overlooked fact that the bound 
(14.52) is actually equivalent to the
light cone inequality (4.15).
2009-11-26-18-55 stop



<a name="ch05b158">　Index begin　Index this file
2009-11-26-19-32 start
■　Exercise 5.3 solution


Exercise 5.3 is designed for relativity
theory to match Lorentz product.
<a name="ch05b159">
define Lorentz product as next
 [x,y]=tc*uc－x1*y1－...－xd*yd ---eqn.4.14
Now set [x,y] to [x,x]
 [x,x]=tc*tc－x1*x1－...－xd*xd ---eqn.AK026
If u is measured length, 
  tc is light traveled distance in
     time interval t
<a name="ch05b160">
let u=[x1,x2,...,xd] ---eqn.AN127
and A=tc ---eqn.AN128
A is t*c in eqn.AK023A

Exercise 5.3 problem statement
  〈u,u〉 ≦ A2 ---eqn.AN113
is same as the square of next line
  measured length ≦ light traveled distance

<a name="ch05b161">
Exercise 5.3 problem statement
A2-〈u,u〉 used in eqn.5.18
is Lorentz product [x,x].

 √(〈u,u〉) is measured length
 √(〈u,u〉)≦A  ---eqn.AN129 (eqn.AN113)
say measured length ≦ light traveled 
distance in related time interval.
<a name="ch05b162">
If let
  a=√(〈u,u〉)  ---eqn.AN130
  b=√(〈v,v〉)  ---eqn.AN131
u is x1,x2,...,xd in eqn.AK023A
v is y1,y2,...,yd in eqn.AK023B

<a name="ch05b163">　Index begin　Index this file
  √(〈v,v〉)≦B  ---eqn.AN132
B is u*c in eqn.AK023B
B is light speed c traveled in time 
interval u.
eqn.AN132 is second event of
measured length ≦ light traveled distance

<a name="ch05b164">
Original Cauchy inequality is
  〈u,v〉≦〈u,u〉1/2〈v,v〉1/2 ---eqn.AN133
Refer to eqn.AN129 and eqn.AN132
eqn.AN133 is further less than
  〈u,v〉≦AB  ---eqn.AN115
2009-11-26-20-18 here

<a name="ch05b165">
Use eqn.AN130 and eqn.AN131, 
wait for proving equation 
  {A2-〈u,u〉}1/2{B2-〈v,v〉}1/2
  ≦ AB-〈u,v〉 ---eqn.5.18
can be written as
  {A2-a2}1/2{B2-b2}1/2
  ?≦? AB-ab  ---eqn.AN134 (eqn.14.51)
<a name="ch05b166">
Square eqn.AN134 get
  {A2-a2}{B2-b2}
  ?≦? (AB-ab)*(AB-ab) ---eqn.AN135
expand
  A2B2-A2b2-a2B2+a2b2
  ?≦? ABAB-ABab-abAB+abab  ---eqn.AN136
Red term cancel, blue term cancel
  0 ?≦? +A2b2+a2B2-ABab-abAB  ---eqn.AN137
<a name="ch05b167">
finally find
  0 ?≦? (Ab-aB)2  ---eqn.AN138
eqn.AN138 is true, then
wait for proving equation eqn.5.18
is true.
2009-11-26-20-38 stop



<a name="ch05b168">　Index begin　Index this file
2009-11-26-21-11 start
■　Exercise 5.4 problem statement
　　textbook page 83
（A Remarkable Inequality of I. Schur）

Show that for all values of x,y,z≧0
one has for all α≧0 that
  xα(x-y)(x-z)+yα(y-x)(y-z)
 +zα(z-x)(z-y)≧0 ---eqn.5.19
Moreover, show that one has equality
here if and only if one has either
x=y=z or two of the variables are
equal and the third is zero.

<a name="ch05b169">
Schur's inequality can sometimes save 
the day in problem where the AM-GM
inequality looks like the natural
tool, yet it comes up short. Sometimes
the two-pronged condition for equality
also provides a clue that Schur's
inequality may be of help.
2009-11-26-21-19 here






<a name="ch05b170">
2009-11-26-21-21
■　Exercise 5.4 hint
　　textbook page 244
The problem does not come with an order
relation, but we can give ourselves one
if we note that by the symmetry of the 
bound we can assume that
  0≦x≦y≦z ---eqn.AN139
<a name="ch05b171">
We then get for free the positivity of
the first summand xα(x-y)(x-z),
so to complete the proof we just need
to show the positivity of the other two.
This follows from the factorization
  yα(y-x)(y-z)+zα(z-x)(z-y)
 =(z-y){zα(z-x)-yα(y-x)} ---eqn.AN140
and the observation that
  z≧y ---eqn.AN141
and
  z-x≧y-x ---eqn.AN142
<a name="ch05b172">
This proof illustrates one of the most
general methods at our disposal; the
positivity of a sum can often be proved
by creative grouping the summands so
that the positivity of each group
become obvious.
2009-11-26-21-33




<a name="ch05b173">　Index begin　Index this file
2009-11-26-21-34
■　Exercise 5.4 solution


Given  x,y,z≧0 and  α≧0 
Target equation is to prove
  xα(x-y)(x-z)+yα(y-x)(y-z)
 +zα(z-x)(z-y)≧0 ---eqn.5.19
<a name="ch05b174">
Hint suggest we assume the relation
  0≦x≦y≦z ---eqn.AN139
Under this assumption, 
  xα(x-y)(x-z)≧0 ---eqn.AN143
is ensured. Next question is
  yα(y-x)(y-z)+zα(z-x)(z-y) ?≧? 0 ---eqn.AN144
Two terms in eqn.AN144 has common term
(z-y) which is ≧0 by eqn.AN139

<a name="ch05b175">
the factorization
  yα(y-x)(y-z)+zα(z-x)(z-y)
 =(z-y){zα(z-x)-yα(y-x)} ---eqn.AN140
and the observation that
  z≧y ---eqn.AN141
and  α≧0
then zα≧yα ---eqn.AN145
<a name="ch05b176">
The assumption of z≧y≧x≧0 gives
  z-x≧y-x ---eqn.AN142
eqn.AN142 and eqn.AN145 gives
  {zα(z-x)-yα(y-x)}≧0 ---eqn.AN146
eqn.AN146 plus (z-y)≧0 showed
eqn.AN144 is true.
eqn.5.19 is proved.

<a name="ch05b177">
Exercise 5.4 look complicate, but with 
Exercise 5.4 hint guidance,
solution is actually easy.
2009-11-26-21-48 stop



<a name="ch05b178">　Index begin　Index this file
2009-11-27-07-52 start
■　Exercise 5.5 problem statement
　　textbook page 83
（The Polya-Szego Converse Restructured）

The converse Cauchy inequality (5.7)
is expressed with the aid of bounds
on the ratio ak/bk, but for many
application it is useful to know
that one also has a natural converse
under the more straightforward
hypothesis that
  0＜a≦ak≦A ---eqn.AN147
  0＜b≦bk≦B ---eqn.AN148
for all k=1,2,...,n

<a name="ch05b179">
Use the Cauchy converse (5.7) to prove
that in this case one has

2009-11-27-08-23 here





<a name="ch05b180">
2009-11-27-08-28
■　Exercise 5.5 hint
　　textbook page 245

This is one of the text's few "plug-in"
exercises, but the bound is so nice it 
had to be made explicit. We just note
that
  m defined= a/A ≦ ak/bk ≦ A/b defined= M ---eqn.AN150
(where is capital B? 2009-11-27-08-35 LiuHH)
then we substitute into the formula
(5.6) and (5.7)
2009-11-27-08-33




<a name="ch05b181">　Index begin　Index this file
2009-11-27-08-42
■　Exercise 5.5 solution


Problem assumption
  0＜a≦ak≦A ---eqn.AN147
  0＜b≦bk≦B ---eqn.AN148

<a name="ch05b182">
Define
  m = a/B ---eqn.AN151
  M = A/b ---eqn.AN152
  m = a/B ≦ ak/bk ≦ A/b = M ---eqn.AN153
Red B is change made by LiuHH.

<a name="ch05b183">
Define
  A=(m+M)/2 ---eqn.AM216 (eqn.5.6)
  G = √(mM) ---eqn.AM217 (eqn.5.6)
then
  A=(a/B + A/b)/2  ---eqn.AN154
  G = √[aA/(bB)]  ---eqn.AN155
<a name="ch05b184">
eqn.5.7 use A/G
  A/G=(a/B + A/b)/{2√[aA/(bB)]}
     =(ab+AB)/(bB)/{2√[aA/(bB)]}
     =(ab+AB)/{2√[aA(bB)]}
     =(ab/√[aA(bB)] + AB/√[aA(bB)])/2
     =(√[ab/(AB)] + √[AB/(ab)])/2  ---eqn.AN156

<a name="ch05b185">
eqn.AN149 is square of eqn.5.7
  (A/G)2  ---eqn.AN157
     ={(√[ab/(AB)] + √[AB/(ab)])/2}2
     = {√[ab/(AB)] + √[AB/(ab)]}2/4

eqn.AN157 is eqn.AN149 right hand side
exactly. Problem solved.
2009-11-27-09-07 stop



<a name="ch05b186">　Index begin　Index this file
2009-11-27-11-11 start
■　Exercise 5.6 problem statement
　　textbook page 84
（A Competition Perennial）

Show that if a＞0, b＞0 and c＞0 then one
has the elegent symmetric bound

<a name="ch05b188">
2009-11-27-11-20 here
This is known as Nesbitt's inequality, 
and along with several natural variations.
it has served a remarkable number of
mathematical competitions, from Moscow
in 1962 to the Canadian Maritimes in
2002.
2009-11-27-11-23 here






<a name="ch05b189">
2009-11-27-11-25
■　Exercise 5.6 hint
　　textbook page 245
Without loss of generality, we can assume
that
  0＜a≦b≦c  ---eqn.AN158
and under this assumption
we also have

<a name="ch05b193">
2009-11-27-11-40 here
By summing these two bounds we find
Nesbitt's inequality.

Engel (1998, pp. 162-168) provides 
five instructive proofs of Nesbitt's 
inequality, including the one given 
here, but, even so, one can add to
the list. Tony Cai recently noted that
Nesbitt's inequality follows from the
bound (1.21) page 13, provided that 
one sets

<a name="ch05b196">
2009-11-27-11-54 here
and set
  bk=1/ak for k=1,2,3 ---eqn.AN164
With these substitutions the bound
(1.21) automatically gives us

<a name="ch05b198">
2009-11-27-12-10 here
which in turn yields Nesbitt's inequality
since the second factor is bounded by 2/3
because Cauchy's inequality for (a,b,c) 
and (1,1,1) tells us that 
  (a+b+c)2≦3(a2+b2+c2) ---eqn.AN166
2009-11-27-12-15 stop






<a name="ch05b199">　Index begin　Index this file
2009-11-27-13-02 start
■　Exercise 5.6 solution

We assume that
  0＜a≦b≦c  ---eqn.AN158
then
  a+b≦a+c≦b+c ---eqn.AN167
take reciprocal, find
  1/(b+c)≦1/(a+c)≦1/(a+b) ---eqn.AN168

<a name="ch05b200">
Compare eqn.AN158 and eqn.AN168. 
From left to right, both are monotone
increase. The equal index product sum
has greatest value, that is
  max_product_sum=
  a/(b+c)+b/(a+c)+c/(a+b) ---eqn.AN169
('a' multiply with '1/(b+c)' get 'a/(b+c)'
 this is product, not division)
<a name="ch05b201">
Compare random order b,c,a and
increase order 1/(b+c),1/(a+c),1/(a+b)
created product sum
  mid1_product_sum=
  b/(b+c)+c/(a+c)+a/(a+b) ---eqn.AN170
We conclude that
  b/(b+c)+c/(a+c)+a/(a+b)≦
  a/(b+c)+b/(a+c)+c/(a+b) ---eqn.AN160
<a name="ch05b202">
Similar reason for another random order
  mid2_product_sum=
  c/(b+c)+a/(a+c)+b/(a+b) ---eqn.AN171
We conclude that
  c/(b+c)+a/(a+c)+b/(a+b)≦
  a/(b+c)+b/(a+c)+c/(a+b) ---eqn.AN161
<a name="ch05b203">
Now add eqn.AN160 and eqn.AN161 get
  (b+c)/(b+c)+(a+c)/(a+c)+(a+b)/(a+b)≦
  2*[a/(b+c)+b/(a+c)+c/(a+b)] ---eqn.AN172
Simplify get
  3≦2*[a/(b+c)+b/(a+c)+c/(a+b)] ---eqn.AN173
this is
  3/2≦[a/(b+c)+b/(a+c)+c/(a+b)] ---eqn.5.20
Done prove.
2009-11-27-13-22 here

<a name="ch05b204">　Index begin　Index this file
Second method substitute eqn.AN162, eqn.AN163
and eqn.AN164 to (1.21) get
  1≦[p1*a1+p2*a2+p3*a3]
   *[p1*b1+p2*b2+p3*b3] ---eqn.AN174
It is easier to do one small piece at
one time.
  p1*a1=[a/(a+b+c)]*[(a+b+c)/(b+c)]=[a/(b+c)] ---eqn.AN175
  p2*a2=[b/(a+b+c)]*[(a+b+c)/(a+c)]=[b/(a+c)] ---eqn.AN176
  p3*a3=[c/(a+b+c)]*[(a+b+c)/(a+b)]=[c/(a+b)] ---eqn.AN177
<a name="ch05b205">
remember
  bk=1/ak for k=1,2,3 ---eqn.AN164
  p1*b1=[a/(a+b+c)]*[(b+c)/(a+b+c)]=[(b+c)*a/(a+b+c)2] ---eqn.AN178
  p2*b2=[b/(a+b+c)]*[(a+c)/(a+b+c)]=[(a+c)*b/(a+b+c)2] ---eqn.AN179
  p3*b3=[c/(a+b+c)]*[(a+b)/(a+b+c)]=[(a+b)*c/(a+b+c)2] ---eqn.AN180

<a name="ch05b206">
Substitute eqn.AN175 to eqn.AN180 into
eqn.AN174 get
  1≦[a/(b+c) + b/(a+c) + c/(a+b)] ---eqn.AN181
   *[(b+c)*a + (a+c)*b + (a+b)*c]/(a+b+c)2

<a name="ch05b207">
compare eqn.AN181 with eqn.AN165 
need confirm next relation
  (b+c)*a + (a+c)*b + (a+b)*c ?=? ---eqn.AN182
  (a+b+c)2－(a2+b2+c2)
expand eqn.AN182 right side, get
  a2+b2+c2
  + (b+c)*a + (a+c)*b + (a+b)*c
  －(a2+b2+c2)
Red terms cancel. eqn.AN182 equality
confirmed.

<a name="ch05b208">
"With these substitutions the bound
(1.21) automatically gives us" eqn.AN165
which is true.
[[
Cauchy's inequality for (a,b,c) 
and (1,1,1) tells us that 
  (a+b+c)2≦3(a2+b2+c2) ---eqn.AN166
]]
2009-11-27-13-53 here

<a name="ch05b209">
2009-11-27-16-30
eqn.AN166 give
  1/3≦(a2+b2+c2)/(a+b+c)2 ---eqn.AN183
eqn.AN166 also give
  (a+b+c)2-(a2+b2+c2)≦2(a2+b2+c2) ---eqn.AN184
eqn.AN184/(a+b+c)2 get
  [(a+b+c)2-(a2+b2+c2)]/(a+b+c)2
  ≦2(a2+b2+c2)/(a+b+c)2 ---eqn.AN185
<a name="ch05b210">
ANY (a2+b2+c2)/(a+b+c)2 value satisfy 
eqn.AN185. 
eqn.AN183 say the smallest value is 1/3
We put 1/3 to eqn.AN185 is still true.
Finally get
  [(a+b+c)2-(a2+b2+c2)]/(a+b+c)2≦2/3 ---eqn.AN186
eqn.AN181 and eqn.AN186 conclude 
eqn.5.20 is true.
Second proof done.
2009-11-27-16-50 stop



2009-11-27-16-50 done proofread
2009-11-27-17-17 done spelling check

<a name=20091217>
2009-12-17-11-09 start
Update 2009-12-17 change all tute*.htm
(from tute0007.htm to tute0023.htm)
first:
Correct 'Limit' link from '#docA06'
to '#docA006'
second:
Change Javascript index to read from
jslist1e.js so that update jslist1e.js
then update ALL tute*.htm.
2009-12-17-11-23 stop

<a name="Copyright">　Index begin　Index this file
2009-06-19-10-48
If you are interested in inequality,
suggest you buy the book
The Cauchy-Schwarz Master Class
written by Prof. J. Michael Steele
The Cauchy-Schwarz Master Class is
this web page's textbook.

To buy textbook, that is to show thanks
to Prof. J.M. Steele's great work.
and it is also respect copyright law.
Thank you. Freeman 2009-06-19

The Cauchy-Schwarz Master Class
J. Michael Steele ★★★★★
ISBN 978-0-521-54677-5
2009-06-19-10-56