Exam (elaborations)
MildorfInequalities
- Institution
- Nursing 220 Final Exam Review
Exam of 34 pages for the course Nursing 220 Final Exam Review at Nursing 220 Final Exam Review (MildorfInequalities)
[Show more]
Seller
Follow
Content preview
Olympiad InequalitiesThomas J. Mildorf
December 22, 2005
It is the purpose of this document to familiarize the reader with a wide range of theorems
and techniques that can be used to solve inequalities of the variety typically appearing on
mathematical olympiads or other elementary proof contests. The Standard Dozen is an
exhibition of twelve famous inequalities which can be cited and applied without proof in
a solution. It is expected that most problems will fall entirely within the span of these
inequalities. The Examples section provides numerous complete solutions as well as remarks
on inequality-solving intuition, all intended to increase the reader’s aptitude for the material
covered here. It is organized in rough order of difficulty. Finally, the Problems section
contains exercises without solutions, ranging from straightforward to quite difficult, for the
purpose of practicing techniques contained in this document.
I have compiled much of this from posts by my peers in a number of mathematical
communities, particularly the Mathlinks-Art of Problem Solving forums,1 as well as from
various MOP lectures,2 Kiran Kedlaya’s inequalities packet,3 and John Scholes’ site.4 I have
tried to take note of original sources where possible. This work in progress is distributed for
personal educational use only. In particular, any publication of all or part of this manuscript
without prior consent of the author, as well as any original sources noted herein, is strictly
prohibited. Please send comments - suggestions, corrections, missing information,5 or other
interesting problems - to the author at tmildorf@mit.edu.
Without further delay...
1
http://www.mathlinks.ro/Forum/ and http://www.artofproblemsolving.com respectively, though they
have merged into a single, very large and robust group. The forums there are also host to a considerable
wealth of additional material outside of inequalities.
2
Math Olympiad Program. Although some people would try to convince me it is the Math Olympiad
Summer Program and therefore is due the acronym MOSP, those who know acknowledge that the traditional
“MOP” is the preferred appellation.
3
The particularly diligent student of inequalities would be interested in this document, which is available
online at http://www.unl.edu/amc/a-activities/a4-for-students/problemtext/ineqs-080299.tex. Further ma-
terial is also available in the books Andreescu-Cartoaje-Dospinescu-Lascu, Old and New Inequalities, GIL
Publishing House, and Hardy-Littlewood-Pólya, Inequalities, Cambridge University Press. (The former is
elementary and geared towards contests, the latter is more technical.)
4
http://www.kalva.demon.co.uk/, where a seemingly inexhaustible supply of Olympiads is available.
5
Such as the source of the last problem in this document.
1
,1 The Standard Dozen
Throughout this lecture, we refer to convex and concave functions. Write I and I 0 for the
intervals [a, b] and (a, b) respectively. A function f is said to be convex on I if and only if
λf (x) + (1 − λ)f (y) ≥ f (λx + (1 − λ)y) for all x, y ∈ I and 0 ≤ λ ≤ 1. Conversely, if the
inequality always holds in the opposite direction, the function is said to be concave on the
interval. A function f that is continuous on I and twice differentiable on I 0 is convex on I
if and only if f 00 (x) ≥ 0 for all x ∈ I (Concave if the inequality is flipped.)
Let x1 ≥ x2 ≥ · · · ≥ xn ; y1 ≥ y2 ≥ · · · ≥ yn be two sequences of real numbers. If
x1 + · · · + xk ≥ y1 + · · · + yk for k = 1, 2, . . . , n with equality where k = n, then the sequence
{xi } is said to majorize the sequence {yi }. An equivalent criterion is that for all real numbers
t,
|t − x1 | + |t − x2 | + · · · + |t − xn | ≥ |t − y1 | + |t − y2 | + · · · + |t − yn |
We use these definitions to introduce some famous inequalities.
Theorem 1 (Jensen) Let f : I → R be a convex function. Then for any x1 , . . . , xn ∈ I
and any nonnegative reals ω1 , . . . , ωn ,
µ ¶
ω 1 x1 + · · · + ω n xn
ω1 f (x1 ) + · · · + ωn f (xn ) ≥ (ω1 + · · · + ωn ) f
ω1 + · · · + ωn
If f is concave, then the inequality is flipped.
Theorem 2 (Weighted Power Mean) If x1 , . . . , xn are nonnegative reals and ω1 , . . . , ωn
are nonnegative reals with a postive sum, then
µ ¶1
ω1 xr1 + · · · + ωn xrn r
f (r) :=
ω1 + · · · + ωn
is a non-decreasing function of r, with the convention that r = 0 is the weighted geometric
mean. f is strictly increasing unless all the xi are equal except possibly for r ∈ (−∞, 0],
where if some xi is zero f is identically 0. In particular, f (1) ≥ f (0) ≥ f (−1) gives the
AM-GM-HM inequality.
Theorem 3 (Hölder) Let a1 , . . . , an ; b1 , . . . , bn ; · · · ; z1 , . . . , zn be sequences of nonnegative
real numbers, and let λa , λb , . . . , λz positive reals which sum to 1. Then
(a1 + · · · + an )λa (b1 + · · · + bn )λb · · · (z1 + · · · + zn )λz ≥ aλ1 a bλ1 b · · · z1λz + · · · + aλnz bλnb · · · znλz
This theorem is customarily identified as Cauchy when there are just two sequences.
Theorem 4 (Rearrangement) Let a1 ≤ a2 ≤ · · · ≤ an and b1 ≤ b2 ≤ · · · ≤ bn be two
nondecreasing sequences of real numbers. Then, for any permutation π of {1, 2, . . . , n}, we
have
a1 b1 + a2 b2 + · · · + an bn ≥ a1 bπ(1) + a2 bπ(2) + · · · + an bπ(n) ≥ a1 bn + a2 bn−1 + · · · + an b1
with equality on the left and right holding if and only if the sequence π(1), . . . , π(n) is de-
creasing and increasing respectively.
2
,Theorem 5 (Chebyshev) Let a1 ≤ a2 ≤ · · · ≤ an ; b1 ≤ b2 ≤ · · · ≤ bn be two nondecreas-
ing sequences of real numbers. Then
a1 b1 + a2 b2 + · · · + an bn a1 + a2 + · · · + an b1 + b2 + · · · + bn a1 bn + a2 bn−1 + · · · + an b1
≥ · ≥
n n n n
Theorem 6 (Schur) Let a, b, c be nonnegative reals and r > 0. Then
ar (a − b)(a − c) + br (b − c)(b − a) + cr (c − a)(c − b) ≥ 0
with equality if and only if a = b = c or some two of a, b, c are equal and the other is 0.
Remark - This can be improved considerably. (See the problems section.) However, they
are not as well known (as of now) as this form of Schur, and so should be proven whenever
used on a contest.
Theorem 7 (Newton) Let x1 , . . . , xn be nonnegative real numbers. Define the symmetric
n
polynomials s0 , s1 , . . . , sn by (x + x1¡)(x
¢ + x2 ) · · · (x + xn ) = sn x + · · · + s1 x + s0 , and define
n
the symmetric averages by di = si / i . Then
d2i ≥ di+1 di−1
Theorem 8 (Maclaurin) Let di be defined as above. Then
p p p
d1 ≥ d2 ≥ 3 d3 ≥ · · · ≥ n dn
Theorem 9 (Majorization) Let f : I → R be a convex on I and suppose that the sequence
x1 , . . . , xn majorizes the sequence y1 , . . . , yn , where xi , yi ∈ I. Then
f (x1 ) + · · · + f (xn ) ≥ f (y1 ) + · · · + f (yn )
Theorem 10 (Popoviciu) Let f : I → R be convex on I, and let x, y, z ∈ I. Then for any
positive reals p, q, r,
µ ¶
px + qy + rz
pf (x) + qf (y) + rf (z) + (p + q + r)f
p+q+r
µ ¶ µ ¶ µ ¶
px + qy qy + rz rz + px
≥ (p + q)f + (q + r)f + (r + p)f
p+q q+r r+p
Theorem 11 (Bernoulli) For all r ≥ 1 and x ≥ −1,
(1 + x)r ≥ 1 + xr
3
, Theorem 12 (Muirhead) Suppose the sequence a1 , . . . , an majorizes the sequence b1 , . . . , bn .
Then for any positive reals x1 , . . . , xn ,
X X
xa11 xa22 · · · xann ≥ xb11 xb22 · · · xbnn
sym sym
where the sums are taken over all permutations of n variables.
Remark - Although Muirhead’s theorem is a named theorem, it is generally not favor-
ably regarded as part of a formal olympiad solution. Essentially, the majorization criterion
guarantees that Muirhead’s inequality can be deduced from a suitable application of AM-GM.
Hence, whenever possible, you should use Muirhead’s inequality only to deduce the correct
relationship and then explicitly write all of the necessary applications of AM-GM. For a
particular case this is a simple matter.
We now present an array of problems and solutions based primarily on these inequalities
and ideas.
2 Examples
When solving any kind of problem, we should always look for a comparatively easy solu-
tion first, and only later try medium or hard approaches. Although what constitutes this
notoriously indeterminate “difficulty” varies widely from person to person, I usually con-
sider “Dumbassing,” AM-GM (Power Mean), Cauchy, Chebyshev (Rearrangement), Jensen,
Hölder, in that order before moving to more clever techniques. (The first technique is de-
scribed in remarks after example 1.) Weak inequalities will fall to AM-GM, which blatantly
pins a sum to its smallest term. Weighted Jensen and Hölder are “smarter” in that the effect
of widely unequal terms does not cost a large degree of sharpness6 - observe what happens
when a weight of 0 appears. Especially sharp inequalities may be assailable only through
clever algebra.
Anyway, I have arranged the following with that in mind.
1. Show that for positive reals a, b, c
¡ 2 ¢¡ ¢
a b + b2 c + c2 a ab2 + bc2 + ca2 ≥ 9a2 b2 c2
Solution 1. Simply use AM-GM on the terms within each factor, obtaining
¡ 2 2 2
¢¡ 2 2 2
¢ ³ √3
´³ √
3
´
3
a b + b c + c a ab + bc + ca ≥ 3 a b c 3 3 3 a b c = 9a2 b2 c2
3 3 3
6
The sharpness of an inequality generally refers to the extent to which the two sides mimic each other,
particularly near equality cases.
4
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller modockochieng06. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for £6.48. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
62890 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy revision notes and other study material for 14 years now