Proving Inequalities by Exploiting Homogeneity

This is a powerful yet underestimated method for proving inequalities. A function /(is homogeneous of order к if /(A.ri,A.i'2,...,A.v„) = ?^f(x[,x2,...,xn) for every A > 0.

Consider the inequality /(хьх2,...,л:л)<0. The homogeneity of the inequality permits assuming without loss of generality additional constraints, for example, jci +x2+... + xn = 1, j:J" + x'{‘ + ... + x!" = 1, m > 1; xxx2...xn = 1. Indeed, the positive constant A can always be selected to scale the variables x,x2,...,x„ so that, for example, they add up to 1: Ax, +Лх2 +... + kxn =1. If instead of the original variables x,x2,...,x„, the scaled variables at =Xx,a2 = Xx2,...,a„ = Ax„ are substituted, the inequality will not be altered. As a result, the equivalent inequality f(aba2,...,a„)< 0 is obtained, with a constraint at + a2 +... + a„ = 1.

This technique will be illustrated with proving the special case of Holder’s inequality:

where a, > 0, b, > 0, c, > 0; i = 1

Constants Я, ju and v can always be chosen such that

Substituting in (3.41) the original variables a,,fe,,c, with the scaled variables Яahjibi,vcj gives

which, after the cancellations, yields the original inequality (3.41).

By setting x, = Aa,, yf = kb, and г, = Я/у, the equivalent inequality

is obtained, with constraints

After substituting the constraints (3.43) in (3.42), the proof reduces to demonstrating that

According to the AM-GM inequality, the following inequalities hold:

xi + yf + zf . .

---^ xty,zi, i = 1

Adding the n inequalities and considering (3.43), yields xyz+ ■■■ + x„ynzn < 1, which proves inequality (3.42) and the original inequality (3.41).

Proving Inequalities by a Mathematical Induction

Commonly, the method of mathematical induction for proving an inequality, stated for an arbitrary number n of variables, consists of the following steps.

  • 1. Proof of a base case (for example, that the inequality holds for n = 2 variables).
  • 2. Induction hypothesis: assuming that the inequality holds for n = к variables
  • (*>2).
  • 3. Inductive step: Proof that whenever the inequality holds for n=k variables, it also holds for n = к +1 variables.
  • 4. Conclusion: If steps 1, 2 and 3 have been proved, the inequality holds for n variables.

The method of mathematical induction will be illustrated by proving the inequality

where a, are non-negative real numbers.

1. Proof that the inequality holds for n = 2 variables. For n = 2, the inequality

becomes

Expanding the left-hand side gives

a a f 1 1 >

Since — + — > 2, (a, + a2) — + — > 4 = 22 and the base case has been a2 a, ' ^ a, a2,

proved.

2. Assume that the inequality holds for n = k (induction hypothesis).

3. It will be proven that if inequality (3.45) holds, the inequality also holds for n =k +1, (inductive step), which means proving the inequality

Transforming the left-hand side of inequality (3.46) gives

Because of the induction hypothesis and because Л!_ + > 2;

at* i "I

_5_+ >2;+ Ht±> 2, for equality (3.47), which is the left-hand

flt+1 “2 «Ш “k 1 ^

side of inequality (3.46), we have

The inductive step has been proved, therefore inequality (3.44) holds for all of integer n.

Example 3.6

This example is from Sedrakyan and Sedrakyan (2010).

Suppose that for the real numbers a,,fo,,ci( i = 1 the following conditions hold:

Then, it can be shown that the following general inequality (Sedrakyan inequality) holds:

Inequality (3.49) will be proved by induction. The proof starts with the basic case corresponding to n = 2. For, n = 2, inequality (3.49) becomes

To prove (3.50), it suffices to prove

The left-hand side of (3.51) can be transformed to:

From the conditions (3.48), a,/ci>a2/c2 and b|/ci>62/c2; therefore, (aic2-a2cd>0 and (b|C2-feed>0. As a result, the right side of (3.52) is nonnegative, —a2ci)(b|C2w|1jc[1 proves inequalities (3.51) and (3.50).

c,c2(c, +c2)

Now assume that inequality (3.49) is true for n = к > 2 (induction hypothesis):

It will be shown that inequality (3.53) is also true for n = k +1 (induction step).

Adding the term t0 both sides of (3.53), (ak/ck>= ak+1/ck+l; bk/ck>= Ьмы),

results in the inequality

Denoting x = Xf=iai< У = X,*L|b;, c,, the right-hand side of (3.54) becomes

xy | aMbM

z c<.+i . It can be demonstrated that x/z>=ak+1/ck+, and y/z>=bM/cM (the

proof is very similar to the one given in Section 9.4 and will not be duplicated here).

Because inequality (3.49) holds for the basic case n = 2, the next inequality holds: Finally,

This proves the induction step and inequality (3.49) for arbitrary n.

The inequality is sharp because equality is attained if a, / c, =a, / cjr i Ф j and

b; / C; = bj / Cj, i Ф j.

Proving Inequalities by Using the Properties of Convex/Concave Functions

The concept of convex/concave functions has already been introduced in formulating the Jensen inequality in Chapter 2. The concept will be discussed in greater detail here because it is a very powerful tool for proving inequalities. A function /(x) with a domain [a,b] is said to be convex if for all values x, and x2 in its domain (x,,x2 e [a,b]), the next inequality holds

where 0< w< 1.

The function f(x) is said to be strictly convex if equality in (3.56) holds only when w = 0; w = 1 or x, = x2. The function f(x) is strictly convex if for 0 < w < 1, x, Ф x2, the inequality

holds.

If /(x) is twice differentiable for all xe(a,b), and if the second derivative is non-negative (/"(x) > 0), the function /(x) is convex on (a,b). If /(x) is twice differentiable for all x e (a,b), and if the second derivative is positive (/"(x) > 0), the function /(x) is strictly convex on (a,b). For a strictly convex function/(x) of a single argument, the graph between any two points x, < x2 remains below the line segment joining the values /(x,), /(x2) corresponding to these points (Figure 3.1a). An example of a convex function is /(x) = x'" for m > 1 and x > 0.

For concave functions, the inequalities are reversed.

If /(x) is twice differentiable for all xe(a,b), and if for the second derivative /"(x) < 0 is fulfilled, the function /(x) is concave on (a,b). If /(x) is twice differentiable for all x e (a,b), and if the second derivative is negative, f"(x) < 0, the function /(x) is strictly concave on (a,b). For a strictly concave function/(x) of a single argument, the graph between any two points x, < x2 remains above the line segment joining

(a) A strictly convex function and (b) a strictly concave function of a single

FIGURE 3.1 (a) A strictly convex function and (b) a strictly concave function of a single

argument.

the values /(x,), /(x2) corresponding to these points (Figure 3.1b). An example of a concave function is f(x) = In .v. If a function f(x) is convex, the function -f(x) is concave and vice versa. Thus, f(x) = In x and g(x) = [x are both concave functions but -ln(x) and -л/х are both convex functions.

A sum of convex functions is a convex function and a sum of concave functions is a concave function.

A convex function does not mean that the function is increasing or decreasing. The absolute maximum of a convex function is never found in the interior of the domain where the arguments vary. It occurs at the boundary of the domain. Similarly, the absolute minimum of a concave function is never found in the interior of the domain where the arguments vary. It occurs at the boundary of the domain.

The concepts of convex/concave functions are very powerful and can be used to prove various inequalities.

Example 3.7

Consider the quadratic trinomial f(x) = ax2+bx+c where xeh,u2|, If a>the second derivative of the quadratic trinomial is positive, the function f(x) a ax2 +bx + c is convex and its global maximum is attained either at x = Uj or x = u2. The maximum is found by comparing f(uj) and f(u2), whichever is greater.

If a < 0, the second derivative of the quadratic trinomial is negative, the function f(x) = ax2 + bx + c is concave and its global minimum is attained either at x = Ui or x = u2. The global minimum is found by comparing f(U]) and f(u2), whichever is smaller. This provides a useful technique for proving inequalities.

Here is an example.

For the non-negative x,y,z for varying in the intervals 0z < 1 it can be shown that the inequality

holds.

This inequality can be proved by using convex functions.

Because the second partial derivatives of the function f(x,y,z)= x2(1-y)+x2(1-z)+y2(1-z)+y2(1-x)+z2(1-x)+z2(1-y) with respect to each of the variables x,yandz are non-negative (d2f(x,y,z) / <5x2 = 2 x(2 - y- z) > 0; d2f(x,y,z)/8y2 =2x(2-x-z)>0 and d2f(x,y,z)/8z2 = 2x(2-x-y)>0), the function f(x,y,z) is convex and attains its global maximum at the boundary of its domain. Because of the symmetry, the combination of values to check for a maximum is /"(0,0,0) = 0, /"(1,0,0) = 2, f( 1,1,0) = 2 and f( 1,1,1) = 0. The maximum value of the function f(x,y,z) is equal to 2, which proves the inequality.

Example 3.8

Determine the smallest constant C such that where 1 < x < 2.

f(x) = 2x2 -yfx -2lnx is a convex function because it is a sum of three convex functions: f(x) = lx2, f2(x) = -fx and f3(x) = -2ln(x).

Consequently, the maximum of f(x) is obtained at the ends of the interval [1,2]. There are two values to be compared: f(1) = 1 and f(2) = 5.2. The maximum is attained at x = 2 and is equal to 5.2. Therefore, the smallest value of the constant is C = 5.2.

Example 3.9

In the next example, for the non-negative numbers 0 < a < 1, 0 < Ь < 1 and 0 < c < 1, by using the concept of convexity, it can be shown that

The function f(a,b,c) =-J-r + --7-r + 7r-!-r + a2b2+fo2c2+c2a2 is continuous on a closed domain 0 < a < 1, 0 < fo < 1 and 0 < c < 1; therefore, according to the extreme value theorem from calculus, the function must attain its maximum and minimum in that domain.

The function f(a,b,c) =——^- +—V-r +—-—т + з2Ь2 +b2c2 + c2a2 is strictly (1 + a)2 (1 + fo)2 (1 + c)2 1

convex with respect to each of the variables a, b and c because

Because the function is strictly convex and continuous on the bounded and closed domain 0ies of the domain. The boundary points are:

The maximum is attained at f(1,1,1) = 15/4, hence inequality (3.58) holds.

Jensen Inequality

For any convex function f(x), the Jensen’s inequality states that

where vv, (/ = 1,...,«) are numbers that satisfy 0 < w, < 1 and w, + w, +... + vc„ = 1. For concave functions, the direction of inequality (3.59) is reversed.

The function In x is concave for positive values x > 0 because its second derivative (lnx)" = -l/x2 is negative. According to the Jensen inequality for concave functions,

holds. Using the properties of the logarithms

Because both sides of (3.60) are positive and ex is an increasing function, it follows that or finally

which is the AM-GM inequality.

If xi,x2,...,x„ are positive numbers, and a*- 0 is a real number, the number

(а 1/П

лГ +-*2 ++xn I is known as a power mean of the positive numbers.

Applying the AM-GM inequality to the numbers xf ,x“,...,x“ yields

from which is obtained.

If a > 1 and x, > 0 then /(x) = x“ is a convex function because /"(x) = a(a - l)x“'2 > 0- According to the Jensen inequality for convex functions,

If 0 < a < 1 and x, > 0 then /(x) = x“ is a concave function because /"(x) = a(a - l)x“~2 < 0. According to the Jensen inequality for concave functions

The next example illustrates another application of the Jensen inequality.

Example 3.10

For the non-negative numbers x > 0, у > 0 and z > 0, prove that

Proof. The function f(u) = u~V2 is a strictly convex function for и > 0 because f"(u)=(3/4)u~5/2 >0. According to the Jensen inequality, for a convex function f(x,y,z), the inequality

holds and for the convex function f(u) = и , the inequality

holds, from which inequality (3.64) follows. Because the function is strictly convex, the equality in (3.64) is attained only for x = у = z.

 
Source
< Prev   CONTENTS   Source   Next >