# Mathematical Induction Problem.

• Mar 30th 2010, 02:01 AM
Rel
Mathematical Induction Problem.
Using mathematical induction
proof this formula.

the formula is attached the jpg files
[Sorry I hard to using type that formula so I captured that :)

• Mar 30th 2010, 02:43 AM
sa-ri-ga-ma
For n = 2 you can prove it easily.
(a1+a2)/2 > sqrt(a1*a2)
(a1+a2) > 2*sqrt(a1*a2)
(a1+a2)^2 >4(a1*a2)
(a1+a2)^2 - 4(a1*a2) > 0
(a1-a2)^2 > 0
• Mar 30th 2010, 03:11 AM
Rel
Quote:

Originally Posted by sa-ri-ga-ma
For n = 2 you can prove it easily.
(a1+a2)/2 > sqrt(a1*a2)
(a1+a2) > 2*sqrt(a1*a2)
(a1+a2)^2 >4(a1*a2)
(a1+a2)^2 - 4(a1*a2) > 0
(a1-a2)^2 > 0

That's right but that only n=2 case
I want prove that formula using Mathematical induction by all of n.

sorry.
that is not answer in this problem.
• Mar 30th 2010, 08:09 AM
Quote:

Originally Posted by Rel
Using mathematical induction
proof this formula.

the formula is attached the jpg files
[Sorry I hard to using type that formula so I captured that :)

Hi Rel,

You could consider using the properties of logarithms.

P(n)

$\displaystyle \frac{a_1+a_2+a_3+....+a_n}{n}\ \ge\ \left(a_1\ a_2\ a_3\ ....a_n\right)^{\frac{1}{n}}$

We want to show that this causes P(n+1) to be true

P(n+1)

$\displaystyle \frac{a_1+a_2+a_3+...+a_n+a_{n+1}}{n+1}\ \ge\ \left(a_1\ a_2\ a_3\ ....a_n\ a_{n+1}\right)^{\frac{1}{n+1}}$

Proof

$\displaystyle \frac{a_1}{n}+\frac{a_2}{n}+\frac{a_3}{n}+...+\fra c{a_n}{n}\ \ge\ (a_1)^{\frac{1}{n}}\ (a_2)^{\frac{1}{n}}\ (a_3)^{\frac{1}{n}}\ ....(a_n)^{\frac{1}{n}}$

$\displaystyle \left(\frac{n}{n+1}\right)\left(\frac{a_1}{n}+\fra c{a_2}{n}+....+\frac{a_n}{n}+\frac{a_{n+1}}{n}\rig ht)\ \ge\ (a_1)^{\frac{1}{n+1}}\ (a_2)^{\frac{1}{n+1}}\ .....(a_n)^{\frac{1}{n+1}}\ (a_{n+1})^{\frac{1}{n+1}}$ ?

$\displaystyle \Rightarrow\ \frac{n}{n+1}\left[\frac{a_1}{n}+....+\frac{a_n}{n}\right]+\frac{a_{n+1}}{n+1}\ \ge\ (a_1)^{\frac{1}{n}\ \frac{n}{n+1}}\ (a_2)^{\frac{1}{n}\ \frac{n}{n+1}}....(a_n)^{\frac{1}{n}\ \frac{n}{n+1}}\ (a_{n+1})^{\frac{1}{n}\ \frac{n}{n+1}}$

$\displaystyle \Rightarrow\ \frac{n}{n+1}\left[\frac{a_1}{n}+....+\frac{a_n}{n}\right]+\frac{a_{n+1}}{n+1}\ \ge\ \left((a_1)^{\frac{1}{n}}\ (a_2)^{\frac{1}{n}}....(a_n)^{\frac{1}{n}}\right)^ {\frac{n}{n+1}}\ (a_{n+1})^{\frac{1}{n+1}}$

Now, notice that

$\displaystyle log\left[\left((a_1)^{\frac{1}{n}}\ (a_2)^{\frac{1}{n}}.....(a_n)^{\frac{1}{n}}\right) ^{\frac{n}{n+1}}\ (a_{n+1})^{\frac{1}{n+1}}\right]$ $\displaystyle =\frac{n}{n+1}\left((a_1)^{\frac{1}{n}}\ (a_2)^{\frac{1}{n}}...(a_n)^{\frac{1}{n}}\right)+\ frac{a_{n+1}}{n+1}$

and the proof follows since

$\displaystyle x>logx$

Whoops!! massive typo!! I left out the logs in the RHS
so there is no proof!!
• Mar 30th 2010, 09:48 AM
tonio
Quote:

Hi Rel,

You could consider using the properties of logarithms.

P(n)

$\displaystyle \frac{a_1+a_2+a_3+....+a_n}{n}\ \ge\ \left(a_1\ a_2\ a_3\ ....a_n\right)^{\frac{1}{n}}$

We want to show that this causes P(n+1) to be true

P(n+1)

$\displaystyle \frac{a_1+a_2+a_3+...+a_n+a_{n+1}}{n+1}\ \ge\ \left(a_1\ a_2\ a_3\ ....a_n\ a_{n+1}\right)^{\frac{1}{n+1}}$

Proof

$\displaystyle \frac{a_1}{n}+\frac{a_2}{n}+\frac{a_3}{n}+...+\fra c{a_n}{n}\ \ge\ (a_1)^{\frac{1}{n}}\ (a_2)^{\frac{1}{n}}\ (a_3)^{\frac{1}{n}}\ ....(a_n)^{\frac{1}{n}}$

$\displaystyle \left(\frac{n}{n+1}\right)\left(\frac{a_1}{n}+\fra c{a_2}{n}+....+\frac{a_n}{n}+\frac{a_{n+1}}{n}\rig ht)\ \ge\ (a_1)^{\frac{1}{n+1}}\ (a_2)^{\frac{1}{n+1}}\ .....(a_n)^{\frac{1}{n+1}}\ (a_{n+1})^{\frac{1}{n+1}}$ ?

$\displaystyle \Rightarrow\ \frac{n}{n+1}\left[\frac{a_1}{n}+....+\frac{a_n}{n}\right]+\frac{a_{n+1}}{n+1}\ \ge\ (a_1)^{\frac{1}{n}\ \frac{n}{n+1}}\ (a_2)^{\frac{1}{n}\ \frac{n}{n+1}}....(a_n)^{\frac{1}{n}\ \frac{n}{n+1}}\ (a_{n+1})^{\frac{1}{n}\ \frac{n}{n+1}}$

$\displaystyle \Rightarrow\ \frac{n}{n+1}\left[\frac{a_1}{n}+....+\frac{a_n}{n}\right]+\frac{a_{n+1}}{n+1}\ \ge\ \left((a_1)^{\frac{1}{n}}\ (a_2)^{\frac{1}{n}}....(a_n)^{\frac{1}{n}}\right)^ {\frac{n}{n+1}}\ (a_{n+1})^{\frac{1}{n+1}}$

Now, notice that

$\displaystyle log\left[\left((a_1)^{\frac{1}{n}}\ (a_2)^{\frac{1}{n}}.....(a_n)^{\frac{1}{n}}\right) ^{\frac{n}{n+1}}\ (a_{n+1})^{\frac{1}{n+1}}\right]$ $\displaystyle =\frac{n}{n+1}\left((a_1)^{\frac{1}{n}}\ (a_2)^{\frac{1}{n}}...(a_n)^{\frac{1}{n}}\right)+\ frac{a_{n+1}}{n+1}$

Surely you meant $\displaystyle \log\left[\left((a_1)^{\frac{1}{n}}\ (a_2)^{\frac{1}{n}}.....(a_n)^{\frac{1}{n}}\right) ^{\frac{n}{n+1}}\ (a_{n+1})^{\frac{1}{n+1}}\right]$ $\displaystyle =\frac{n}{n+1}\log\left((a_1)^{\frac{1}{n}}\ (a_2)^{\frac{1}{n}}...(a_n)^{\frac{1}{n}}\right)+\ frac{1}{n+1}\log a_{n+1}$ , but then I don't see clearly how to continue...

Tonio

and the proof follows since

$\displaystyle x>logx$

.
• Apr 2nd 2010, 09:44 AM
Thanks tonio,

starting from scratch,
we can apply a few manipulations for convenience...

If the following is true

$\displaystyle \frac{A_1+A_2+......+A_n}{n}\ \ge\ \sqrt[n]{A_1A_2....A_n}$

we attempt to prove that it causes

$\displaystyle \frac{A_1+A_2+....+A_n+A_{n+1}}{n+1}\ \ge\ \sqrt[n+1]{A_1A_2....A_nA_{n+1}}$

to be true.

Rewriting $\displaystyle a_i=\sqrt[n]{A_i}$ for i=1,2,....,n

we try to prove

$\displaystyle {a_1}^n+{a_2}^n+....+{a_n}^n\ \ge\ na_1a_2....a_n$

by showing that it causes

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+...{a_k}^{k+1}+{a_{k+1}}^{ k+1}\ \ge\ (k+1)a_1a_2....a_ka_{k+1}$

Proof

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+....+{a_k}^{k+1}+{a_{k+1}} ^{k+1}=a_1{a_1}^k+a_2{a_2}^k+....+\color{red}a_k\c olor{black}{a_k}^k+\color{blue}a_{k+1}\color{black }{a_{k+1}}^k$

To develop the inequality, the following may be utilised...

$\displaystyle x_1\ \ge\ x_2,\ y_1\ \ge\ y_2\ \Rightarrow\ x_1y_1+x_2y_2\ \ge\ x_1y_2+x_2y_1$

This is because

$\displaystyle x_1y_1+x_2y_2-(x_1y_2+x_2y_1)=x_1(y_1-y_2)-x_2(y_1-y_2)=(x_1-x_2)(y_1-y_2)\ \ge\ 0$

Hence, if the terms are arranged in decreasing order...

$\displaystyle a_1\ \ge\ a_2\ \ge\ a_3\ \ge.....\ge\ a_k\ \ge\ a_{k+1}$

$\displaystyle a_1{a_1}^k+a_2{a_2}^k+....+\color{red}a_k\color{bl ack}{a_k}^k+\color{blue}a_{k+1}\color{black}{a_{k+ 1}}^k\ \ge\ a_1{a_1}^k+a_2{a_2}^k+....+\color{blue}a_{k+1}\col or{black}{a_k}^k+\color{red}a_k\color{black}{a_{k+ 1}}^k$

Therefore

$\displaystyle a_1{a_1}^k+a_2{a_2}^k+...+a_k{a_k}^k+a_{k+1}{a_{k+ 1}}^k\ \ge\ (a_{k+1}{a_1}^k+a_{k+1}{a_2}^k+....a_{k+1}{a_k}^k) +a_k{a_{k+1}}^k$

$\displaystyle \ge\ a_{k+1}({a_1}^k+{a_2}^k+...+{a_k}^k)+a_k{a_{k+1}}^ k$

Hence

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+....{a_k}^{k+1}+{a_{k+1}}^ {k+1}\ \ge\ a_{k+1}({a_1}^k+{a_2}^k+...+{a_k}^k)+a_k{a_{k+1}}^ k$

Since the terms are arranged in decreasing order, then $\displaystyle a_i\ \ge\ a_{k+1}$

Hence

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+....{a_k}^{k+1}+{a_{k+1}}^ {k+1}\ \ge\ a_{k+1}({a_1}^k+{a_2}^k+...+{a_k}^k)+a_1a_2...a_ka _{k+1}$

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+....{a_k}^{k+1}+{a_{k+1}}^ {k+1}\ \ge\ [a_{k+1}]\left[({a_1}^k+{a_2}^k+...+{a_k}^k)+a_1a_2...a_k\right]$

If the original statement is true, $\displaystyle {a_1}^k+{a_1}^k+...+{a_k}^k\ \ge\ ka_1a_2...a_k$

then

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+....+{a_k}^{k+1}+{a_{k+1}} ^{k+1}\ \ge\ a_{k+1}[(ka_1a_2...a_k)+a_1a_2...a_k]$

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+....+{a_k}^{k+1}+{a_{k+1}} ^{k+1}\ \ge\ (k+1)(a_1a_2....a_{k+1})$
• Jun 6th 2010, 04:16 PM
MathematicalInduction
Just to note, the above answer does not work. I'm not sure how to exactly solve it, but if you follow the above string of logic, it doesn't work for 2 reasons.
A) You state that "if we assume the sequence decreases" there is nothing in the original problem that says the sequence decreases, only that all numbers of a are greater than 0. they could all be positive and be completely random. It does not make a difference.
b) second of all, if one assumes that a1 is greater than a2 which is greater than a3 etc, then akak+1^k cannot be greater than a1a2....akak+1 simply because akak+1^k has the exact same amount of digits as a1a2.....akak+1, but since a1 is (by transitive property) greater than or equal to ak+1, then the inequality must be false (it can be equal to, but not greater than. If it was simply equal to, it would be a formula, not an inequality, so therefore, that one step does not connect with the previous one)

Other than that, the logic is fine, but since most of the problem only works ASSUMING that the sequence is decreasing, which the problem does not state. If you want to state that the sequence is decreasing, then you would need to prove it somehow. Also, if the sequence is decreasing, then that last chain of logic does not work, as stated above.

On the other hand, I'm not sure how to actually solve it, but I think I'm quite right in noticing the flaw(s) in your logic. I would like to see the actual answer to the problem, please reply!(Happy)

Oh, by the way, the above Mathematical Induction Problem is hardly Pre-Algebra to Algebra level. I don't even recall doing anything this hard when I did pre-calculus in high school. It should probably be moved to "University Math". Its also the reason why I joined, as I couldn't help but see the flaw, and I felt a need to correct it. I would really like to see a final result though, as I'm not quite sure how to go about solving it either.
• Jun 6th 2010, 04:40 PM
Quote:

Originally Posted by MathematicalInduction
Just to note, the above answer does not work. I'm not sure how to exactly solve it, but if you follow the above string of logic, it doesn't work for 2 reasons.
A) You state that "if we assume the sequence decreases" there is nothing in the original problem that says the sequence decreases, only that all numbers of a are greater than 0. they could all be positive and be completely random. It does not make a difference.
b) second of all, if one assumes that a1 is greater than a2 which is greater than a3 etc, then akak+1^k cannot be greater than a1a2....akak+1 simply because akak+1^k has the exact same amount of digits as a1a2.....akak+1, but since a1 is (by transitive property) greater than or equal to ak+1, then the inequality must be false (it can be equal to, but not greater than. If it was simply equal to, it would be a formula, not an inequality, so therefore, that one step does not connect with the previous one)

Other than that, the logic is fine, but since most of the problem only works ASSUMING that the sequence is decreasing, which the problem does not state. If you want to state that the sequence is decreasing, then you would need to prove it somehow. Also, if the sequence is decreasing, then that last chain of logic does not work, as stated above.

false

On the other hand, I'm not sure how to actually solve it, but I think I'm quite right in noticing the flaw(s) in your logic. I would like to see the actual answer to the problem, please reply!(Happy)

Oh, by the way, the above Mathematical Induction Problem is hardly Pre-Algebra to Algebra level. I don't even recall doing anything this hard when I did pre-calculus in high school. It should probably be moved to "University Math". Its also the reason why I joined, as I couldn't help but see the flaw, and I felt a need to correct it. I would really like to see a final result though, as I'm not quite sure how to go about solving it either.

I checked this.

The proof is valid.
The numbers are placed in order.
They may not be in that order initially,
however the proof is correct for the set of numbers.

Edit.... there is an error! well spotted.
• Jun 6th 2010, 04:48 PM
MathematicalInduction
Quote:

Thanks tonio,

starting from scratch,
we can apply a few manipulations for convenience...

If the following is true

$\displaystyle \frac{A_1+A_2+......+A_n}{n}\ \ge\ \sqrt[n]{A_1A_2....A_n}$

we attempt to prove that it causes

$\displaystyle \frac{A_1+A_2+....+A_n+A_{n+1}}{n+1}\ \ge\ \sqrt[n+1]{A_1A_2....A_nA_{n+1}}$

to be true.

Rewriting $\displaystyle a_i=\sqrt[n]{A_i}$ for i=1,2,....,n

we try to prove

$\displaystyle {a_1}^n+{a_2}^n+....+{a_n}^n\ \ge\ na_1a_2....a_n$

by showing that it causes

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+...{a_k}^{k+1}+{a_{k+1}}^{ k+1}\ \ge\ (k+1)a_1a_2....a_ka_{k+1}$

Proof

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+....+{a_k}^{k+1}+{a_{k+1}} ^{k+1}=a_1{a_1}^k+a_2{a_2}^k+....+\color{red}a_k\c olor{black}{a_k}^k+\color{blue}a_{k+1}\color{black }{a_{k+1}}^k$

To develop the inequality, the following may be utilised...

$\displaystyle x_1\ \ge\ x_2,\ y_1\ \ge\ y_2\ \Rightarrow\ x_1y_1+x_2y_2\ \ge\ x_1y_2+x_2y_1$

This is because

$\displaystyle x_1y_1+x_2y_2-(x_1y_2+x_2y_1)=x_1(y_1-y_2)-x_2(y_1-y_2)=(x_1-x_2)(y_1-y_2)\ \ge\ 0$

Hence, if the terms are arranged in decreasing order...

$\displaystyle a_1\ \ge\ a_2\ \ge\ a_3\ \ge.....\ge\ a_k\ \ge\ a_{k+1}$

$\displaystyle a_1{a_1}^k+a_2{a_2}^k+....+\color{red}a_k\color{bl ack}{a_k}^k+\color{blue}a_{k+1}\color{black}{a_{k+ 1}}^k\ \ge\ a_1{a_1}^k+a_2{a_2}^k+....+\color{blue}a_{k+1}\col or{black}{a_k}^k+\color{red}a_k\color{black}{a_{k+ 1}}^k$

Therefore

$\displaystyle a_1{a_1}^k+a_2{a_2}^k+...+a_k{a_k}^k+a_{k+1}{a_{k+ 1}}^k\ \ge\ (a_{k+1}{a_1}^k+a_{k+1}{a_2}^k+....a_{k+1}{a_k}^k) +a_k{a_{k+1}}^k$

$\displaystyle \ge\ a_{k+1}({a_1}^k+{a_2}^k+...+{a_k}^k)+a_k{a_{k+1}}^ k$

Hence

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+....{a_k}^{k+1}+{a_{k+1}}^ {k+1}\ \ge\ a_{k+1}({a_1}^k+{a_2}^k+...+{a_k}^k)+a_k{a_{k+1}}^ k$<--- how did you prove that this

Since the terms are arranged in decreasing order, then $\displaystyle a_i\ \ge\ a_{k+1}$

Hence

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+....{a_k}^{k+1}+{a_{k+1}}^ {k+1}\ \ge\ a_{k+1}({a_1}^k+{a_2}^k+...+{a_k}^k)+a_1a_2...a_ka _{k+1}$ <------- is less than or equal to that? the way i solved it, it ended up be greater than or equal to. can you please explain it more in depth? i'm not quite sure I understand your logic there. everything else i get but that

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+....{a_k}^{k+1}+{a_{k+1}}^ {k+1}\ \ge\ [a_{k+1}]\left[({a_1}^k+{a_2}^k+...+{a_k}^k)+a_1a_2...a_k\right]$

If the original statement is true, $\displaystyle {a_1}^k+{a_1}^k+...+{a_k}^k\ \ge\ ka_1a_2...a_k$

then

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+....+{a_k}^{k+1}+{a_{k+1}} ^{k+1}\ \ge\ a_{k+1}[(ka_1a_2...a_k)+a_1a_2...a_k]$

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+....+{a_k}^{k+1}+{a_{k+1}} ^{k+1}\ \ge\ (k+1)(a_1a_2....a_{k+1})$

ok, so i understand what you did with the decreasing order thing.
however, please explain the above step, thanks.
• Jun 6th 2010, 05:52 PM
tonio
Quote:

Originally Posted by MathematicalInduction
Just to note, the above answer does not work. I'm not sure how to exactly solve it, but if you follow the above string of logic, it doesn't work for 2 reasons.
A) You state that "if we assume the sequence decreases" there is nothing in the original problem that says the sequence decreases, only that all numbers of a are greater than 0. they could all be positive and be completely random. It does not make a difference.

I couldn't see anywhere in his proof "assuming". He just arranged the terms of the sequence in decreasing order which can always be done in a finite set of real numbers.

In fact his proof is a rather standard one to prove the means inequality.

Tonio

b) second of all, if one assumes that a1 is greater than a2 which is greater than a3 etc, then akak+1^k cannot be greater than a1a2....akak+1 simply because akak+1^k has the exact same amount of digits as a1a2.....akak+1, but since a1 is (by transitive property) greater than or equal to ak+1, then the inequality must be false (it can be equal to, but not greater than. If it was simply equal to, it would be a formula, not an inequality, so therefore, that one step does not connect with the previous one)

Other than that, the logic is fine, but since most of the problem only works ASSUMING that the sequence is decreasing, which the problem does not state. If you want to state that the sequence is decreasing, then you would need to prove it somehow. Also, if the sequence is decreasing, then that last chain of logic does not work, as stated above.

On the other hand, I'm not sure how to actually solve it, but I think I'm quite right in noticing the flaw(s) in your logic. I would like to see the actual answer to the problem, please reply!(Happy)

Oh, by the way, the above Mathematical Induction Problem is hardly Pre-Algebra to Algebra level. I don't even recall doing anything this hard when I did pre-calculus in high school. It should probably be moved to "University Math". Its also the reason why I joined, as I couldn't help but see the flaw, and I felt a need to correct it. I would really like to see a final result though, as I'm not quite sure how to go about solving it either.

.
• Jun 6th 2010, 07:22 PM
MathematicalInduction
Quote:

Originally Posted by tonio
Originally Posted by MathematicalInduction View Post
Just to note, the above answer does not work. I'm not sure how to exactly solve it, but if you follow the above string of logic, it doesn't work for 2 reasons.
A) You state that "if we assume the sequence decreases" there is nothing in the original problem that says the sequence decreases, only that all numbers of a are greater than 0. they could all be positive and be completely random. It does not make a difference.

I couldn't see anywhere in his proof "assuming". He just arranged the terms of the sequence in decreasing order which can always be done in a finite set of real numbers.

In fact his proof is a rather standard one to prove the means inequality.

Tonio

b) second of all, if one assumes that a1 is greater than a2 which is greater than a3 etc, then akak+1^k cannot be greater than a1a2....akak+1 simply because akak+1^k has the exact same amount of digits as a1a2.....akak+1, but since a1 is (by transitive property) greater than or equal to ak+1, then the inequality must be false (it can be equal to, but not greater than. If it was simply equal to, it would be a formula, not an inequality, so therefore, that one step does not connect with the previous one)

Other than that, the logic is fine, but since most of the problem only works ASSUMING that the sequence is decreasing, which the problem does not state. If you want to state that the sequence is decreasing, then you would need to prove it somehow. Also, if the sequence is decreasing, then that last chain of logic does not work, as stated above.

On the other hand, I'm not sure how to actually solve it, but I think I'm quite right in noticing the flaw(s) in your logic. I would like to see the actual answer to the problem, please reply!

Oh, by the way, the above Mathematical Induction Problem is hardly Pre-Algebra to Algebra level. I don't even recall doing anything this hard when I did pre-calculus in high school. It should probably be moved to "University Math". Its also the reason why I joined, as I couldn't help but see the flaw, and I felt a need to correct it. I would really like to see a final result though, as I'm not quite sure how to go about solving it either..

yeah, i understood that. I after he cleared it up. i just don't understand the steps i highlighted above, as im getting the exact opposite answer that I should be getting. anybody want to explain the exact logic between those 2 steps to me? thanks.
• Jun 6th 2010, 08:06 PM
simplependulum
Quote:

Originally Posted by Rel
Using mathematical induction
proof this formula.

the formula is attached the jpg files
[Sorry I hard to using type that formula so I captured that :)

First show by induction if $\displaystyle a_1 a_2 ... a_n = 1 ~ a_i > 0$ then $\displaystyle a_1 + a_2 + ... + a_n \geq n$

When $\displaystyle n = 1$ it is true by checking actually $\displaystyle a_1 = 1 \geq 1$

Assume it is true for $\displaystyle a_1 ... a_k = 1 ~ \implies a_1 + ... + a_k \geq k$

When $\displaystyle n=k+1$

Among these $\displaystyle k+1$ numbers , let's choose $\displaystyle max\{\ a_i \}\$ and $\displaystyle min\{\ a_i \}\$ wlog let them be $\displaystyle a_k$ and $\displaystyle a_{k+1}$ respectvely and we have $\displaystyle a_k \geq 1$ and $\displaystyle a_{k+1} \leq 1$

then $\displaystyle (a_k - 1 ) (a_{k+1} - 1 ) \leq 0$

$\displaystyle \boxed{ a_k + a_{k+1} \geq 1 + a_k a_{k+1} }$

Then we have for $\displaystyle a_1 ... a_{k-1} (a_k a_{k+1} )= 1$

$\displaystyle a_1 + a_2 + ... + a_{k-1 } + (a_k a_{k+1}) \geq k$ (by asumption )

Thus

$\displaystyle a_1 + a_2 + ... + a_{k-1} + (a_k + a_{k+1}) \geq a_1 + a_2 + ... + a_{k-1} + (1 + a_k a_{k+1})$

$\displaystyle = (a_1 + a_2 + ... + a_{k-1} + a_k a_{k+1} )+ 1 \geq k +1$

Then let $\displaystyle a_i = \frac{b_i}{B}$ then we have

$\displaystyle b_1 b_2 ... b_n = B^n$ implies

$\displaystyle \frac{b_1 + b_2 + ... + b_n}{B} \geq n$

$\displaystyle \frac{b_1 + b_2 + ... + b_n}{n} \geq B = \sqrt[n]{ b_1 b_2 ... b_n }$

QED
• Jun 7th 2010, 02:49 AM
Quote:

Thanks tonio,

starting from scratch,
we can apply a few manipulations for convenience...

If the following is true

$\displaystyle \frac{A_1+A_2+......+A_n}{n}\ \ge\ \sqrt[n]{A_1A_2....A_n}$

we attempt to prove that it causes

$\displaystyle \frac{A_1+A_2+....+A_n+A_{n+1}}{n+1}\ \ge\ \sqrt[n+1]{A_1A_2....A_nA_{n+1}}$

to be true.

Rewriting $\displaystyle a_i=\sqrt[n]{A_i}$ for i=1,2,....,n

here we use $\displaystyle \color{blue}\sqrt{ab}=\sqrt{a}\sqrt{b}$

we try to prove

$\displaystyle {a_1}^k+{a_2}^k+....+{a_k}^k\ \ge\ ka_1a_2....a_k$

by showing that it causes

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+...{a_k}^{k+1}+{a_{k+1}}^{ k+1}\ \ge\ (k+1)a_1a_2....a_ka_{k+1}$

Proof

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+....+{a_k}^{k+1}+{a_{k+1}} ^{k+1}=\color{red}a_1\color{black}{a_1}^k+a_2{a_2} ^k+....+a_k{a_k}^k+\color{blue}a_{k+1}\color{black }{a_{k+1}}^k$

To develop the inequality, the following may be utilised...

$\displaystyle x_1\ \ge\ x_2,\ y_1\ \ge\ y_2\ \Rightarrow\ x_1y_1+x_2y_2\ \ge\ x_1y_2+x_2y_1$

This is because

$\displaystyle x_1y_1+x_2y_2-(x_1y_2+x_2y_1)=x_1(y_1-y_2)-x_2(y_1-y_2)=(x_1-x_2)(y_1-y_2)\ \ge\ 0$

Hence, if the terms are arranged in decreasing order...as it makes no difference to the outcome, but easier to write a proof

$\displaystyle a_1\ \ge\ a_2\ \ge\ a_3\ \ge.....\ge\ a_k\ \ge\ a_{k+1}$

$\displaystyle \color{red}a_1\color{black}{a_1}^k+a_2{a_2}^k+.... +a_k\color{black}{a_k}^k+\color{blue}a_{k+1}\color {black}{a_{k+1}}^k\ \ge\ \color{blue}a_{k+1}\color{black}{a_1}^k+a_2{a_2}^k +....+a_{k}\color{black}{a_k}^k+\color{red}a_1\col or{black}{a_{k+1}}^k$

as $\displaystyle a_1{a_1}^k\ \ge\ a_{k+1}{a_{k+1}}^k$

Now use the $\displaystyle \color{blue}a_{k+1}$ factors in the last term

Therefore

$\displaystyle a_1{a_1}^k+a_2{a_2}^k+...+a_k{a_k}^k+a_{k+1}{a_{k+ 1}}^{k}\ \ge\ a_{k+1}{a_1}^k+a_2{a_2}^k+....\color{red}a_{k+1}\c olor{black}{a_k}^k+a_1\color{red}a_k\color{black}{ a_{k+1}}^{k-1}$

terms in red interchanged, maintaining the inequality

$\displaystyle \ge\ a_{k+1}{a_1}^k+a_2{a_2}^k+...+a_{k+1}{a_{k-1}}^k+a_{k+1}{a_k}^k+a_1a_{k-1}a_k{a_{k+1}}^{k-2}$

Hence, continuing this on for all terms of the RHS

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+....{a_k}^{k+1}+{a_{k+1}}^ {k+1}\ \ge\ a_{k+1}({a_1}^k+{a_2}^k+...+{a_k}^k)+a_1a_2a_3.... a_ka_{k+1}$

Then

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+....{a_k}^{k+1}+{a_{k+1}}^ {k+1}\ \ge\ [a_{k+1}]\left[({a_1}^k+{a_2}^k+...+{a_k}^k)+a_1a_2...a_k\right]$

If the original statement is true, $\displaystyle {a_1}^k+{a_1}^k+...+{a_k}^k\ \ge\ ka_1a_2...a_k$

then

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+....+{a_k}^{k+1}+{a_{k+1}} ^{k+1}\ \ge\ a_{k+1}[(ka_1a_2...a_k)+a_1a_2...a_k]$

$\displaystyle {a_1}^{k+1}+{a_2}^{k+1}+....+{a_k}^{k+1}+{a_{k+1}} ^{k+1}\ \ge\ (k+1)(a_1a_2....a_{k+1})$

I owe you a sincere apology, as there was a typing error
and the line you questioned was mathematically incorrect,
though the logic behind the proof was correct.

Thank you for pointing it out and to Tonio and simplependulum for their input.
• Jun 8th 2010, 06:27 PM
MathematicalInduction
no problem. and thanks for solving it. it makes sense now.
• Jun 9th 2010, 11:22 AM
FancyMouse
An easier way is to prove the n=2^k case by induction, and then for an arbitrary n, pad a[i] up to a power of 2 by the AM of a[1] to a[n]