1985 Putnam Question A-2: Solution Part 6

Overview

In the previous section, we took a large step in our simplification of the given problem. The expression we were asked to minimize:

`\frac{A(R)+A(S)}{A(T)}`,

which originally contained three variables, has now been simplified to a single variable, `b_i`:

`1-\sum_{i=1}^{n+1}(b_i)^2`

where n is the number of rectangles inscribed in the acute triangle `T`.

The next step will require the Cauchy-Schwarz Inequality to solve (although there are other ways, this is my favorite inequality and therefore the method that we will be using).

In this section, we will state the Cauchy-Schwarz inequality, provide a proof with in-depth explanations every step of the way, and then show an example problem involving the inequality. The goal of this section is to allow the you to develop an understanding of the inequality and establish a reasonable level of comfort with it. We will be using what we learn in this section to simplify and solve our problem in section 7.

Statement and Explanation of the Cauchy-Schwarz Inequality

This inequality deals with two series of numbers, which we will call `q` and `r`. Each series will have n terms, and will look like:

`q_1, q_2, q_3, ... , q_n`, and
`r_1, r_2, r_3, ... , r_n`.

The statement of the inequality is given as:

`[\sum_{i=1}^{n}(q_i)^2]\cdot [\sum_{i=1}^{n}(r_i)^2]` `\geq [\sum_{i=1}^{n}(q_i\cdot r_i)]^2`

Where

`q_i=k\cdot r_i`

`k` is a constant positive integer (`k=1,2,3...`)

Now considering that the expression we are trying to solve is `1-\sum_{i=1}^{n+1}(b_n)^2`, it should be pretty obvious why we want to use this inequality.

But there is not much sense (for our purposes, anyway) in using this tool if we do not understand how it works.

Look at the inequality and consider the situation where `n=1`

The inequality can now be written as simply `q^2\cdot r^2 \geq (q\cdot r)^2`

Rearranging how we write the above,

`q^2\cdot r^2 \geq q^2\cdot r^2`

and the two will be equal given any values of `q` and `r`, meaning that this equality holds true for this base case.

For a slightly more complicated scenario, let `n=2`

Now the inequality can be written as:

`(q_1^2+q_2^2)\cdot (r_1^2+r_2^2)` `\geq |q_1\cdot r_1 +q_2\cdot r_2|^2`

To make this example easier, we can let `q_1=a`, `q_2=b`, `r_1=c`, and `r_2=d`

Now we can write the inequality as:

`(a^2+b^2)\cdot(c^2+d^2)\geq |a\cdot b + c\cdot d |^2`

Is this true for all values?

For starters, let `a=b=c=d=1`

`(1^2+1^2)\cdot (1^2+1^2)\geq |1\cdot 1 + 1\cdot 1|^2`

`2\cdot 2 \geq (1+1)^2`

so, according to the inequality,

`4\geq 4`,

which is true

Now what if we said `a=b=c=1`, but `d=2`?

Now we would get:

`(1^2+1^2)\cdot (1^2+2^2)\geq |1\cdot 1 + 1\cdot 2|^2`

`(1+1)\cdot (1+4)\geq (1+2)^2`

`2\cdot 5 \geq 3^2`

`10 \geq 9`

Which is also true.

But lets take a moment to consider what happened when we changed one of the variables to 2. When all of the variables were equal, the inequality gave equal values on each side. But when one of the variables became larger, the difference became larger.

Lets examine this pattern further. Let `a=b=c=d=2`

These are again all the same value, although a larger one. If our hypothesis holds, we should see equality once again.

The inequality will now give:

`(2^2+2^2)\cdot (2^2+2^2)\geq (2\cdot 2+2\cdot 2)^2`

`(4+4)\cdot (4+4) \geq 4^2`

`8\cdot 8 \geq 8^2`

`64 \geq 64`

It becomes clear that in the situation where all the numbers in the two series equal the same values, equality will hold.

So what about fractions? Consider the situation where `a=b=c=d=\frac{1}{2}`. For this situation, the inequality can be written as:

`(\frac{1}{2}^2+\frac{1}{2}^2)\cdot (\frac{1}{2}^2+\frac{1}{2}^2)` `\geq (\frac{1}{2}\cdot \frac{1}{2} +\frac{1}{2}\cdot \frac{1}{2})^2`

`(\frac{1}{4}+\frac{1}{4})\cdot (\frac{1}{4}+\frac{1}{4})\geq (\frac{1}{4}+\frac{1}{4})^2`

`\frac{1}{8}\cdot \frac{1}{8} \geq \frac{1}{8}^2`

`\frac{1}{64}\geq \frac{1}{64}`

Once again, it holds true that the two sides are equal when `k=1` for all `i`.

To be sure, lets consider `a=b=c=d=\frac{1}{10}` The inequality can be written as:

`(\frac{1}{10}^2+\frac{1}{10}^2)\cdot (\frac{1}{10}^2+\frac{1}{10}^2)` `\geq (\frac{1}{10}\cdot\frac{1}{10}+\frac{1}{10}\cdot \frac{1}{10})^2`

`(\frac{1}{100}+\frac{1}{100})\cdot (\frac{1}{100}+\frac{1}{100})` `\geq (\frac{1}{100}+\frac{1}{100})^2`

Now look closely, each side is the same value. So once again the inequality holds

But before when we varied the values, the difference between the right and left sides became greater. So lets consider one more example: let `a=1, b=9, c=4` and `d=13`. Now using these values in the inequality, we get:

`(1^2+9^2)\cdot (4^2+13^2)` `\geq(1\cdot 9+4\cdot 13)^2`

`(1+81)\cdot (16+169)\geq (9+52)^2`

`82\cdot 185\geq 61^2`

Now, using a caluclator if need be, you end up with:

`15170\geq 3721`

So we can see that this inequality does indeed work.

Furthermore, we know that a greater variance in the values of the numbers in the series translates to a larger difference between the left and right sides of the inequality.

Example

Quite often we will need to solve far more complicated inequalities than the ones presented above. Below is an example problem from the second edition of Putnam and Beyond by Razvan Gelca and Titu Andreescu, which serves as the standard preparatory volume for students interested in the Putnam Competition. The book is also widely renowned as a well-rounded Introduction to Problem Solving.

The question

If `a_1+a_2+...+a_n = n`, prove that `(a_1)^4+(a_2)^4+ ... (a_n^4) \geq n`

(From section 2.1.3, problem #111)

Answer

Using our statement of the Cauchy-Schwarz inequality,

`[\sum_{i=1}^{n}(q_i)^2]\cdot [\sum_{i=1}^{n}(r_i)^2]` `\geq [\sum_{i=1}^{n}(q_i\cdot r_i)]^2`

we can let

`q_i=a_i` (i.e. `q_1=a_1, q_2=a_2, q_3=a_3`, etc.).

We can assign any values we please to `r_i`, so let `r_i=1` for all `i`

`r_1=r_2=r_3=...=r_n=1`

Using these values, the inequality now looks like:

`[\sum_{i=1}^{n}(a_i)^2]\cdot [\sum_{i=1}^{n}(1^2)]` `\geq [\sum_{i=1}^{n}(a_i\cdot 1)]^2`

First let's look at the left side of the inequality.

`\sum_{i=1}^{n}(1^2)` `=\sum_{i=1}^{n}{1}=1+1+1+1+...+1` `=n`

We will leave the other term alone for now. So the left side of the inequality simplifies to:

`n\cdot\sum_{i=1}^{n}(a_i)^2`

Now looking at the right side:

`[\sum_{i=1}^{n}(a_i\cdot 1)]^2=\sum_{i=1}^{n}(a_i)^2`

In the problem it says that `a_1+a_2+...+a_n = n`, so

`\sum_{i=1}^{n}(a_i)^2=n^2`

Now we can rewrite the inequality as:

`n\cdot\sum_{i=1}^{n}(a_i)^2\geq n^2`

If we divide each side by `n`, we get

`\sum_{i=1}^{n}(a_i)^2\geq n`

Now we just have to implement the Cauchy-Schwarz inequality one more time. Looking back at the original formula:

`[\sum_{i=1}^{n}(q_i)^2]\cdot [\sum_{i=1}^{n}(r_i)^2]` `\geq [\sum_{i=1}^{n}(q_i\cdot r_i)]^2`

Just like last time, we will let `r_i=1` for all `i`
But now we will let `q_i=a_i^2`

Implementing these values, we get:

`[\sum_{i=1}^{n}(a_i)^2]\cdot [\sum_{i=1}^{n}1^2]` `\geq [\sum_{i=1}^{n}(a_i\cdot 1)]^2`

Simplifying as we did before, we get:

`n\cdot\sum_{i=1}^{n}(a_i)^4\geq(\sum_{i=1}^{n}(a_i)^2)^2`

But as we found after our first implementation of Cauchy-Schwarz,

`\sum_{i=1}^{n}(a_i)^2\geq n`

So we know that:

`(\sum_{i=1}^{n}(a_i)^2)^2\geq n^2`

So we can then write:

`n\cdot\sum_{i=1}^{n}(a_i)^4\geq(\sum_{i=1}^{n}(a_i)^2)^2\geq n^2`

Now we can actually eliminate the middle term altogether, since it is not actually pertinent to what we want to solve. Doing this, we get:

`n\cdot\sum_{i=1}^{n}(a_i)^4\geq n^2`

Once again, dividing each side by `n`, we get:

`\sum_{i=1}^{n}(a_i)^4\geq n`

Which is what we set out to prove in the first place, rendering this problem solved.

Summary

In this section, the sixth installment of the series, we introduced the Cauchy-Schwarz inequality. This inequality is considered important and useful in various fields of Mathematics, and will serve as the key to solving our problem.

We reviewed a number of basic examples with the inequality to develop a basic feel for how it works. Then we solved a problem from Putnam and Beyond that required the Cauchy-Schwarz inequality to answer correctly. This problem hopefully gave you a feel for some of the ways in which the Cauchy-Schwarz inequality can be implemented in more advanced problems. In Part 7 (the final section), we will pick up where we left off in Part 5, now using the Cauchy-Schwarz inequality to finally solve our problem.

Congratulations, you've made it to the final step, coming up next. Thanks for reading, I hope you enjoyed it!