Algebra theory inequalities

Power mean inequality:

Power Mean 

For real numbers x1,x2,…,xn≥0x_1, x_2, \ldots, x_n \ge 0 and real p≠0p \ne 0, the power mean of order pp is:

Mp=(x1p+x2p+⋯+xnpn)1/pM_p = \left( \frac{x_1^p + x_2^p + \cdots + x_n^p}{n} \right)^{1/p}

Power Mean Inequality

If p<qp < q, then:

(x1p+x2p+⋯+xnpn)1/p≤(x1q+x2q+⋯+xnqn)1/q\left( \frac{x_1^p + x_2^p + \cdots + x_n^p}{n} \right)^{1/p} \le \left( \frac{x_1^q + x_2^q + \cdots + x_n^q}{n} \right)^{1/q}

with equality if and only if x1=x2=⋯=xnx_1 = x_2 = \cdots = x_n.

Example (n = 3, p = 2, q = 3)

Let’s say:

x1,x2,x3≥0x_1, x_2, x_3 \ge 0

Then the power mean inequality says:

(x12+x22+x323)1/2≤(x13+x23+x333)1/3\left( \frac{x_1^2 + x_2^2 + x_3^2}{3} \right)^{1/2} \le \left( \frac{x_1^3 + x_2^3 + x_3^3}{3} \right)^{1/3}


Ex1) Prove that

a4+b4+c4≥abc(a+b+c)a^4 + b^4 + c^4 \ge abc(a + b + c)

Solution:

PM4=(a4+b4+c43)1/4\text{PM}_4 = \left( \frac{a^4 + b^4 + c^4}{3} \right)^{1/4} PM1=(a+b+c3)\text{PM}_1 = \left( \frac{a + b + c}{3} \right)

PM4≥PM1⇒(a4+b4+c43)1/4≥a+b+c3\text{PM}_4 \ge \text{PM}_1 \quad \Rightarrow \quad \left( \frac{a^4 + b^4 + c^4}{3} \right)^{1/4} \ge \frac{a + b + c}{3}

Multiplying both sides by 3 and raising both sides to the power 4:

a4+b4+c4≥(a+b+c)(a+b+c3)3a^4 + b^4 + c^4 \ge (a + b + c) \left( \frac{a + b + c}{3} \right)^3


Using AM ≥ GM for the set {a,b,c}\{a, b, c\}:

a+b+c3≥(abc)1/3\frac{a + b + c}{3} \ge (abc)^{1/3}

Raising both sides to the power 3:

(a+b+c3)3≥abc\left( \frac{a + b + c}{3} \right)^3 \ge abc

Then multiplying both sides by a+b+ca + b + c:

(a+b+c)(a+b+c3)3≥abc(a+b+c)(a + b + c) \left( \frac{a + b + c}{3} \right)^3 \ge abc(a + b + c)

Therefore:

a4+b4+c4≥abc(a+b+c)a^4 + b^4 + c^4 \ge abc(a + b + c)

Hence Proved.

Ex2:

Prove that:

2S2S−a+2S2S−b+2S2S−c≥92\frac{2S}{2S - a} + \frac{2S}{2S - b} + \frac{2S}{2S - c} \ge \frac{9}{2}

where

S=a+b+c2S = \frac{a + b + c}{2}

Solution:

a+b+cb+c+a+b+ca+c+a+b+ca+b≥92\frac{a + b + c}{b + c} + \frac{a + b + c}{a + c} + \frac{a + b + c}{a + b} \ge \frac{9}{2}

This implies:

1b+c+1a+c+1a+b≥92(a+b+c)\frac{1}{b + c} + \frac{1}{a + c} + \frac{1}{a + b} \ge \frac{9}{2(a + b + c)}

Then, applying Power Mean inequality on the values 1b+c,1a+c,1a+b\frac{1}{b + c}, \frac{1}{a + c}, \frac{1}{a + b}:

PM1=((1b+c)1+(1a+c)1+(1a+b)13)1/1\text{PM}_1 = \left( \frac{ \left( \frac{1}{b + c} \right)^1 + \left( \frac{1}{a + c} \right)^1 + \left( \frac{1}{a + b} \right)^1 }{3} \right)^{1/1}

PM−1=((1b+c)1+(1a+c)1+(1a+b)13)−1\text{PM}_{-1} = \left( \frac{\left( \frac{1}{b + c} \right)^1 + \left( \frac{1}{a + c} \right)^1 + \left( \frac{1}{a + b} \right)^1}{3} \right)^{-1} =13[1b+c+1a+c+1a+b]= \frac{1}{3} \left[ \frac{1}{b + c} + \frac{1}{a + c} + \frac{1}{a + b} \right] PM−1=((1b+c)−1+(1a+c)−1+(1a+b)−13)−1\text{PM}_{-1} = \left( \frac{ \left( \frac{1}{b + c} \right)^{-1} + \left( \frac{1}{a + c} \right)^{-1} + \left( \frac{1}{a + b} \right)^{-1} }{3} \right)^{-1} =(b+c+a+c+a+b3)−1= \left( \frac{b + c + a + c + a + b}{3} \right)^{-1} =32(a+b+c)= \frac{3}{2(a + b + c)}


Starting with the power mean inequality:

PM−1≤PM1\text{PM}_{-1} \le \text{PM}_1

Substituting the expressions:

32(a+b+c)≤13(1b+c+1c+a+1a+b)\frac{3}{2(a + b + c)} \le \frac{1}{3} \left( \frac{1}{b + c} + \frac{1}{c + a} + \frac{1}{a + b} \right)

Multiplying both sides by 3:

92(a+b+c)≤1b+c+1c+a+1a+b\frac{9}{2(a + b + c)} \le \frac{1}{b + c} + \frac{1}{c + a} + \frac{1}{a + b}

Which implies:

2(a+b+c)≥91b+c+1c+a+1a+b2(a + b + c) \ge \frac{9}{\frac{1}{b + c} + \frac{1}{c + a} + \frac{1}{a + b}}

Hence proved.

Another simpler solution:

Applying the Arithmetic Mean ≥ Harmonic Mean (AM ≥ HM) inequality on the values 

b+c,  c+a,  a+bb + c, \; c + a, \; a + b:

(b+c)+(c+a)+(a+b)3≥31b+c+1c+a+1a+b\frac{(b + c) + (c + a) + (a + b)}{3} \ge \frac{3}{\frac{1}{b + c} + \frac{1}{c + a} + \frac{1}{a + b}}

Ex3:

Given:

a2+b2+c2=27,where a,b,c>0a^2 + b^2 + c^2 = 27,\quad \text{where } a, b, c > 0

Prove that:

a3+b3+c3≥81a^3 + b^3 + c^3 \ge 81

Solution:
PM2 = [(a^2 + b^2 + c^2)/3]^(1/2)
PM3 = [(a^3 + b^3 + c^3)/3]^(1/3)
PM3 >= PM2 = (27/3)^1/2 = 3
[(a^3 + b^3 + c^3)/3]^(1/3) >= 3
=> (a^3 + b^3 + c^3)/3 >= 3^3 = 27
=> (a^3 + b^3 + c^3) >= 27*3 = 81 H.P.



Chebyshev Inequality: (Intuitive explanation)

Given sequences of positive numbers in increasing order:
a1,a2,a3,…,ana_1, a_2, a_3, \ldots, a_n
b1,b2,b3,…,bnb_1, b_2, b_3, \ldots, b_n (in increasing order)


(a1+a2+a3+⋯+ann)(b1+b2+b3+⋯+bnn)≤a1b1+a2b2+a3b3+⋯+anbnn\left( \frac{a_1 + a_2 + a_3 + \cdots + a_n}{n} \right) \left( \frac{b_1 + b_2 + b_3 + \cdots + b_n}{n} \right) \leq \frac{a_1 b_1 + a_2 b_2 + a_3 b_3 + \cdots + a_n b_n}{n}

Another way to express the same result:

Let

aˉ=1n∑i=1nai,bˉ=1n∑i=1nbi,ab‾=1n∑i=1naibi.\bar{a} = \frac{1}{n} \sum_{i=1}^{n} a_i,\quad \bar{b} = \frac{1}{n} \sum_{i=1}^{n} b_i,\quad \overline{ab} = \frac{1}{n} \sum_{i=1}^{n} a_i b_i.

Then the inequality is simply

aˉ bˉ≤ab‾\bar{a} \, \bar{b} \leq \overline{ab}

whenever the two lists are sorted the same way (both non-decreasing or both non-increasing).


A specific version of this (when both sequences are the same) yields:
Square of mean <= Mean of squares


(a1+a2+a3+⋯+ann)2≤a12+a22+a32+⋯+an2n


Ex1:
Prove that

(a2+b2+c2)(a3+b3+c3)≤3(a5+b5+c5)(a^2 + b^2 + c^2)(a^3 + b^3 + c^3) \leq 3(a^5 + b^5 + c^5)

Given:
Assume the ordering (also given a,b,c > 0):

a2≤b2≤c2anda3≤b3≤c3a^2 \leq b^2 \leq c^2 \quad \text{and} \quad a^3 \leq b^3 \leq c^3

Then use the Chebyshev inequality:

(a2+b2+c23)(a3+b3+c33)≤(a5+b5+c53)\left( \frac{a^2 + b^2 + c^2}{3} \right) \left( \frac{a^3 + b^3 + c^3}{3} \right) \leq \left( \frac{a^5 + b^5 + c^5}{3} \right)

Multiply both sides by 33 to get the desired inequality.

Ex2:


Prove that:

a8+b8+c8≥(a2+b2+c2)(a6+b6+c6)3a^8 + b^8 + c^8 \geq \frac{(a^2 + b^2 + c^2)(a^6 + b^6 + c^6)}{3}

And from there also prove:

a8+b8+c8≥a3b3c3(1a+1b+1c)
Solution:
First part is straightforward application of Chebyshev Inequality as shown in the last example.
Then:

Applying the AM ≥ GM inequality to the terms 

a6,b6,c6a^6, b^6, c^6, we have:

a6+b6+c63≥a6b6c63=a2b2c2\frac{a^6 + b^6 + c^6}{3} \geq \sqrt[3]{a^6 b^6 c^6} = a^2 b^2 c^2

Multiplying both sides by a2+b2+c2a^2 + b^2 + c^2, we get new bound on RHS.

a6+b6+c63⋅(a2+b2+c2)≥a2b2c2(a2+b2+c2)\frac{a^6 + b^6 + c^6}{3} \cdot (a^2 + b^2 + c^2) \geq a^2 b^2 c^2 (a^2 + b^2 + c^2)

Now, assume a≥b≥ca \geq b \geq c. By the Rearrangement Inequality, we know:

a2+b2+c2≥ab+bc+caa^2 + b^2 + c^2 \geq ab + bc + ca

Therefore:

a2b2c2(a2+b2+c2)≥a2b2c2(ab+bc+ca)a^2 b^2 c^2 (a^2 + b^2 + c^2) \geq a^2 b^2 c^2 (ab + bc + ca)

Now observe that:

a2b2c2(ab+bc+ca)=a3b3c3(1a+1b+1c)a^2 b^2 c^2 (ab + bc + ca) = a^3 b^3 c^3 \left( \frac{1}{a} + \frac{1}{b} + \frac{1}{c} \right)

So, we conclude:

a6+b6+c63⋅(a2+b2+c2)≥a3b3c3(1a+1b+1c)

H.P.


Cauchy–Schwarz Inequality

a1,a2,a3,…,an;b1,b2,b3,…,bna_1, a_2, a_3, \ldots, a_n \quad ; \quad b_1, b_2, b_3, \ldots, b_n

are real numbers.

(a1b1+a2b2+a3b3+…+anbn)2≤(a12+a22+a32+…+an2)(b12+b22+b32+…+bn2)(a_1b_1 + a_2b_2 + a_3b_3 + \ldots + a_n b_n)^2 \leq (a_1^2 + a_2^2 + a_3^2 + \ldots + a_n^2)(b_1^2 + b_2^2 + b_3^2 + \ldots + b_n^2)

Equality will hold if

a1b1=a2b2=…=anbn\frac{a_1}{b_1} = \frac{a_2}{b_2} = \ldots = \frac{a_n}{b_n}

Important:
Unlike Chebyshev inequality, this doesn't expect the numbers to be in increasing order.

Let's see a simple example with 2 sequences of length 2:


Cauchy-Schwarz Inequality Example (Length 2 Sequences)

Let a=(a1,a2)\mathbf{a} = (a_1, a_2) and b=(b1,b2)\mathbf{b} = (b_1, b_2).

The Cauchy-Schwarz inequality states:

(a12+a22)(b12+b22)≥(a1b1+a2b2)2(a_1^2 + a_2^2)(b_1^2 + b_2^2) \geq (a_1 b_1 + a_2 b_2)^2

Step 1: Expand both sides

Left-hand side:

(a12+a22)(b12+b22)=a12b12+a12b22+a22b12+a22b22(a_1^2 + a_2^2)(b_1^2 + b_2^2) = a_1^2 b_1^2 + a_1^2 b_2^2 + a_2^2 b_1^2 + a_2^2 b_2^2

Right-hand side:

(a1b1+a2b2)2=a12b12+2a1a2b1b2+a22b22(a_1 b_1 + a_2 b_2)^2 = a_1^2 b_1^2 + 2 a_1 a_2 b_1 b_2 + a_2^2 b_2^2

Step 2: Subtract right-hand side from left-hand side

(a12b12+a12b22+a22b12+a22b22)−(a12b12+2a1a2b1b2+a22b22)=a12b22+a22b12−2a1a2b1b2\begin{align*} & (a_1^2 b_1^2 + a_1^2 b_2^2 + a_2^2 b_1^2 + a_2^2 b_2^2) - (a_1^2 b_1^2 + 2 a_1 a_2 b_1 b_2 + a_2^2 b_2^2) \\ & = a_1^2 b_2^2 + a_2^2 b_1^2 - 2 a_1 a_2 b_1 b_2 \end{align*}

Step 3: Factor the result

a12b22+a22b12−2a1a2b1b2=(a1b2−a2b1)2a_1^2 b_2^2 + a_2^2 b_1^2 - 2 a_1 a_2 b_1 b_2 = (a_1 b_2 - a_2 b_1)^2

Conclusion:

(a12+a22)(b12+b22)−(a1b1+a2b2)2=(a1b2−a2b1)2≥0(a_1^2 + a_2^2)(b_1^2 + b_2^2) - (a_1 b_1 + a_2 b_2)^2 = (a_1 b_2 - a_2 b_1)^2 \geq 0

Since the square of any real number is non-negative, the inequality is always true.

Ex1:

 Prove that

ab+bc+ca≥(a+b+c)2ab+bc+ca\frac{a}{b} + \frac{b}{c} + \frac{c}{a} \geq \frac{(a + b + c)^2}{ab + bc + ca} (a+b+c)2≤(ab+bc+ca)(ab+bc+ca)(a + b + c)^2 \leq \left( \frac{a}{b} + \frac{b}{c} + \frac{c}{a} \right)(ab + bc + ca) ≤[(ab)2+(bc)2+(ca)2][(ab)2+(bc)2+(ca)2]\leq \left[ \left( \frac{a}{b} \right)^2 + \left( \frac{b}{c} \right)^2 + \left( \frac{c}{a} \right)^2 \right] \left[ (\sqrt{ab})^2 + (\sqrt{bc})^2 + (\sqrt{ca})^2 \right] a1,a2,a3withab,bc,caa_1, a_2, a_3 \quad \text{with} \quad \frac{a}{\sqrt{b}}, \frac{b}{\sqrt{c}}, \frac{c}{\sqrt{a}} b1,b2,b3withab,bc,cab_1, b_2, b_3 \quad \text{with} \quad \sqrt{ab}, \sqrt{bc}, \sqrt{ca} (a1b1+a2b2+a3b3)2≤(a12+a22+a32)(b12+b22+b32)(a_1 b_1 + a_2 b_2 + a_3 b_3)^2 \leq (a_1^2 + a_2^2 + a_3^2)(b_1^2 + b_2^2 + b_3^2) (a+b+c)2≤(ab+bc+ca)(ab+bc+ca)(a + b + c)^2 \leq \left( \frac{a}{b} + \frac{b}{c} + \frac{c}{a} \right)(ab + bc + ca)

Ex2.


Prove that

(a3b+b3c+c3d+d3a)(ab3+bc2+cd3+da3)≥(a2b2+b2c2+c2d2+d2a2)2(a^3b + b^3c + c^3d + d^3a)(ab^3 + bc^2 + cd^3 + da^3) \geq (a^2b^2 + b^2c^2 + c^2d^2 + d^2a^2)^2

from there prove that

(a3b+b3c+c3d+d3a)(ab3+bc2+cd3+da3)≥16(abcd)2(a^3b + b^3c + c^3d + d^3a)(ab^3 + bc^2 + cd^3 + da^3) \geq 16(abcd)^2

Solution:
First part:

Apply Cauchy–Schwarz to the 4-tuples

x=(a3b, b3c, c3d, d3a),y=(ab3, bc3, cd3, da3)x=\big(\sqrt{a^{3}b},\ \sqrt{b^{3}c},\ \sqrt{c^{3}d},\ \sqrt{d^{3}a}\big),\qquad y=\big(\sqrt{ab^{3}},\ \sqrt{bc^{3}},\ \sqrt{cd^{3}},\ \sqrt{da^{3}}\big)

(for a,b,c,d≥0a,b,c,d\ge 0). Then

(∑xi2)(∑yi2)  ≥  (∑xiyi)2.\big(\sum x_i^2\big)\big(\sum y_i^2\big)\;\ge\; \big(\sum x_i y_i\big)^2 .

Here,

∑xi2=a3b+b3c+c3d+d3a,∑yi2=ab3+bc3+cd3+da3,\sum x_i^2=a^3b+b^3c+c^3d+d^3a,\qquad \sum y_i^2=ab^3+bc^3+cd^3+da^3,

and

∑xiyi=a3b⋅ab3+⋯=a2b2+b2c2+c2d2+d2a2.\sum x_i y_i =\sqrt{a^{3}b\cdot ab^{3}}+\cdots = a^2 b^2+b^2 c^2+c^2 d^2+d^2 a^2 .

Therefore

(a3b+b3c+c3d+d3a) (ab3+bc3+cd3+da3)  ≥  (a2b2+b2c2+c2d2+d2a2)2,(a^3 b + b^3 c + c^3 d + d^3 a)\,(ab^3 + bc^3 + cd^3 + da^3) \;\ge\; \big(a^2 b^2 + b^2 c^2 + c^2 d^2 + d^2 a^2\big)^2,

as required.

For the second part, simply do A.M >= G.M. for the terms on RHS.


Comments

Post a Comment

Popular posts from this blog

IOQM 2024 Paper solutions (Done 1-21, 29)

Image
Q1 (number-theory). The smallest positive integer that does not divide 1 × 2 × 3 × 4 × 5 × 6 × 7 × 8 × 9 is: Solution : This product has all the integers from 1 to 9. So smallest integer not dividing it would be the next prime after 9. Which is 11. Answer: 11 Q2 (combinatorics): The number of four-digit odd numbers having digits 1, 2, 3, 4, each occurring exactly once, is: Solution: Last digit has to be 1 or 3: 2C1 Choosing remaining 3 digits: 3C3 Arranging those 3 digits: 3! Answer: 2C1*3C3*3! = 12 Q3 (number-theory): The number obtained by taking the last two digits of \(5^{2024}\) in the same order is: Solution: To get last 2 digits from number, divide by 100 and take the remainder. So we have to compute mod 100. 25 mod 100 = 25 25.5 mod 100 = 125 mod 100 = 25 5^3.5 mod 100 = 25.5 mod 100 = 25 5^4.5 mod 100 = 25.5 mod 100 = 25 ..... So: 5^2024 mod 100 = 25. Q4 (geometry): Let ABCD be a quadrilateral with \(\angle ADC = 70^\circ\), \(\angle ACD = 70^\circ\), \(\angle ACB = 10^\circ\...
Read more

Combinatorics DPP - RACE 6 - Q16 pending discussion

Image
Q1 . A question paper consists of two sections. Section A has 7 questions and section B has 8 questions. A student has to answer 10 questions out of these 15 questions. The number of ways in which he can answer if he must answer at least 3 of section A and at least 4 of the section B is: Solution: One wrong way to solve this: For the mandatory questions: 7C3*8C4 Now 3 more questions need to be answered from 4 of A and 4 of B. Cases: 3A,0B | 2A,1B | 1A,2B | 0A,3B 4C3*4C0 + 4C2*4C1 + 4C1*4C2 + 4C0*4C1 = 4 + 24 + 24 + 4 = 56 Finally: 7C3*8C4*56 = 35*70*56 = 137200 Why is it wrong? Let's say we chose A1,A2,A3 as mandatory from A and then chose A4,A5,A6 when we did 4C3*4C0 for (3A,0B). But we could have done it the other way round also, i.e. choose A4,A5,A6 as mandatory and then choose A1,A2,A3. So there is overcounting. Correct Solution : Simply create the cases for A,B: (3,7),(4,6),(5,5),(6,4) 7C3*8C7 + 7C4*8C6 + 7C5*8C5 + 7C6*8C4 = 2926. Q2 . A kindergarten teacher has 25 kids in her...
Read more

IOQM 2023 solutions

Image
Q1. Let n be a positive integer such that 1 ≤ n ≤ 1000 . Let M n be the number of integers in the set X n = { 4 n + 1 , 4 n + 2 , … , 4 n + 1000 } . Let a = max ⁡ { M n : 1 ≤ n ≤ 1000 } , and b = min ⁡ { M n : 1 ≤ n ≤ 1000 } . a = \max\{M_n : 1 \leq n \leq 1000\}, \quad \text{and} \quad b = \min\{M_n : 1 \leq n \leq 1000\}. Find a − b a - b . Solution: Quick tip: If n^2 = k then (n+1)^2 = k + (2n + 1) We will use this here. Also as the numbers grow larger the gap between 2 perfect squares becomes less and less. For. e.g. there are 10 perfect squares between 1 and 100 but only 4 perfect squares between 101 and 200. So X1 = {sqrt(5) ... sqrt(1004)} will have the most number of perfect squares. While X1000 = {sqrt(4001)...sqrt(5000)} will have the least. In X1 the first integer square root is 3 and we know that 1024 is the square of 32 so the last integer will be 31. Total: 31 - 3 + 1 = 29 integers in X1. In X1000, We know that 64^2 = 4096 so 64 is the first integer. 70^2 = 4900 and ...
Read more