Mixing
Check proof that, if $a_1a_2… a_n=1$ with $a_igt0$ then $(1+a_1)(1+a_2)…(1+a_n)geq2^n$
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Theorem: Suppose there is a sequence of positive real numbers such that $a_1a_2... a_n=1$ then
$$(1+a_1)(1+a_2)...(1+a_n)geq2^n$$
(Prove by induction, do not use geometric mean)
I believe I have a proof, but I am unsure it is correct. Could you help me identify any mistakes or find a more direct approach?
Proof: Let $n=1$ then clearly $a_1=1$ and $(1+1)geq2$
Assume the claim is true for all sequences of length $k<n$. Then from a sequence $a_1a_2..a_n$, let $c=a_ia_j$ where $a_igeq1$ and $a_jleq1$. We know we can pick these because otherwise the product must be less or than greater one.
Then $c(a_1a_2...a_n)= 1$ where $ineq j$ and $ineq k$ and by the induction hypothesis:
$$(c+1)(a_1+1)(a_2+1)...(a_n+1)geq 2^n-1$$
And
$$(1+a_i)(1+a_j)=a_ia_j+a_i+a_j+1$$
We want to show this product is greater than $2(c+1)$.
$$(1-a_j)geq (1-a_j)$$
$$a_i(1-a_j)geq (1-a_j)$$ since $a_igeq 1$.
$$a_i-a_ia_jgeq (1-a_j)$$
$$a_i + a_j geq a_ia_j + 1$$
$$a_i + a_j + (a_ia_j + 1) geq a_ia_j + 1 + (a_ia_j + 1)$$
$$(1+a_i)(1+a_j) geq 2(a_ia_j + 1) = 2(c+1)$$
Finally:
$$(1+a_i)(1+a_j)(a_1+1)...(a_n+1)geq 2(c+1)frac2^n-1c+1=2^n$$
Note: This exercise comes from Udi Manber's Intro to Algorithms.
discrete-mathematics proof-verification algorithms induction
edited Jul 22 at 16:46
Ryan Pendleton
1032
asked Jul 22 at 5:56
Justin Meiners
1064
 |Â
show 3 more comments
up vote
1
down vote
favorite
Theorem: Suppose there is a sequence of positive real numbers such that $a_1a_2... a_n=1$ then
$$(1+a_1)(1+a_2)...(1+a_n)geq2^n$$
(Prove by induction, do not use geometric mean)
I believe I have a proof, but I am unsure it is correct. Could you help me identify any mistakes or find a more direct approach?
Proof: Let $n=1$ then clearly $a_1=1$ and $(1+1)geq2$
Assume the claim is true for all sequences of length $k<n$. Then from a sequence $a_1a_2..a_n$, let $c=a_ia_j$ where $a_igeq1$ and $a_jleq1$. We know we can pick these because otherwise the product must be less or than greater one.
Then $c(a_1a_2...a_n)= 1$ where $ineq j$ and $ineq k$ and by the induction hypothesis:
$$(c+1)(a_1+1)(a_2+1)...(a_n+1)geq 2^n-1$$
And
$$(1+a_i)(1+a_j)=a_ia_j+a_i+a_j+1$$
We want to show this product is greater than $2(c+1)$.
$$(1-a_j)geq (1-a_j)$$
$$a_i(1-a_j)geq (1-a_j)$$ since $a_igeq 1$.
$$a_i-a_ia_jgeq (1-a_j)$$
$$a_i + a_j geq a_ia_j + 1$$
$$a_i + a_j + (a_ia_j + 1) geq a_ia_j + 1 + (a_ia_j + 1)$$
$$(1+a_i)(1+a_j) geq 2(a_ia_j + 1) = 2(c+1)$$
Finally:
$$(1+a_i)(1+a_j)(a_1+1)...(a_n+1)geq 2(c+1)frac2^n-1c+1=2^n$$
Note: This exercise comes from Udi Manber's Intro to Algorithms.
discrete-mathematics proof-verification algorithms induction
edited Jul 22 at 16:46
Ryan Pendleton
1032
asked Jul 22 at 5:56
Justin Meiners
1064
It looks correct to me.
– Parcly Taxel
Jul 22 at 5:59
Please try to concoct informative titles, see the edited title for an example.
– Did
Jul 22 at 8:29
Possible duplicate of Prove that $(1+a_1) cdot (1+a_2) cdot dots cdot (1+a_n) geq 2^n$
– rtybase
Jul 22 at 8:50
@rtybase Thank you. that is the same setup, but the book specifically asks for an induction method. The answer is using geometric mean, which the book said not to use.
– Justin Meiners
Jul 22 at 15:37
1
Math is really hard to search, I definitely attempted to find the answer first. I still think this is a unique solution, but I don't want to pollute any sites and I don't think I have any more desire to contribute here. Please delete my question.
– Justin Meiners
Jul 22 at 16:16
 |Â
show 3 more comments
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Theorem: Suppose there is a sequence of positive real numbers such that $a_1a_2... a_n=1$ then
$$(1+a_1)(1+a_2)...(1+a_n)geq2^n$$
(Prove by induction, do not use geometric mean)
I believe I have a proof, but I am unsure it is correct. Could you help me identify any mistakes or find a more direct approach?
Proof: Let $n=1$ then clearly $a_1=1$ and $(1+1)geq2$
Assume the claim is true for all sequences of length $k<n$. Then from a sequence $a_1a_2..a_n$, let $c=a_ia_j$ where $a_igeq1$ and $a_jleq1$. We know we can pick these because otherwise the product must be less or than greater one.
Then $c(a_1a_2...a_n)= 1$ where $ineq j$ and $ineq k$ and by the induction hypothesis:
$$(c+1)(a_1+1)(a_2+1)...(a_n+1)geq 2^n-1$$
And
$$(1+a_i)(1+a_j)=a_ia_j+a_i+a_j+1$$
We want to show this product is greater than $2(c+1)$.
$$(1-a_j)geq (1-a_j)$$
$$a_i(1-a_j)geq (1-a_j)$$ since $a_igeq 1$.
$$a_i-a_ia_jgeq (1-a_j)$$
$$a_i + a_j geq a_ia_j + 1$$
$$a_i + a_j + (a_ia_j + 1) geq a_ia_j + 1 + (a_ia_j + 1)$$
$$(1+a_i)(1+a_j) geq 2(a_ia_j + 1) = 2(c+1)$$
Finally:
$$(1+a_i)(1+a_j)(a_1+1)...(a_n+1)geq 2(c+1)frac2^n-1c+1=2^n$$
Note: This exercise comes from Udi Manber's Intro to Algorithms.
discrete-mathematics proof-verification algorithms induction
edited Jul 22 at 16:46
Ryan Pendleton
1032
asked Jul 22 at 5:56
Justin Meiners
1064
Theorem: Suppose there is a sequence of positive real numbers such that $a_1a_2... a_n=1$ then
$$(1+a_1)(1+a_2)...(1+a_n)geq2^n$$
(Prove by induction, do not use geometric mean)
I believe I have a proof, but I am unsure it is correct. Could you help me identify any mistakes or find a more direct approach?
Proof: Let $n=1$ then clearly $a_1=1$ and $(1+1)geq2$
Assume the claim is true for all sequences of length $k<n$. Then from a sequence $a_1a_2..a_n$, let $c=a_ia_j$ where $a_igeq1$ and $a_jleq1$. We know we can pick these because otherwise the product must be less or than greater one.
Then $c(a_1a_2...a_n)= 1$ where $ineq j$ and $ineq k$ and by the induction hypothesis:
$$(c+1)(a_1+1)(a_2+1)...(a_n+1)geq 2^n-1$$
And
$$(1+a_i)(1+a_j)=a_ia_j+a_i+a_j+1$$
We want to show this product is greater than $2(c+1)$.
$$(1-a_j)geq (1-a_j)$$
$$a_i(1-a_j)geq (1-a_j)$$ since $a_igeq 1$.
$$a_i-a_ia_jgeq (1-a_j)$$
$$a_i + a_j geq a_ia_j + 1$$
$$a_i + a_j + (a_ia_j + 1) geq a_ia_j + 1 + (a_ia_j + 1)$$
$$(1+a_i)(1+a_j) geq 2(a_ia_j + 1) = 2(c+1)$$
Finally:
$$(1+a_i)(1+a_j)(a_1+1)...(a_n+1)geq 2(c+1)frac2^n-1c+1=2^n$$
Note: This exercise comes from Udi Manber's Intro to Algorithms.
discrete-mathematics proof-verification algorithms induction
edited Jul 22 at 16:46
Ryan Pendleton
1032
asked Jul 22 at 5:56
Justin Meiners
1064
edited Jul 22 at 16:46
Ryan Pendleton
1032
edited Jul 22 at 16:46
Ryan Pendleton
1032
edited Jul 22 at 16:46
Ryan Pendleton
1032
1032
asked Jul 22 at 5:56
Justin Meiners
1064
asked Jul 22 at 5:56
Justin Meiners
1064
asked Jul 22 at 5:56
Justin Meiners
1064
1064
It looks correct to me.
– Parcly Taxel
Jul 22 at 5:59
Please try to concoct informative titles, see the edited title for an example.
– Did
Jul 22 at 8:29
Possible duplicate of Prove that $(1+a_1) cdot (1+a_2) cdot dots cdot (1+a_n) geq 2^n$
– rtybase
Jul 22 at 8:50
@rtybase Thank you. that is the same setup, but the book specifically asks for an induction method. The answer is using geometric mean, which the book said not to use.
– Justin Meiners
Jul 22 at 15:37
1
Math is really hard to search, I definitely attempted to find the answer first. I still think this is a unique solution, but I don't want to pollute any sites and I don't think I have any more desire to contribute here. Please delete my question.
– Justin Meiners
Jul 22 at 16:16
 |Â
show 3 more comments
It looks correct to me.
– Parcly Taxel
Jul 22 at 5:59
Please try to concoct informative titles, see the edited title for an example.
– Did
Jul 22 at 8:29
Possible duplicate of Prove that $(1+a_1) cdot (1+a_2) cdot dots cdot (1+a_n) geq 2^n$
– rtybase
Jul 22 at 8:50
@rtybase Thank you. that is the same setup, but the book specifically asks for an induction method. The answer is using geometric mean, which the book said not to use.
– Justin Meiners
Jul 22 at 15:37
1
Math is really hard to search, I definitely attempted to find the answer first. I still think this is a unique solution, but I don't want to pollute any sites and I don't think I have any more desire to contribute here. Please delete my question.
– Justin Meiners
Jul 22 at 16:16
It looks correct to me.
– Parcly Taxel
Jul 22 at 5:59
It looks correct to me.
– Parcly Taxel
Jul 22 at 5:59
Please try to concoct informative titles, see the edited title for an example.
– Did
Jul 22 at 8:29
Please try to concoct informative titles, see the edited title for an example.
– Did
Jul 22 at 8:29
Possible duplicate of Prove that $(1+a_1) cdot (1+a_2) cdot dots cdot (1+a_n) geq 2^n$
– rtybase
Jul 22 at 8:50
Possible duplicate of Prove that $(1+a_1) cdot (1+a_2) cdot dots cdot (1+a_n) geq 2^n$
– rtybase
Jul 22 at 8:50
@rtybase Thank you. that is the same setup, but the book specifically asks for an induction method. The answer is using geometric mean, which the book said not to use.
– Justin Meiners
Jul 22 at 15:37
@rtybase Thank you. that is the same setup, but the book specifically asks for an induction method. The answer is using geometric mean, which the book said not to use.
– Justin Meiners
Jul 22 at 15:37
1
1
Math is really hard to search, I definitely attempted to find the answer first. I still think this is a unique solution, but I don't want to pollute any sites and I don't think I have any more desire to contribute here. Please delete my question.
– Justin Meiners
Jul 22 at 16:16
Math is really hard to search, I definitely attempted to find the answer first. I still think this is a unique solution, but I don't want to pollute any sites and I don't think I have any more desire to contribute here. Please delete my question.
– Justin Meiners
Jul 22 at 16:16
 |Â
show 3 more comments
1 Answer
1
active
oldest
votes
up vote
5
down vote
$$ a+b geq 2sqrtab $$
$$ (1+a_1)(1+a_2)ldots(1+a_n) geq 2sqrta_1 cdot 2sqrta_2 ldots 2sqrta_n = 2^nsqrta_1a_2a_3 ldots a_n = 2^n $$
answered Jul 22 at 6:15
Vladislav Kharlamov
572216
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
$$ a+b geq 2sqrtab $$
$$ (1+a_1)(1+a_2)ldots(1+a_n) geq 2sqrta_1 cdot 2sqrta_2 ldots 2sqrta_n = 2^nsqrta_1a_2a_3 ldots a_n = 2^n $$
answered Jul 22 at 6:15
Vladislav Kharlamov
572216
add a comment |Â
up vote
5
down vote
$$ a+b geq 2sqrtab $$
$$ (1+a_1)(1+a_2)ldots(1+a_n) geq 2sqrta_1 cdot 2sqrta_2 ldots 2sqrta_n = 2^nsqrta_1a_2a_3 ldots a_n = 2^n $$
answered Jul 22 at 6:15
Vladislav Kharlamov
572216
add a comment |Â
up vote
5
down vote
up vote
5
down vote
$$ a+b geq 2sqrtab $$
$$ (1+a_1)(1+a_2)ldots(1+a_n) geq 2sqrta_1 cdot 2sqrta_2 ldots 2sqrta_n = 2^nsqrta_1a_2a_3 ldots a_n = 2^n $$
answered Jul 22 at 6:15
Vladislav Kharlamov
572216
$$ a+b geq 2sqrtab $$
$$ (1+a_1)(1+a_2)ldots(1+a_n) geq 2sqrta_1 cdot 2sqrta_2 ldots 2sqrta_n = 2^nsqrta_1a_2a_3 ldots a_n = 2^n $$
answered Jul 22 at 6:15
Vladislav Kharlamov
572216
answered Jul 22 at 6:15
Vladislav Kharlamov
572216
answered Jul 22 at 6:15
Vladislav Kharlamov
572216
answered Jul 22 at 6:15
Vladislav Kharlamov
572216
572216
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2859135%2fcheck-proof-that-if-a-1a-2-a-n-1-with-a-i-gt0-then-1a-11a%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
It looks correct to me.
– Parcly Taxel
Jul 22 at 5:59
Please try to concoct informative titles, see the edited title for an example.
– Did
Jul 22 at 8:29
Possible duplicate of Prove that $(1+a_1) cdot (1+a_2) cdot dots cdot (1+a_n) geq 2^n$
– rtybase
Jul 22 at 8:50
@rtybase Thank you. that is the same setup, but the book specifically asks for an induction method. The answer is using geometric mean, which the book said not to use.
– Justin Meiners
Jul 22 at 15:37
1
Math is really hard to search, I definitely attempted to find the answer first. I still think this is a unique solution, but I don't want to pollute any sites and I don't think I have any more desire to contribute here. Please delete my question.
– Justin Meiners
Jul 22 at 16:16