Results 1 to 7 of 7

Thread: 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.

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

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

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

    Not sure what to do now.

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

    $\displaystyle P(2n):~\prod_{i=1}^{2n}x_i\le\left( \frac{\sum_{i=1}^{2n}x_i}
    {2n}\right)^{2n}$

    Need to show $\displaystyle 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
    3
    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.

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

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

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

    Not sure what to do now.


    Take $\displaystyle x_1,...,x_{n-1},x_n:=\frac{x_1+\ldots+x_{n-1}}{n-1}$, so that $\displaystyle 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$ $\displaystyle 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$ $\displaystyle \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) $\displaystyle P(2):~ x_1x_2 \le \frac{(x_1+x_2)^2}{4}$

    $\displaystyle P(2n):~\prod_{i=1}^{2n}x_i\le\left( \frac{\sum_{i=1}^{2n}x_i}
    {2n}\right)^{2n}$

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

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

    (2) $\displaystyle 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!:

    $\displaystyle 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$ $\displaystyle =\left(\frac{x_1+\ldots+x_n}{n}\cdot\frac{x_{n+1}+ \ldots+x_{2n}}{n}\right)^n$ $\displaystyle \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

    $\displaystyle 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

    $\displaystyle a\le b \wedge c \le d \implies ac \le bd $ ?
    If a, b, c and d are integers then take $\displaystyle a=b=c=-1$ and $\displaystyle d=1$. In this case $\displaystyle a\leq b$ means $\displaystyle -1\leq -1$ which is true and $\displaystyle c\leq d$ means $\displaystyle -1\leq 1$ which is also true. Now, $\displaystyle ac\leq bd$ means $\displaystyle (-1)*(-1)\leq (-1)*1$ and therefore $\displaystyle 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 $\displaystyle 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 $\displaystyle 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: Aug 3rd 2011, 10:47 AM
  2. help me with Inductive Proof #2
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 17th 2009, 03:20 AM
  3. help me with Inductive Proof #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 16th 2009, 10:16 AM
  4. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: Oct 7th 2009, 01:09 PM
  5. Inductive Proof help!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 25th 2009, 09:38 AM

Search Tags


/mathhelpforum @mathhelpforum