inductive proof exercise

**blablablerg** · November 10th 2009, 02:48 PM

Hi guys, im trying to figure out this problem:

prove that:

$\frac{1}{n}\displaystyle\sum_{i=1}^n x_i \geq \left(\displaystyle\prod_{i=1}^n x_i\right)^\frac{1}{n}$

for positive integers n and postive real numbers $x_i$

It does not seem to be possible to give a direct proof of this result using induction on $n$ . However, it can be proved for $n = 2^m$ for $m \geq 0$ by induction on $m$ . The general result now follows by proving the converse of the usual inductive step: if the result holds for $n = k +1$ , where $k$ is a positive integer, then it holds for $n = k$ .

the only step i can figure out is substituting $n$ for $2^m$ , resulting in:
$\frac{1}{2^m}\displaystyle\sum_{i=1}^{2^m} x_i \geq \left(\displaystyle\prod_{i=1}^{2^m} x_i\right)^\frac{1}{2^m}$

and then im stuck (after hours of fiddling with this inequality). i hope someone can help, thanks in advance

**tonio** · November 11th 2009, 03:16 PM

Originally Posted by blablablerg

Hi guys, im trying to figure out this problem:
the only step i can figure out is substituting $n$ for $2^m$ , resulting in:
$\frac{1}{2^m}\displaystyle\sum_{i=1}^{2^m} x_i \geq \left(\displaystyle\prod_{i=1}^{2^m} x_i\right)^\frac{1}{2^m}$

and then im stuck (after hours of fiddling with this inequality). i hope someone can help, thanks in advance

Yeah, Cauchy's proof of the means inequality uses powers of 2 and stuff, but it's rather involved and long. I propose the following much shorter and, imo, simpler and more elegant:

Lemma: if $y_1,...,y_n\geq 0\,\,and\,\,\prod\limits_{k=1}^ny_k=1\,,\,\,then\, \,\sum\limits_{k=1}^ny_k\geq n$

$\mbox{First, prove that your problem's solution follows from the above lemma by putting}$

$y_i=\frac{x_i}{\left(\prod\limits_{k=1}^nx_k\right )^{1\slash n}}$

Next, prove the lemma by induction: for n = 1 it's clear, so we can assume it's true for n-1 and show for n. Now, if all the numbers are equal then the inequality is trivial, so

we may assume the numbers are in increasing order, and thus $x_1\leq 1\leq x_n$ (attention: if not all the numbers are equal then there must be numbers above and below 1).

The inductive hypothesis tells us that $x_2+...+x_{n-1}+x_1x_n\geq n-1$ (why?) , so:

$\sum\limits_{k=1}^nx_1=x_1+(x_2+....+x_{n-1}+x_1x_n)+x_n-x_1x_n\geq n-1+x_1+x_n-x_1x_n$ $\geq n+(x_n-1)-x_1(x_n-1)=n+(x_n-1)(1-x_1)\geq n$ (why??). Q.E.D.

Tonio

**santiagos11** · November 12th 2009, 06:22 PM

Are you trying to solve the problems of the book "an intro to mathematical reasoning" from Peter J. Eccles? I am. I already solve that problem, you can find the solution in wikepedia, read cauchy's proof which is the easier and the one I think the author intended us to use. The other proofs are more difficult to undestand?
It would be really nice if we keep in touch and try to solve all the problems.
here is the link:
http://en.wikipedia.org/wiki/AMGM

**blablablerg** · November 17th 2009, 06:38 AM

Hi, indeed i was trying to solve that problem from Eccles' book. And i must say, i find both proofs (the one from Cauchy and the one from tonio given here) quite difficult to follow.

But i guess these kind of problems are the hardest ones in the book, it is not really necessary to solve them to understand the basic concepts, but it is still fun to try

tonio: i tried to follow your reasoning but i wasnt able to completely follow it

i thought that if
$ y_i=\frac{x_i}{\left(\prod\limits_{k=1}^nx_k\right )^{1\slash n}} $

then
$ \sum\limits_{k=1}^ny_k=\frac{\sum\limits_{k=1}^nx_ k}{\left(\prod\limits_{k=1}^nx_k\right)^{1\slash n}} $

$ \frac{\sum\limits_{k=1}^nx_k}{\left(\prod\limits_{ k=1}^nx_k\right)^{1\slash n}}\geq n \geq 1 $
$ \frac{\frac{1}{n}\sum\limits_{k=1}^nx_k}{\left(\pr od\limits_{k=1}^nx_k\right)^{1\slash n}} \geq 1 $

therefore

$\frac{1}{n}\sum\limits_{k=1}^nx_k \geq {\left(\prod\limits_{k=1}^nx_k\right)^{1\slash n}}\$

i dont know if this is correct, but i could not figure out this step:

$ x_2+...+x_{n-1}+x_1x_n\geq n-1$

santiagos11: did you manage to solve the last problem of chapter 1?

**tonio** · November 17th 2009, 07:06 AM

Originally Posted by blablablerg

Hi, indeed i was trying to solve that problem from Eccles' book. And i must say, i find both proofs (the one from Cauchy and the one from tonio given here) quite difficult to follow.

But i guess these kind of problems are the hardest ones in the book, it is not really necessary to solve them to understand the basic concepts, but it is still fun to try

tonio: i tried to follow your reasoning but i wasnt able to completely follow it

i thought that if
$ y_i=\frac{x_i}{\left(\prod\limits_{k=1}^nx_k\right )^{1\slash n}} $

then
$ \sum\limits_{k=1}^ny_k=\frac{\sum\limits_{k=1}^nx_ k}{\left(\prod\limits_{k=1}^nx_k\right)^{1\slash n}} $

$ \frac{\sum\limits_{k=1}^nx_k}{\left(\prod\limits_{ k=1}^nx_k\right)^{1\slash n}}\geq n \geq 1 $
$ \frac{\frac{1}{n}\sum\limits_{k=1}^nx_k}{\left(\pr od\limits_{k=1}^nx_k\right)^{1\slash n}} \geq 1 $

therefore

$\frac{1}{n}\sum\limits_{k=1}^nx_k \geq {\left(\prod\limits_{k=1}^nx_k\right)^{1\slash n}}\$

i dont know if this is correct, but i could not figure out this step:

$ x_2+...+x_{n-1}+x_1x_n\geq n-1$

santiagos11: did you manage to solve the last problem of chapter 1?

You're mixing stuff here: on one hand, you've some problems with proving the lemma, and otoh you've problems applying the lemma to your particular case...or I misunderstood?

Anyway: in $x_2+...+x_{n-1}+x_1x_n$ we have the sum of n-1 numbers whose product is 1...! So by the ind. hypothesis their sum is greater than or equal n-1. That's all.

About appying the lemma to your problem: be VERY careful not to mix indexes! You wrote $ \sum\limits_{k=1}^ny_k=\frac{\sum\limits_{k=1}^nx_ k}{\left(\prod\limits_{k=1}^nx_k\right)^{1\slash n}} $ and you have k both in the sum and in the product...not good at all! Try $\sum\limits_{i=1}^ny_i=\frac{\sum\limits_{i=1}^nx_ i}{\left(\prod\limits_{k=1}^nx_k\right)^{1\slash n}}$

Anyway, now : $ \prod\limits_{i=1}^ny_i=\prod\limits_{i=1}^n\frac{ x_i}{\left(\prod\limits_{k=1}^nx_k\right)^{1\slash n}}=\frac{\prod\limits_{i=1}^nx_i}{\prod\limits_{k =1}^nx_k}=1$ , and thus the lemma tells you that $\sum\limits_{i=1}^ny_i\geq n$ and then you end the proof as you did above.

Tonio

**blablablerg** · November 18th 2009, 11:23 PM

Dear tonio,

thanks for all your help in the first place.

$x_2+...+x_{n-1}+x_1x_n$ we have the sum of n-1 numbers whose product is 1...! So by the ind. hypothesis their sum is greater than or equal n-1. That's all.

i was thinking that way about it, but i thought that a sum or product sequence is fixed. correct me if i'm wrong, but i thought that a list whose product is 1, and is increasing, should look like this:

for example:
1/3,1/2,1,2,3

if n-1 you get (by your example)

1/2,1,2,1

this changes the whole list itself, and i always thought that lists used in this way where fixed, and you could only add or remove numbers from the end (n-1, n+1).

**santiagos11** · November 21st 2009, 06:02 AM

blablablerg,
take a look at my page, i posted the solutions here.
As for the last problem, i thing we are suppose to see that it is ovious that that the number of regions is given by a(n) = n + C(n-1,2) + C(n-1,3) + C(n-1,4). So take this as a definition and show that this is indeed equivalent to the other formula. I think that this have to to with the fact that there cannot be 3 concurrent lines. If it was 4 concurrent lines, i think we would have to add another term, namely C(n-1,4), and so on. It is difficult to "see it". I does not even make sense to me.
http://student.fgcu.edu/ssalaza/Problems%20I.pdf
Another thing. I you have any suggestions for my solutions or any comments or find any mistakes, just let me know. I would really appreciate it.

**tonio** · November 21st 2009, 08:30 AM

Originally Posted by blablablerg

Dear tonio,

thanks for all your help in the first place.

i was thinking that way about it, but i thought that a sum or product sequence is fixed. correct me if i'm wrong, but i thought that a list whose product is 1, and is increasing, should look like this:

for example:
1/3,1/2,1,2,3

if n-1 you get (by your example)

1/2,1,2,1

this changes the whole list itself, and i always thought that lists used in this way where fixed, and you could only add or remove numbers from the end (n-1, n+1).

But look what we did: if we've the list $\frac{1}{3}\,,\,\frac{1}{2}\,,\,1\,,\,2\,,\,3$ , then we took $\frac{1}{2}\,,\,1\,,\,2\,,\,\frac{1}{3}*3=1$ ...!, so that the product of the n-1 numbers $\frac{1}{2}\,,\,1\,,\,2\,,\,1$ STILL is 1 and thus,

by the ind. hyp., their sum is > n-1...

All the rest remains as it is.

Tonio

**blablablerg** · November 24th 2009, 06:51 AM

Originally Posted by tonio

But look what we did: if we've the list

, then we took

...!, so that the product of the n-1 numbers

STILL is 1 and thus,

yes i understand that, but i thought the discription of a sum or product sequence was pretty strict, so that if you have e.g. sequence n: 1/3,1/2,1,2,3

n-1 has to be 1/3,1/2,1,2

but i guess i must be wrong here?

EDIT: o wait, i think i get it now, you are not redefining the list, just showing that the sequence has to be < n-1.

but i still find it kind of confusing tho, because a sequence defined that way is not a fixed list in the sense i discussed a couple of lines above..

**santiagos11** · November 24th 2009, 07:20 PM

why dont you try cauchy's proof. I think that one is the easiest to understand.

**blablablerg** · November 25th 2009, 12:28 PM

hey man i just checked that pdf you posted on the forum. did you make that yourself?

looks very nice. im gonna print those out and check them. right now i just started chapter 9.

are you planning to finish the whole book?

cu krishan

**santiagos11** · November 25th 2009, 03:30 PM

Well yeah. That's the plan. Althoough I dont have much time. That is why I'm looking for people who wants to contribute. A would really appreciate any comments or if you find any mistake in my solutions. By the way, I just finished chap 11. Now in chapter 12 is where it really gets hard until like chap 14. Then the last chapters are easy. I also posted partial solution to the first problems of unit II, but they are messy. I have not have timeto organize them.
Did you solve those 26 problems of unit I yet?

**blablablerg** · November 25th 2009, 11:50 PM

Hi Santiagos,

I for sure will check them out, I don't know when tho because i also have a tight schedule. It comes in pretty handy because i find the lack of the solutions to the problems a bit lacking.

IIRC, i solved all of part one except for the one this thread is about and the last one (because i couldnt figure out how that formula is constructed).

**santiagos11** · December 2nd 2009, 05:29 PM

blablablerg, did you finish comparing my solutions with your solutions?
Do your solutions agree with mine?

Thread: inductive proof exercise

LinkBack

Thread Tools

Display

inductive proof exercise

Similar Math Help Forum Discussions

inductive proof that the sum (r=0:n) of (n C r)^2 = (2n C n)

Inductive Proof

Inductive proof

help me with Inductive Proof #1

help...inductive proof???

Search Tags