Results 1 to 7 of 7

Math Help - Inductive proof

  1. #1
    Senior Member
    Joined
    Jul 2006
    Posts
    364

    Inductive proof



    --------
    My attempts:

    a) We need to show that if P(n) is true then P(n-1) also is.

    x_n=\frac{\sum_{i=1}^{n-1}x_i}{n-1}, so

    P(n):~ x_1x_2\cdots x_n\le x_{n+1}^n and

    P(n-1):~ x_1x_2\cdots x_{n-1}\le x_{n}^{n-1}.

    Not sure what to do now.

    b) P(2):~ x_1x_2 \le \frac{(x_1+x_2)^2}{4}

    P(2n):~\prod_{i=1}^{2n}x_i\le\left( \frac{\sum_{i=1}^{2n}x_i}<br />
{2n}\right)^{2n}

    Need to show P(n) \wedge P(2) \implies P(2n). No idea what to do next.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by scorpion007 View Post


    --------
    My attempts:

    a) We need to show that if P(n) is true then P(n-1) also is.

    x_n=\frac{\sum_{i=1}^{n-1}x_i}{n-1}, so

    P(n):~ x_1x_2\cdots x_n\le x_{n+1}^n and

    P(n-1):~ x_1x_2\cdots x_{n-1}\le x_{n}^{n-1}.

    Not sure what to do now.


    Take x_1,...,x_{n-1},x_n:=\frac{x_1+\ldots+x_{n-1}}{n-1}, so that P(n)=x_1\cdot\ldots\cdot x_{n-1}\cdot\frac{x_1+\ldots+x_{n-1}}{n-1}\le \left(\frac{x_1+\ldots+x_{n-1}+\frac{x_1+\ldots+x_{n-1}}{n-1}}{n}\right)^n\Longleftrightarrow x_1\cdot\ldots\cdot x_{n-1}\cdot \frac{x_1+\ldots+x_{n-1}}{n-1}\le \left(\frac{nx_1+nx_2+\ldots+nx_{n-1}}{n(n-1)}\right)^n=\left(\frac{x_1+\ldots+x_{n-1}}{n-1}\right)^n \Longleftrightarrow x_1\cdot\ldots\cdot x_{n-1}\le \left(\frac{x_1+\ldots+x_{n-1}}{n-1}\right){n-1}=P(n-1)


    b) P(2):~ x_1x_2 \le \frac{(x_1+x_2)^2}{4}

    P(2n):~\prod_{i=1}^{2n}x_i\le\left( \frac{\sum_{i=1}^{2n}x_i}<br />
{2n}\right)^{2n}

    Need to show P(n) \wedge P(2) \implies P(2n). No idea what to do next.
    Since P(n) is true we get:

    (1) x_1\cdot\ldots\cdot x_n\le \left(\frac{x_1+\ldots+x_n}{n}\right)^n

    (2) x_{n+1}\cdot\ldots\cdot x_{2n}\le \left(\frac{x_{n+1}+\ldots+x_{2n}}{n}\right)^n

    Now multiply both inequalities above and use P(2) for the right side!:

    x_1\cdot\ldots\cdot x_n\cdot x_{n+1}\cdot\ldots\cdot x_{2n}\le \left(\frac{x_1+\ldots+x_n}{n}\right)^n\left(\frac  {x_{n+1}+\ldots+x_{2n}}{n}\right)^n =\left(\frac{x_1+\ldots+x_n}{n}\cdot\frac{x_{n+1}+  \ldots+x_{2n}}{n}\right)^n \buildrel\text{P(2)}\over\le\left[\displaystyle{\left(\frac{\frac{x_1+\ldots+x_n}{n}  +\frac{x_{n+1}+\ldots+x_{2n}}{n}}{2}\right)^2}\rig  ht]^n.

    Well, now just re-arrange cosmetically a little the rightmost side and you have there P(2n)

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jul 2006
    Posts
    364
    Thanks!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jul 2006
    Posts
    364
    I noticed you multiplied both sides of the inequality by different amounts. Is it true in general that

    a\le b \wedge c \le d \implies ac \le bd ?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    Posts
    10
    Hello scorpion007!

    Quote Originally Posted by scorpion007 View Post
    I noticed you multiplied both sides of the inequality by different amounts. Is it true in general that

    a\le b \wedge c \le d \implies ac \le bd ?
    If a, b, c and d are integers then take a=b=c=-1 and d=1. In this case a\leq b means -1\leq -1 which is true and c\leq d means -1\leq 1 which is also true. Now, ac\leq bd means (-1)*(-1)\leq (-1)*1 and therefore 1\leq -1 which is false.

    Best wishes,
    Seppel
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Jul 2006
    Posts
    364
    Thanks Seppel!

    Ah, but what if a,b,c,d \ge 0, like in the original question? Perhaps then it is true?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by scorpion007 View Post
    Thanks Seppel!

    Ah, but what if a,b,c,d \ge 0, like in the original question? Perhaps then it is true?
    Yes, it is then true.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Inductive Proof
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 3rd 2011, 10:47 AM
  2. help me with Inductive Proof #2
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 17th 2009, 03:20 AM
  3. help me with Inductive Proof #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 16th 2009, 10:16 AM
  4. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: October 7th 2009, 01:09 PM
  5. Inductive Proof help!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 25th 2009, 09:38 AM

Search Tags


/mathhelpforum @mathhelpforum