# Inductive proof

• Dec 6th 2009, 10:49 PM
scorpion007
Inductive proof
http://img24.imageshack.us/img24/6747/math16.png

--------
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}
{2n}\right)^{2n}$

Need to show $P(n) \wedge P(2) \implies P(2n)$. No idea what to do next.
• Dec 7th 2009, 05:22 AM
tonio
Quote:

Originally Posted by scorpion007
http://img24.imageshack.us/img24/6747/math16.png

--------
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}
{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
• Dec 7th 2009, 04:27 PM
scorpion007
Thanks!
• Dec 7th 2009, 04:58 PM
scorpion007
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$ ?
• Dec 8th 2009, 01:30 AM
Seppel
Hello scorpion007!

Quote:

Originally Posted by scorpion007
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
• Dec 8th 2009, 01:47 AM
scorpion007
Thanks Seppel!

Ah, but what if $a,b,c,d \ge 0$, like in the original question? Perhaps then it is true?
• Dec 8th 2009, 02:11 AM
Defunkt
Quote:

Originally Posted by scorpion007
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.