Proving AM-GM Inequality using Induction: Spivak 2-22

[Site]

Using the fact that the Arithmetic Mean of n numbers is greater than the Geometric Mean of those n numbers when n=2, prove by induction on k that the Arithmetic Mean is greater than the Geometric Mean for n=2^k.

I know how to prove the AM-GM inequality in general, but I can't figure out how to use induction to do so. Thanks in advance!

 

[tiny-tim]

Welcome to PF!

Hi Site! Welcome to PF!

As always in induction proofs …

start by writing the equation for 2^k and for 2^k+1 …

then find a way of getting from one to the other. ​

 

[nickalh]

Also, the "basis", in this case,
arithmetic mean of 2 numbers > geometric mean of 2 numbers
needs to be mentioned. I usually subtitle that part
Basis, n=1
or in this example
Basis, n=2.

The policy is to ask students to show some work before giving answers.

 

[Site]

Thanks for the warm welcome!

I'm still a little lost on the inductive step. This is my start:

Assume that the product of 2^k positive real numbers with a given average is maximized when each number is equal to the average. Now consider 2^(k+1) numbers which have an average A. Split the numbers into two groups of 2^k numbers each and call the product of the first group of numbers x and the product of the second group of numbers y. Let the average of the numbers of x be X and the average of the numbers in y be Y. Clearly A = (X+Y)/2

Based on our assumption, the quantity x is maximized when each element of x is equal to X and the quantity y is maximized when each element of y is equal to Y. So then x = X ^ (2^k) and y = Y ^ (2^k)

That's where I get stuck. I can't figure out how to tie that in with maximizing xy itself.

 

[nickalh]

A. Assume that the product of 2^k positive real numbers with a given average is maximized when each number is equal to the average.

Is this a theorem you've used in class? Get in the habit of justifying every statement at least knowing a reason in your mind. Ironically, even if the numbers we choose are maximized, there may exist other sets of k numbers which are not equal to the average, but (arithmetic mean)<= (geometric mean).

So the statement, A. and the idea of maximizing the numbers, should be excluded from the proof to include all possible sets of positive numbers.

Also, ironically, it may be simpler & easier to prove a stronger theorem. If we prove it is true for j=any positive integer, then we've proven it for any 2^k, because 2^k is a positive integer. Don't quote me on the simpler & easier until I've had some more time to think on it.
Hmmm, on second thought, the problem specifically defines k, then asks us to use induction on k. I guess if I'm going to follow the directions correctly, I need to go from 2^k to 2^(k+1)


I suspect the original statement

Using the fact that the Arithmetic Mean of n numbers is greater than the Geometric Mean

has been typed incorrectly. Because -2, -2 have -2 as an arithmetic mean, but the geometric mean is 2. The fact that the numbers must be positive is an essential restriction making the theorem true. Did the phrasing of the original question allow us to induct on sets of size j? Can one of the numbers be zero? Are there any other details, in the original question, we need to know? Also, in the future, please be more exact when typing the question in.

Don't let this discourage you. I hope to write more later. Stuff more directly helping you.

 

[Site]

Thanks for the reply, nichalh.

I was not using the assumption you quoted as a theorem. Since the argument holds for n=2, I used the assumption as the beginning of the inductive step.

I see what you're saying about proving it for j=any positive integer. Spivak outlined that process and I understand it. (And it is arguably easier to do it that way than this other way.) However, as a follow up, he asks the reader to create a different proof that uses induction on k in 2^k. I'm trying to prove it the way he instructed.

You're right, I messed up the question when I typed it up, haha. I don't know how to use Latex so I paraphrased it and botched it. To clarify, the numbers are nonnegative real numbers.

 

[nickalh]

I was not using the assumption you quoted as a theorem. Since the argument holds for n=2, I used the assumption as the beginning of the inductive step.

Duhhh, of course, my mistake.Fancy Notation:
On my web browser, as part of the editing box, there's a sigma/sum/ ∑ sign at the right end of the row with, Bold, Italic, underline. Click it to open a whole slew of notations. This box considers ∑ an operator. There's also subscript and superscript options. I can also click on someone's notation to "view source" and see how individual code works.

 

[nickalh]

A. Assume that the product of 2^k positive real numbers with a given average is maximized when each number is equal to the average.

I was not using the assumption you quoted as a theorem. Since the argument holds for n=2, I used the assumption as the beginning of the inductive step.

This post edited to correct my mistake in this post:
On first thought, although it's true for the basis. On second thought, it's still likely to lead us astray. See my earlier reply about the maximum.

Ironically, even if the numbers we choose are maximized, there may exist other sets of k numbers which are not equal to the average, but (arithmetic mean)<= (geometric mean).

Some ideas for the inductive step would be:
i. Let A= {2^k nonnegative numbers} & B= {2^k nonnegative numbers}, C= A $\bigcup$ B
ii. AM(A) > GM(A) by inductive hypothesis.
iii. AM(B) > GM(B) by inductive hypothesis.
What to do next:
iv. State/write your goal clearly with algebra, in this case not with words. Be sure to say it's the goal, otherwise many readers would think you're assuming the conclusion.
v. Replace AM(X) & GM(X) with algebraic definitions of AM & GM, for all three of A,B & C.
If you've seen it before, you may find $\prod^{2^k}_{i=1} \ x_{i},$ the product of $x_1 * x_2 * x_3* ... x_{2^k}$ a useful shorthand notation.
vi. what intermediate conclusions can you draw?
vii. algebraically manipulate GM
viii. How do GM(A), GM(B) and GM(C) relate to one another? These ideas apply to many proofs:
Restate any terms with algebraic definitions. Or sometimes vice-versa.
What intermediate conclusions can be drawn?
Write out what the goal is, what will the conclusion look like? Simply leaving it in your head, means one's brain is at least in part dedicated to remembering/ knowing the various facts.

Steps iv. through viii. are 80 or 90% of my proof.
Per https://www.physicsforums.com/showthread.php?t=414380"
& sound teaching/tutoring methods, students need to show their work before correct answers are shared. I've nearly completed the proof & am waiting on your answers to post my results, per PF policy.
It turns out my proof needs http://www.google.com/#sclient=psy&...eb8ccc40613db6&biw=1448&bih=883&pf=p&pdl=500", which basically assumes for the inductive hypothesis for EVERY value of k, k<=n. I've used the inductive hypothesis three times, once with n=2^1 and again for A then B.Fancy Notation:
On my web browser, as part of the editing box, there's a sigma/sum/ ∑ sign at the right end of the row with, Bold, Italic, underline. Click it to open a whole slew of notations. This box lists ∑ and & $\prod$ an operator. There's also subscript and superscript options. One can also click on someone's notation to "view source" and see how individual code works.