Results 1 to 14 of 14

Math Help - inductive proof exercise

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    6

    inductive proof exercise

    Hi guys, im trying to figure out this problem:
    prove that:

    \frac{1}{n}\displaystyle\sum_{i=1}^n x_i \geq <br />
\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 <br />
\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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by blablablerg View Post
    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 <br />
\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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2009
    Posts
    37
    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Nov 2009
    Posts
    6
    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
    <br />
y_i=\frac{x_i}{\left(\prod\limits_{k=1}^nx_k\right  )^{1\slash n}}<br />

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


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

    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:

    <br />
x_2+...+x_{n-1}+x_1x_n\geq n-1

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

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by blablablerg View Post
    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
    <br />
y_i=\frac{x_i}{\left(\prod\limits_{k=1}^nx_k\right  )^{1\slash n}}<br />

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


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

    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:

    <br />
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  <br />
\sum\limits_{k=1}^ny_k=\frac{\sum\limits_{k=1}^nx_  k}{\left(\prod\limits_{k=1}^nx_k\right)^{1\slash n}}<br />
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 :  <br />
\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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Nov 2009
    Posts
    6
    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).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2009
    Posts
    37
    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.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Quote Originally Posted by blablablerg View Post
    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
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Nov 2009
    Posts
    6
    Quote 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..
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member
    Joined
    Oct 2009
    Posts
    37
    why dont you try cauchy's proof. I think that one is the easiest to understand.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Nov 2009
    Posts
    6
    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
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Junior Member
    Joined
    Oct 2009
    Posts
    37
    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?
    Last edited by santiagos11; November 25th 2009 at 03:47 PM.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Newbie
    Joined
    Nov 2009
    Posts
    6
    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).
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Junior Member
    Joined
    Oct 2009
    Posts
    37
    blablablerg, did you finish comparing my solutions with your solutions?
    Do your solutions agree with mine?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 5th 2010, 10:15 AM
  2. Inductive Proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 08:57 PM
  3. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: December 8th 2009, 01:11 AM
  4. help me with Inductive Proof #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 16th 2009, 10:16 AM
  5. help...inductive proof???
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 16th 2008, 03:11 PM

Search Tags


/mathhelpforum @mathhelpforum