Results 1 to 9 of 9

Math Help - Induction Proof

  1. #1
    Newbie
    Joined
    Aug 2007
    Posts
    5

    Induction Proof

    I'm stuck on this proof. I'm not sure if I've done something wrong, or if I'm just not seeing the next step. Any help would be appreciated.

    Let a1, a2, ..., an be positive real numbers such that a1*a2*...*an=1. Prove by induction that (1+a1)(1+a2)...(1+an) >= 2^n. The hint for the problem says to try a reduction by introducing another variable that replaces two specially chosen numbers from the sequence.

    The base case is simple enough. On the induction step, I assume a1*a2*...*an=1 implies (1+a1)(1+a2)...(1+an) >= 2^n. Then I let z=an*an+1. Thus, a1*a2*...*an-1*z implies (1+a1)(1+a2)...(1+an-1)(1+z) >= 2^n. I then multiplied both sides of the inequality by 2, to get:
    (1+a1)(1+a2)...(1+an-1)(1+z)(2) >= 2^(n+1)
    At this point, I figured I could try to show that (1+an)(1+an+1)>=(1+z)*2, which would lead to (1+a1)(1+a2)...(1+an)(1+an+1 >= 2^(n+1), but that didn't quite seem to work out.

    Any thoughts?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,668
    Thanks
    1618
    Awards
    1
    I can see no reason to use induction on this.
    We know that x^2  + y^2  \ge 2xy for each x&y.
    Thus we see that a > 0,\;b > 0\quad  \Rightarrow \quad a + b \ge 2\sqrt {ab} .
    From which we have \left( {\forall k} \right)\left[ {\left( {1 + a_k } \right) \ge 2\sqrt {a _k } } \right].
    Put it all together: \prod\limits_{k = 1}^n {\left( {1 + a_k } \right)}  \ge \prod\limits_{k = 1}^n {2\sqrt {a _k }  = 2^n \sqrt {\prod\limits_{k = 1}^n {\left( {a_k } \right)} }  = 2^n }.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2007
    Posts
    5
    Quote Originally Posted by Plato View Post
    I can see no reason to use induction on this.
    Unfortunately, the problem specifically asks for a proof by induction. Thank you for your help though. Any other thoughts?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,668
    Thanks
    1618
    Awards
    1
    Quote Originally Posted by Altaica View Post
    Any other thoughts?
    Yes indeed I have other thoughts.
    For years I have served as an editor for mathematics contest problems as well as commercial test. In that trade this is known as a “too cute problem”. Whoever wrote it has a “cute induction” proof in his/hers brain. But why do it that way when there is a much more standard and usual way of doing it.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2007
    Posts
    5
    I hear you, but the point of the exercise is for us to become more familiar with induction, and that's what I'm trying to figure out here. I'm very rusty, and I've given it my best shot and I'm stuck. I've tried everything I can think of. I've stared at the problem for hours, and I really don't know where to go next. Even a nudge in the right direction would be very much appreciated.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Plato View Post
    Yes indeed I have other thoughts.
    For years I have served as an editor for mathematics contest problems as well as commercial test. In that trade this is known as a “too cute problem”. Whoever wrote it has a “cute induction” proof in his/hers brain. But why do it that way when there is a much more standard and usual way of doing it.
    1. For practice of the technique

    2. Why do we need N>=72 proofs of Pythagoras's theorem?

    RonL
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Aug 2007
    Posts
    5
    Thanks guys for your feedback. Does anyone have any thoughts about solving this by induction?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,668
    Thanks
    1618
    Awards
    1
    Quote Originally Posted by Altaica View Post
    Does anyone have any thoughts about solving this by induction?
    Frankly, I do not see any way that induction applies to this problem.
    From the statement, for each n the set of positive numbers {a_k} may have nothing to do with one another.
    For example, for n=2 we may have the set \left\{ {2,\frac{1}{2}} \right\} while for n=3 we could have the set \left\{ {6,\frac{1}{2},\frac{1}{3}} \right\}.
    It is hard to see how one would employ the inductive step if the sets \left\{ {a_k } \right\}_{k = 1}^n \,\& \,\left\{ {b_k } \right\}_{k = 1}^{n + 1} are not related in any necessary way.

    Are you sure that you have given us the exact statement of the problem?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Aug 2007
    Posts
    5
    Here is the exact wording:
    "Let a1, a2, ..., an be positive real numbers such that a1*a2*...*an=1, n is a natural number greater than 0. Show by PMI (proof by mathematical induction) that (1+a1)(1+a2)...(1+an) >= 2^n."

    The hint for the problem says to try a reduction by introducing another variable that replaces two specially chosen numbers from the sequence. I figured this to mean that when we try the inductive step, we should reduce the problem to the nth case (which we assumed to be true), and then work from there. But, I got stuck shortly after that.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 07:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 12:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 03:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum