Mixing
Proof that $left(sum^n_{k=1}x_kright)left(sum^n_{k=1}y_kright)geq n^2$
$begingroup$
If $x_1,...,x_n$ are positive real numbers and if $y_k=1/x_k$, prove that $$left(sum^n_{k=1}x_kright)left(sum^n_{k=1}y_kright)geq n^2.$$
I've been learning induction, and I've come across this problem that I really can't even break down and begin to think about. I've been told it has something to do with Cauchy-Schwarz, but I cannot figure out how to apply it. I would appreciate help figuring out how to go about and formulate this proof. Thanks!
inequality summation induction a.m.-g.m.-inequality cauchy-schwarz-inequality
edited Jan 21 at 15:21
Martin R
30.5k33558
asked Sep 25 '13 at 1:13
JacksonJackson
260415
$endgroup$
|
show 4 more comments
$begingroup$
If $x_1,...,x_n$ are positive real numbers and if $y_k=1/x_k$, prove that $$left(sum^n_{k=1}x_kright)left(sum^n_{k=1}y_kright)geq n^2.$$
I've been learning induction, and I've come across this problem that I really can't even break down and begin to think about. I've been told it has something to do with Cauchy-Schwarz, but I cannot figure out how to apply it. I would appreciate help figuring out how to go about and formulate this proof. Thanks!
inequality summation induction a.m.-g.m.-inequality cauchy-schwarz-inequality
edited Jan 21 at 15:21
Martin R
30.5k33558
asked Sep 25 '13 at 1:13
JacksonJackson
260415
$endgroup$
$begingroup$
Does it help to call $x_k$ by the name of $a_k^2$?
$endgroup$
– Daniel Fischer
Sep 25 '13 at 1:15
$begingroup$
Cauchy-Schwarz inequality has sum of $a_k^2$ and sum of $b_k^2$ terms multiplied together. Can you guess that?
$endgroup$
– peterwhy
Sep 25 '13 at 1:16
$begingroup$
One way to begin on a problem like this is to take a small $n$ and see what's going on. For $n=2$ the inequality is $$(a+b)left(frac{1}{a} + frac{1}{b}right) geq 4$$. Can you show that?
$endgroup$
– Matthew Leingang
Jul 26 '16 at 17:03
1
$begingroup$
See also this answer math.stackexchange.com/a/194349/269624
$endgroup$
– Yuriy S
Jul 26 '16 at 17:06
1
$begingroup$
Just use the Cauchy-Schwarz Inequality with $x_i=sqrt{a_i}$ and $y_i=frac{1}{sqrt{a_i}}$.
$endgroup$
– Mark Viola
Jul 26 '16 at 17:18
|
show 4 more comments
$begingroup$
If $x_1,...,x_n$ are positive real numbers and if $y_k=1/x_k$, prove that $$left(sum^n_{k=1}x_kright)left(sum^n_{k=1}y_kright)geq n^2.$$
I've been learning induction, and I've come across this problem that I really can't even break down and begin to think about. I've been told it has something to do with Cauchy-Schwarz, but I cannot figure out how to apply it. I would appreciate help figuring out how to go about and formulate this proof. Thanks!
inequality summation induction a.m.-g.m.-inequality cauchy-schwarz-inequality
edited Jan 21 at 15:21
Martin R
30.5k33558
asked Sep 25 '13 at 1:13
JacksonJackson
260415
$endgroup$
If $x_1,...,x_n$ are positive real numbers and if $y_k=1/x_k$, prove that $$left(sum^n_{k=1}x_kright)left(sum^n_{k=1}y_kright)geq n^2.$$
I've been learning induction, and I've come across this problem that I really can't even break down and begin to think about. I've been told it has something to do with Cauchy-Schwarz, but I cannot figure out how to apply it. I would appreciate help figuring out how to go about and formulate this proof. Thanks!
inequality summation induction a.m.-g.m.-inequality cauchy-schwarz-inequality
inequality summation induction a.m.-g.m.-inequality cauchy-schwarz-inequality
edited Jan 21 at 15:21
Martin R
30.5k33558
asked Sep 25 '13 at 1:13
JacksonJackson
260415
edited Jan 21 at 15:21
Martin R
30.5k33558
asked Sep 25 '13 at 1:13
JacksonJackson
260415
edited Jan 21 at 15:21
Martin R
30.5k33558
edited Jan 21 at 15:21
Martin R
30.5k33558
edited Jan 21 at 15:21
Martin R
30.5k33558
30.5k33558
asked Sep 25 '13 at 1:13
JacksonJackson
260415
asked Sep 25 '13 at 1:13
JacksonJackson
260415
asked Sep 25 '13 at 1:13
JacksonJackson
260415
260415
$begingroup$
Does it help to call $x_k$ by the name of $a_k^2$?
$endgroup$
– Daniel Fischer
Sep 25 '13 at 1:15
$begingroup$
Cauchy-Schwarz inequality has sum of $a_k^2$ and sum of $b_k^2$ terms multiplied together. Can you guess that?
$endgroup$
– peterwhy
Sep 25 '13 at 1:16
$begingroup$
One way to begin on a problem like this is to take a small $n$ and see what's going on. For $n=2$ the inequality is $$(a+b)left(frac{1}{a} + frac{1}{b}right) geq 4$$. Can you show that?
$endgroup$
– Matthew Leingang
Jul 26 '16 at 17:03
1
$begingroup$
See also this answer math.stackexchange.com/a/194349/269624
$endgroup$
– Yuriy S
Jul 26 '16 at 17:06
1
$begingroup$
Just use the Cauchy-Schwarz Inequality with $x_i=sqrt{a_i}$ and $y_i=frac{1}{sqrt{a_i}}$.
$endgroup$
– Mark Viola
Jul 26 '16 at 17:18
|
show 4 more comments
$begingroup$
Does it help to call $x_k$ by the name of $a_k^2$?
$endgroup$
– Daniel Fischer
Sep 25 '13 at 1:15
$begingroup$
Cauchy-Schwarz inequality has sum of $a_k^2$ and sum of $b_k^2$ terms multiplied together. Can you guess that?
$endgroup$
– peterwhy
Sep 25 '13 at 1:16
$begingroup$
One way to begin on a problem like this is to take a small $n$ and see what's going on. For $n=2$ the inequality is $$(a+b)left(frac{1}{a} + frac{1}{b}right) geq 4$$. Can you show that?
$endgroup$
– Matthew Leingang
Jul 26 '16 at 17:03
1
$begingroup$
See also this answer math.stackexchange.com/a/194349/269624
$endgroup$
– Yuriy S
Jul 26 '16 at 17:06
1
$begingroup$
Just use the Cauchy-Schwarz Inequality with $x_i=sqrt{a_i}$ and $y_i=frac{1}{sqrt{a_i}}$.
$endgroup$
– Mark Viola
Jul 26 '16 at 17:18
$begingroup$
Does it help to call $x_k$ by the name of $a_k^2$?
$endgroup$
– Daniel Fischer
Sep 25 '13 at 1:15
$begingroup$
Does it help to call $x_k$ by the name of $a_k^2$?
$endgroup$
– Daniel Fischer
Sep 25 '13 at 1:15
$begingroup$
Cauchy-Schwarz inequality has sum of $a_k^2$ and sum of $b_k^2$ terms multiplied together. Can you guess that?
$endgroup$
– peterwhy
Sep 25 '13 at 1:16
$begingroup$
Cauchy-Schwarz inequality has sum of $a_k^2$ and sum of $b_k^2$ terms multiplied together. Can you guess that?
$endgroup$
– peterwhy
Sep 25 '13 at 1:16
$begingroup$
One way to begin on a problem like this is to take a small $n$ and see what's going on. For $n=2$ the inequality is $$(a+b)left(frac{1}{a} + frac{1}{b}right) geq 4$$. Can you show that?
$endgroup$
– Matthew Leingang
Jul 26 '16 at 17:03
$begingroup$
One way to begin on a problem like this is to take a small $n$ and see what's going on. For $n=2$ the inequality is $$(a+b)left(frac{1}{a} + frac{1}{b}right) geq 4$$. Can you show that?
$endgroup$
– Matthew Leingang
Jul 26 '16 at 17:03
1
1
$begingroup$
See also this answer math.stackexchange.com/a/194349/269624
$endgroup$
– Yuriy S
Jul 26 '16 at 17:06
$begingroup$
See also this answer math.stackexchange.com/a/194349/269624
$endgroup$
– Yuriy S
Jul 26 '16 at 17:06
1
1
$begingroup$
Just use the Cauchy-Schwarz Inequality with $x_i=sqrt{a_i}$ and $y_i=frac{1}{sqrt{a_i}}$.
$endgroup$
– Mark Viola
Jul 26 '16 at 17:18
$begingroup$
Just use the Cauchy-Schwarz Inequality with $x_i=sqrt{a_i}$ and $y_i=frac{1}{sqrt{a_i}}$.
$endgroup$
– Mark Viola
Jul 26 '16 at 17:18
|
show 4 more comments
7 Answers
7
active
oldest
votes
$begingroup$
There are couple of ways to prove this. One way is via AM-GM, i.e., we have
$$sum_{k=1}^n x_k geq n sqrt[n]{x_1 x_2 ldots x_n}$$
and
$$sum_{k=1}^n dfrac1{x_k} geq n sqrt[n]{dfrac1{x_1 x_2 ldots x_n}}$$
Multiplying the two, we get what we want.
Another way is consider the vectors
$$left(sqrt{x_1},sqrt{x_2}, ldots, sqrt{x_n} right) text{ and }left(dfrac1{sqrt{x_1}},dfrac1{sqrt{x_2}}, ldots, dfrac1{sqrt{x_n}} right)$$ and apply Cauchy-Schwarz to get what you want.
edited Jul 19 '15 at 13:19
Daniel Fischer
174k17169288
$endgroup$
2
$begingroup$
In the first proof you are actually proving the AM-HM inequality ;)
$endgroup$
– N. S.
Sep 25 '13 at 1:23
$begingroup$
Very helpful. Thank you! :)
$endgroup$
– Jackson
Sep 25 '13 at 1:29
add a comment |
$begingroup$
You can in fact prove it by induction on $n$. For the induction step observe that
$$begin{align*}
left(sum_{k=1}^{n+1}x_kright)left(sum_{k=1}^{n+1}frac1{x_k}right)&=left(sum_{k=1}^nx_k+x_{n+1}right)left(sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}right)\
&=left(sum_{k=1}^nx_kright)left(sum_{k=1}^nfrac1{x_k}right)+x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_k+1\
&ge n^2+1+x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_k;;
end{align*}$$
$(n+1)^2=n^2+2n+1$, so to finish the step, it suffices to show that
$$x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_kge 2n;.$$
For $k=1,ldots,n$ let $u_k=dfrac{x_k}{x_{n+1}}$; then
$$x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_k=sum_{k=1}^nleft(frac1{u_k}+u_kright);,$$
and it’s not hard to show that if $u>0$, then $dfrac1u+uge 2$, either by showing that $f(u)=frac1u+u$ on the positive reals has a minimum at $u=1$, or by observing that for $u>0$ we have $f(u)ge 2$ if and only if $u^2+1ge 2u$ and showing that this inequality is always true.
answered Sep 25 '13 at 1:33
Brian M. ScottBrian M. Scott
460k40516917
$endgroup$
$begingroup$
I will just mention that a similar proof can also be found here: Proof by induction for tricky double summation: $(sum_{k=1}^n x_k)cdot(sum_{k=1}^n frac{1}{x_k})ge{n^2}$.
$endgroup$
– Martin Sleziak
Jan 21 at 14:33
add a comment |
$begingroup$
The function
$$f(x)=frac{1}{x}$$
Is convex on $(0,infty)$, so for $a_1,ldots,a_n>0$ we have
$$frac{n}{a_1+cdots+a_n}leqfrac{1}{na_1}+cdots+frac{1}{na_n}.$$
Rearranging, we obtain the result.
answered Jul 26 '16 at 17:08
AweyganAweygan
14.7k21442
$endgroup$
add a comment |
$begingroup$
$$left(sum_{k=1}^n {sqrt{x_k}}^2right)left(sum_{k=1}^n {sqrt{x_k^{-1}}}^2right)
ge left(sum_{k=1}^n {sqrt{x_k}}sqrt{x_k^{-1}}right)^2 = n^2$$
answered Sep 25 '13 at 1:19
peterwhypeterwhy
12k21229
$endgroup$
add a comment |
$begingroup$
We let $x_{i+n}=x_i$ for $iin{1,2dots n}$ .What you have is $sum_limits{i=1}^n (frac{x_1}{x_{1+i}}+frac{x_2}{x_{2+i}}+dots frac{x_n}{x_{n+i}}).$
By the rearrangement inequality each of these summands is greater than $1+1+dots +1=n$
edited Jan 28 at 17:30
Martin Sleziak
44.9k10122277
answered Jul 26 '16 at 17:05
Jorge Fernández HidalgoJorge Fernández Hidalgo
77k1394195
$endgroup$
add a comment |
$begingroup$
begin{align}
sum_{k = 1}^{n}left(sqrt{x_{k},} + {mu over sqrt{x_{k},}}right)^{2} &geq 0,,
qquad
mu in {mathbb R}
\[3mm]
left(sum_{k = 1}^{n}{1 over x_{k}}right)mu^{2}
+
2nmu
+
left(sum_{k = 1}^{n}x_{k}right) &geq 0
\
left(2nright)^{2}
-
4left(sum_{k = 1}^{n}{1 over x_{k}}right)left(sum_{k = 1}^{n}x_{k}right)
&
leq 0
end{align}
$$
begin{array}{|c|}hline\
color{#ff0000}{largequad%
sum_{k = 1}^{n}x_{k}sum_{k = 1}^{n}{1 over x_{k}}
color{#000000}{ geq }
n^{2}
quad}
\ \ hline
end{array}
$$
answered Sep 25 '13 at 1:19
Felix MarinFelix Marin
68.8k7109146
$endgroup$
add a comment |
$begingroup$
You can use Cauchy-Schwarz inequality with $u_i = sqrt{x_i}$ and $v_i=frac{1}{sqrt{x_i}}$.
edited Jan 28 at 17:30
Martin Sleziak
44.9k10122277
answered Jul 26 '16 at 17:18
DarkDark
1,376417
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f504240%2fproof-that-left-sumn-k-1x-k-right-left-sumn-k-1y-k-right-geq-n2%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
7 Answers
7
active
oldest
votes
7 Answers
7
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There are couple of ways to prove this. One way is via AM-GM, i.e., we have
$$sum_{k=1}^n x_k geq n sqrt[n]{x_1 x_2 ldots x_n}$$
and
$$sum_{k=1}^n dfrac1{x_k} geq n sqrt[n]{dfrac1{x_1 x_2 ldots x_n}}$$
Multiplying the two, we get what we want.
Another way is consider the vectors
$$left(sqrt{x_1},sqrt{x_2}, ldots, sqrt{x_n} right) text{ and }left(dfrac1{sqrt{x_1}},dfrac1{sqrt{x_2}}, ldots, dfrac1{sqrt{x_n}} right)$$ and apply Cauchy-Schwarz to get what you want.
edited Jul 19 '15 at 13:19
Daniel Fischer
174k17169288
$endgroup$
2
$begingroup$
In the first proof you are actually proving the AM-HM inequality ;)
$endgroup$
– N. S.
Sep 25 '13 at 1:23
$begingroup$
Very helpful. Thank you! :)
$endgroup$
– Jackson
Sep 25 '13 at 1:29
add a comment |
$begingroup$
There are couple of ways to prove this. One way is via AM-GM, i.e., we have
$$sum_{k=1}^n x_k geq n sqrt[n]{x_1 x_2 ldots x_n}$$
and
$$sum_{k=1}^n dfrac1{x_k} geq n sqrt[n]{dfrac1{x_1 x_2 ldots x_n}}$$
Multiplying the two, we get what we want.
Another way is consider the vectors
$$left(sqrt{x_1},sqrt{x_2}, ldots, sqrt{x_n} right) text{ and }left(dfrac1{sqrt{x_1}},dfrac1{sqrt{x_2}}, ldots, dfrac1{sqrt{x_n}} right)$$ and apply Cauchy-Schwarz to get what you want.
edited Jul 19 '15 at 13:19
Daniel Fischer
174k17169288
$endgroup$
2
$begingroup$
In the first proof you are actually proving the AM-HM inequality ;)
$endgroup$
– N. S.
Sep 25 '13 at 1:23
$begingroup$
Very helpful. Thank you! :)
$endgroup$
– Jackson
Sep 25 '13 at 1:29
add a comment |
$begingroup$
There are couple of ways to prove this. One way is via AM-GM, i.e., we have
$$sum_{k=1}^n x_k geq n sqrt[n]{x_1 x_2 ldots x_n}$$
and
$$sum_{k=1}^n dfrac1{x_k} geq n sqrt[n]{dfrac1{x_1 x_2 ldots x_n}}$$
Multiplying the two, we get what we want.
Another way is consider the vectors
$$left(sqrt{x_1},sqrt{x_2}, ldots, sqrt{x_n} right) text{ and }left(dfrac1{sqrt{x_1}},dfrac1{sqrt{x_2}}, ldots, dfrac1{sqrt{x_n}} right)$$ and apply Cauchy-Schwarz to get what you want.
edited Jul 19 '15 at 13:19
Daniel Fischer
174k17169288
$endgroup$
There are couple of ways to prove this. One way is via AM-GM, i.e., we have
$$sum_{k=1}^n x_k geq n sqrt[n]{x_1 x_2 ldots x_n}$$
and
$$sum_{k=1}^n dfrac1{x_k} geq n sqrt[n]{dfrac1{x_1 x_2 ldots x_n}}$$
Multiplying the two, we get what we want.
Another way is consider the vectors
$$left(sqrt{x_1},sqrt{x_2}, ldots, sqrt{x_n} right) text{ and }left(dfrac1{sqrt{x_1}},dfrac1{sqrt{x_2}}, ldots, dfrac1{sqrt{x_n}} right)$$ and apply Cauchy-Schwarz to get what you want.
edited Jul 19 '15 at 13:19
Daniel Fischer
174k17169288
edited Jul 19 '15 at 13:19
Daniel Fischer
174k17169288
edited Jul 19 '15 at 13:19
Daniel Fischer
174k17169288
edited Jul 19 '15 at 13:19
Daniel Fischer
174k17169288
174k17169288
answered Sep 25 '13 at 1:19
user17762
2
$begingroup$
In the first proof you are actually proving the AM-HM inequality ;)
$endgroup$
– N. S.
Sep 25 '13 at 1:23
$begingroup$
Very helpful. Thank you! :)
$endgroup$
– Jackson
Sep 25 '13 at 1:29
add a comment |
2
$begingroup$
In the first proof you are actually proving the AM-HM inequality ;)
$endgroup$
– N. S.
Sep 25 '13 at 1:23
$begingroup$
Very helpful. Thank you! :)
$endgroup$
– Jackson
Sep 25 '13 at 1:29
2
2
$begingroup$
In the first proof you are actually proving the AM-HM inequality ;)
$endgroup$
– N. S.
Sep 25 '13 at 1:23
$begingroup$
In the first proof you are actually proving the AM-HM inequality ;)
$endgroup$
– N. S.
Sep 25 '13 at 1:23
$begingroup$
Very helpful. Thank you! :)
$endgroup$
– Jackson
Sep 25 '13 at 1:29
$begingroup$
Very helpful. Thank you! :)
$endgroup$
– Jackson
Sep 25 '13 at 1:29
add a comment |
$begingroup$
You can in fact prove it by induction on $n$. For the induction step observe that
$$begin{align*}
left(sum_{k=1}^{n+1}x_kright)left(sum_{k=1}^{n+1}frac1{x_k}right)&=left(sum_{k=1}^nx_k+x_{n+1}right)left(sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}right)\
&=left(sum_{k=1}^nx_kright)left(sum_{k=1}^nfrac1{x_k}right)+x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_k+1\
&ge n^2+1+x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_k;;
end{align*}$$
$(n+1)^2=n^2+2n+1$, so to finish the step, it suffices to show that
$$x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_kge 2n;.$$
For $k=1,ldots,n$ let $u_k=dfrac{x_k}{x_{n+1}}$; then
$$x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_k=sum_{k=1}^nleft(frac1{u_k}+u_kright);,$$
and it’s not hard to show that if $u>0$, then $dfrac1u+uge 2$, either by showing that $f(u)=frac1u+u$ on the positive reals has a minimum at $u=1$, or by observing that for $u>0$ we have $f(u)ge 2$ if and only if $u^2+1ge 2u$ and showing that this inequality is always true.
answered Sep 25 '13 at 1:33
Brian M. ScottBrian M. Scott
460k40516917
$endgroup$
$begingroup$
I will just mention that a similar proof can also be found here: Proof by induction for tricky double summation: $(sum_{k=1}^n x_k)cdot(sum_{k=1}^n frac{1}{x_k})ge{n^2}$.
$endgroup$
– Martin Sleziak
Jan 21 at 14:33
add a comment |
$begingroup$
You can in fact prove it by induction on $n$. For the induction step observe that
$$begin{align*}
left(sum_{k=1}^{n+1}x_kright)left(sum_{k=1}^{n+1}frac1{x_k}right)&=left(sum_{k=1}^nx_k+x_{n+1}right)left(sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}right)\
&=left(sum_{k=1}^nx_kright)left(sum_{k=1}^nfrac1{x_k}right)+x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_k+1\
&ge n^2+1+x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_k;;
end{align*}$$
$(n+1)^2=n^2+2n+1$, so to finish the step, it suffices to show that
$$x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_kge 2n;.$$
For $k=1,ldots,n$ let $u_k=dfrac{x_k}{x_{n+1}}$; then
$$x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_k=sum_{k=1}^nleft(frac1{u_k}+u_kright);,$$
and it’s not hard to show that if $u>0$, then $dfrac1u+uge 2$, either by showing that $f(u)=frac1u+u$ on the positive reals has a minimum at $u=1$, or by observing that for $u>0$ we have $f(u)ge 2$ if and only if $u^2+1ge 2u$ and showing that this inequality is always true.
answered Sep 25 '13 at 1:33
Brian M. ScottBrian M. Scott
460k40516917
$endgroup$
$begingroup$
I will just mention that a similar proof can also be found here: Proof by induction for tricky double summation: $(sum_{k=1}^n x_k)cdot(sum_{k=1}^n frac{1}{x_k})ge{n^2}$.
$endgroup$
– Martin Sleziak
Jan 21 at 14:33
add a comment |
$begingroup$
You can in fact prove it by induction on $n$. For the induction step observe that
$$begin{align*}
left(sum_{k=1}^{n+1}x_kright)left(sum_{k=1}^{n+1}frac1{x_k}right)&=left(sum_{k=1}^nx_k+x_{n+1}right)left(sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}right)\
&=left(sum_{k=1}^nx_kright)left(sum_{k=1}^nfrac1{x_k}right)+x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_k+1\
&ge n^2+1+x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_k;;
end{align*}$$
$(n+1)^2=n^2+2n+1$, so to finish the step, it suffices to show that
$$x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_kge 2n;.$$
For $k=1,ldots,n$ let $u_k=dfrac{x_k}{x_{n+1}}$; then
$$x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_k=sum_{k=1}^nleft(frac1{u_k}+u_kright);,$$
and it’s not hard to show that if $u>0$, then $dfrac1u+uge 2$, either by showing that $f(u)=frac1u+u$ on the positive reals has a minimum at $u=1$, or by observing that for $u>0$ we have $f(u)ge 2$ if and only if $u^2+1ge 2u$ and showing that this inequality is always true.
answered Sep 25 '13 at 1:33
Brian M. ScottBrian M. Scott
460k40516917
$endgroup$
You can in fact prove it by induction on $n$. For the induction step observe that
$$begin{align*}
left(sum_{k=1}^{n+1}x_kright)left(sum_{k=1}^{n+1}frac1{x_k}right)&=left(sum_{k=1}^nx_k+x_{n+1}right)left(sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}right)\
&=left(sum_{k=1}^nx_kright)left(sum_{k=1}^nfrac1{x_k}right)+x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_k+1\
&ge n^2+1+x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_k;;
end{align*}$$
$(n+1)^2=n^2+2n+1$, so to finish the step, it suffices to show that
$$x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_kge 2n;.$$
For $k=1,ldots,n$ let $u_k=dfrac{x_k}{x_{n+1}}$; then
$$x_{n+1}sum_{k=1}^nfrac1{x_k}+frac1{x_{n+1}}sum_{k=1}^nx_k=sum_{k=1}^nleft(frac1{u_k}+u_kright);,$$
and it’s not hard to show that if $u>0$, then $dfrac1u+uge 2$, either by showing that $f(u)=frac1u+u$ on the positive reals has a minimum at $u=1$, or by observing that for $u>0$ we have $f(u)ge 2$ if and only if $u^2+1ge 2u$ and showing that this inequality is always true.
answered Sep 25 '13 at 1:33
Brian M. ScottBrian M. Scott
460k40516917
answered Sep 25 '13 at 1:33
Brian M. ScottBrian M. Scott
460k40516917
answered Sep 25 '13 at 1:33
Brian M. ScottBrian M. Scott
460k40516917
answered Sep 25 '13 at 1:33
Brian M. ScottBrian M. Scott
460k40516917
460k40516917
$begingroup$
I will just mention that a similar proof can also be found here: Proof by induction for tricky double summation: $(sum_{k=1}^n x_k)cdot(sum_{k=1}^n frac{1}{x_k})ge{n^2}$.
$endgroup$
– Martin Sleziak
Jan 21 at 14:33
add a comment |
$begingroup$
I will just mention that a similar proof can also be found here: Proof by induction for tricky double summation: $(sum_{k=1}^n x_k)cdot(sum_{k=1}^n frac{1}{x_k})ge{n^2}$.
$endgroup$
– Martin Sleziak
Jan 21 at 14:33
$begingroup$
I will just mention that a similar proof can also be found here: Proof by induction for tricky double summation: $(sum_{k=1}^n x_k)cdot(sum_{k=1}^n frac{1}{x_k})ge{n^2}$.
$endgroup$
– Martin Sleziak
Jan 21 at 14:33
$begingroup$
I will just mention that a similar proof can also be found here: Proof by induction for tricky double summation: $(sum_{k=1}^n x_k)cdot(sum_{k=1}^n frac{1}{x_k})ge{n^2}$.
$endgroup$
– Martin Sleziak
Jan 21 at 14:33
add a comment |
$begingroup$
The function
$$f(x)=frac{1}{x}$$
Is convex on $(0,infty)$, so for $a_1,ldots,a_n>0$ we have
$$frac{n}{a_1+cdots+a_n}leqfrac{1}{na_1}+cdots+frac{1}{na_n}.$$
Rearranging, we obtain the result.
answered Jul 26 '16 at 17:08
AweyganAweygan
14.7k21442
$endgroup$
add a comment |
$begingroup$
The function
$$f(x)=frac{1}{x}$$
Is convex on $(0,infty)$, so for $a_1,ldots,a_n>0$ we have
$$frac{n}{a_1+cdots+a_n}leqfrac{1}{na_1}+cdots+frac{1}{na_n}.$$
Rearranging, we obtain the result.
answered Jul 26 '16 at 17:08
AweyganAweygan
14.7k21442
$endgroup$
add a comment |
$begingroup$
The function
$$f(x)=frac{1}{x}$$
Is convex on $(0,infty)$, so for $a_1,ldots,a_n>0$ we have
$$frac{n}{a_1+cdots+a_n}leqfrac{1}{na_1}+cdots+frac{1}{na_n}.$$
Rearranging, we obtain the result.
answered Jul 26 '16 at 17:08
AweyganAweygan
14.7k21442
$endgroup$
The function
$$f(x)=frac{1}{x}$$
Is convex on $(0,infty)$, so for $a_1,ldots,a_n>0$ we have
$$frac{n}{a_1+cdots+a_n}leqfrac{1}{na_1}+cdots+frac{1}{na_n}.$$
Rearranging, we obtain the result.
answered Jul 26 '16 at 17:08
AweyganAweygan
14.7k21442
edited Mar 16 at 21:37
answered Jul 26 '16 at 17:08
AweyganAweygan
14.7k21442
answered Jul 26 '16 at 17:08
AweyganAweygan
14.7k21442
answered Jul 26 '16 at 17:08
AweyganAweygan
14.7k21442
14.7k21442
add a comment |
add a comment |
$begingroup$
$$left(sum_{k=1}^n {sqrt{x_k}}^2right)left(sum_{k=1}^n {sqrt{x_k^{-1}}}^2right)
ge left(sum_{k=1}^n {sqrt{x_k}}sqrt{x_k^{-1}}right)^2 = n^2$$
answered Sep 25 '13 at 1:19
peterwhypeterwhy
12k21229
$endgroup$
add a comment |
$begingroup$
$$left(sum_{k=1}^n {sqrt{x_k}}^2right)left(sum_{k=1}^n {sqrt{x_k^{-1}}}^2right)
ge left(sum_{k=1}^n {sqrt{x_k}}sqrt{x_k^{-1}}right)^2 = n^2$$
answered Sep 25 '13 at 1:19
peterwhypeterwhy
12k21229
$endgroup$
add a comment |
$begingroup$
$$left(sum_{k=1}^n {sqrt{x_k}}^2right)left(sum_{k=1}^n {sqrt{x_k^{-1}}}^2right)
ge left(sum_{k=1}^n {sqrt{x_k}}sqrt{x_k^{-1}}right)^2 = n^2$$
answered Sep 25 '13 at 1:19
peterwhypeterwhy
12k21229
$endgroup$
$$left(sum_{k=1}^n {sqrt{x_k}}^2right)left(sum_{k=1}^n {sqrt{x_k^{-1}}}^2right)
ge left(sum_{k=1}^n {sqrt{x_k}}sqrt{x_k^{-1}}right)^2 = n^2$$
answered Sep 25 '13 at 1:19
peterwhypeterwhy
12k21229
answered Sep 25 '13 at 1:19
peterwhypeterwhy
12k21229
answered Sep 25 '13 at 1:19
peterwhypeterwhy
12k21229
answered Sep 25 '13 at 1:19
peterwhypeterwhy
12k21229
12k21229
add a comment |
add a comment |
$begingroup$
We let $x_{i+n}=x_i$ for $iin{1,2dots n}$ .What you have is $sum_limits{i=1}^n (frac{x_1}{x_{1+i}}+frac{x_2}{x_{2+i}}+dots frac{x_n}{x_{n+i}}).$
By the rearrangement inequality each of these summands is greater than $1+1+dots +1=n$
edited Jan 28 at 17:30
Martin Sleziak
44.9k10122277
answered Jul 26 '16 at 17:05
Jorge Fernández HidalgoJorge Fernández Hidalgo
77k1394195
$endgroup$
add a comment |
$begingroup$
We let $x_{i+n}=x_i$ for $iin{1,2dots n}$ .What you have is $sum_limits{i=1}^n (frac{x_1}{x_{1+i}}+frac{x_2}{x_{2+i}}+dots frac{x_n}{x_{n+i}}).$
By the rearrangement inequality each of these summands is greater than $1+1+dots +1=n$
edited Jan 28 at 17:30
Martin Sleziak
44.9k10122277
answered Jul 26 '16 at 17:05
Jorge Fernández HidalgoJorge Fernández Hidalgo
77k1394195
$endgroup$
add a comment |
$begingroup$
We let $x_{i+n}=x_i$ for $iin{1,2dots n}$ .What you have is $sum_limits{i=1}^n (frac{x_1}{x_{1+i}}+frac{x_2}{x_{2+i}}+dots frac{x_n}{x_{n+i}}).$
By the rearrangement inequality each of these summands is greater than $1+1+dots +1=n$
edited Jan 28 at 17:30
Martin Sleziak
44.9k10122277
answered Jul 26 '16 at 17:05
Jorge Fernández HidalgoJorge Fernández Hidalgo
77k1394195
$endgroup$
We let $x_{i+n}=x_i$ for $iin{1,2dots n}$ .What you have is $sum_limits{i=1}^n (frac{x_1}{x_{1+i}}+frac{x_2}{x_{2+i}}+dots frac{x_n}{x_{n+i}}).$
By the rearrangement inequality each of these summands is greater than $1+1+dots +1=n$
edited Jan 28 at 17:30
Martin Sleziak
44.9k10122277
answered Jul 26 '16 at 17:05
Jorge Fernández HidalgoJorge Fernández Hidalgo
77k1394195
edited Jan 28 at 17:30
Martin Sleziak
44.9k10122277
edited Jan 28 at 17:30
Martin Sleziak
44.9k10122277
edited Jan 28 at 17:30
Martin Sleziak
44.9k10122277
44.9k10122277
answered Jul 26 '16 at 17:05
Jorge Fernández HidalgoJorge Fernández Hidalgo
77k1394195
answered Jul 26 '16 at 17:05
Jorge Fernández HidalgoJorge Fernández Hidalgo
77k1394195
answered Jul 26 '16 at 17:05
Jorge Fernández HidalgoJorge Fernández Hidalgo
77k1394195
77k1394195
add a comment |
add a comment |
$begingroup$
begin{align}
sum_{k = 1}^{n}left(sqrt{x_{k},} + {mu over sqrt{x_{k},}}right)^{2} &geq 0,,
qquad
mu in {mathbb R}
\[3mm]
left(sum_{k = 1}^{n}{1 over x_{k}}right)mu^{2}
+
2nmu
+
left(sum_{k = 1}^{n}x_{k}right) &geq 0
\
left(2nright)^{2}
-
4left(sum_{k = 1}^{n}{1 over x_{k}}right)left(sum_{k = 1}^{n}x_{k}right)
&
leq 0
end{align}
$$
begin{array}{|c|}hline\
color{#ff0000}{largequad%
sum_{k = 1}^{n}x_{k}sum_{k = 1}^{n}{1 over x_{k}}
color{#000000}{ geq }
n^{2}
quad}
\ \ hline
end{array}
$$
answered Sep 25 '13 at 1:19
Felix MarinFelix Marin
68.8k7109146
$endgroup$
add a comment |
$begingroup$
begin{align}
sum_{k = 1}^{n}left(sqrt{x_{k},} + {mu over sqrt{x_{k},}}right)^{2} &geq 0,,
qquad
mu in {mathbb R}
\[3mm]
left(sum_{k = 1}^{n}{1 over x_{k}}right)mu^{2}
+
2nmu
+
left(sum_{k = 1}^{n}x_{k}right) &geq 0
\
left(2nright)^{2}
-
4left(sum_{k = 1}^{n}{1 over x_{k}}right)left(sum_{k = 1}^{n}x_{k}right)
&
leq 0
end{align}
$$
begin{array}{|c|}hline\
color{#ff0000}{largequad%
sum_{k = 1}^{n}x_{k}sum_{k = 1}^{n}{1 over x_{k}}
color{#000000}{ geq }
n^{2}
quad}
\ \ hline
end{array}
$$
answered Sep 25 '13 at 1:19
Felix MarinFelix Marin
68.8k7109146
$endgroup$
add a comment |
$begingroup$
begin{align}
sum_{k = 1}^{n}left(sqrt{x_{k},} + {mu over sqrt{x_{k},}}right)^{2} &geq 0,,
qquad
mu in {mathbb R}
\[3mm]
left(sum_{k = 1}^{n}{1 over x_{k}}right)mu^{2}
+
2nmu
+
left(sum_{k = 1}^{n}x_{k}right) &geq 0
\
left(2nright)^{2}
-
4left(sum_{k = 1}^{n}{1 over x_{k}}right)left(sum_{k = 1}^{n}x_{k}right)
&
leq 0
end{align}
$$
begin{array}{|c|}hline\
color{#ff0000}{largequad%
sum_{k = 1}^{n}x_{k}sum_{k = 1}^{n}{1 over x_{k}}
color{#000000}{ geq }
n^{2}
quad}
\ \ hline
end{array}
$$
answered Sep 25 '13 at 1:19
Felix MarinFelix Marin
68.8k7109146
$endgroup$
begin{align}
sum_{k = 1}^{n}left(sqrt{x_{k},} + {mu over sqrt{x_{k},}}right)^{2} &geq 0,,
qquad
mu in {mathbb R}
\[3mm]
left(sum_{k = 1}^{n}{1 over x_{k}}right)mu^{2}
+
2nmu
+
left(sum_{k = 1}^{n}x_{k}right) &geq 0
\
left(2nright)^{2}
-
4left(sum_{k = 1}^{n}{1 over x_{k}}right)left(sum_{k = 1}^{n}x_{k}right)
&
leq 0
end{align}
$$
begin{array}{|c|}hline\
color{#ff0000}{largequad%
sum_{k = 1}^{n}x_{k}sum_{k = 1}^{n}{1 over x_{k}}
color{#000000}{ geq }
n^{2}
quad}
\ \ hline
end{array}
$$
answered Sep 25 '13 at 1:19
Felix MarinFelix Marin
68.8k7109146
edited Sep 25 '13 at 1:48
answered Sep 25 '13 at 1:19
Felix MarinFelix Marin
68.8k7109146
answered Sep 25 '13 at 1:19
Felix MarinFelix Marin
68.8k7109146
answered Sep 25 '13 at 1:19
Felix MarinFelix Marin
68.8k7109146
68.8k7109146
add a comment |
add a comment |
$begingroup$
You can use Cauchy-Schwarz inequality with $u_i = sqrt{x_i}$ and $v_i=frac{1}{sqrt{x_i}}$.
edited Jan 28 at 17:30
Martin Sleziak
44.9k10122277
answered Jul 26 '16 at 17:18
DarkDark
1,376417
$endgroup$
add a comment |
$begingroup$
You can use Cauchy-Schwarz inequality with $u_i = sqrt{x_i}$ and $v_i=frac{1}{sqrt{x_i}}$.
edited Jan 28 at 17:30
Martin Sleziak
44.9k10122277
answered Jul 26 '16 at 17:18
DarkDark
1,376417
$endgroup$
add a comment |
$begingroup$
You can use Cauchy-Schwarz inequality with $u_i = sqrt{x_i}$ and $v_i=frac{1}{sqrt{x_i}}$.
edited Jan 28 at 17:30
Martin Sleziak
44.9k10122277
answered Jul 26 '16 at 17:18
DarkDark
1,376417
$endgroup$
You can use Cauchy-Schwarz inequality with $u_i = sqrt{x_i}$ and $v_i=frac{1}{sqrt{x_i}}$.
edited Jan 28 at 17:30
Martin Sleziak
44.9k10122277
answered Jul 26 '16 at 17:18
DarkDark
1,376417
edited Jan 28 at 17:30
Martin Sleziak
44.9k10122277
edited Jan 28 at 17:30
Martin Sleziak
44.9k10122277
edited Jan 28 at 17:30
Martin Sleziak
44.9k10122277
44.9k10122277
answered Jul 26 '16 at 17:18
DarkDark
1,376417
answered Jul 26 '16 at 17:18
DarkDark
1,376417
answered Jul 26 '16 at 17:18
DarkDark
1,376417
1,376417
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f504240%2fproof-that-left-sumn-k-1x-k-right-left-sumn-k-1y-k-right-geq-n2%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Does it help to call $x_k$ by the name of $a_k^2$?
$endgroup$
– Daniel Fischer
Sep 25 '13 at 1:15
$begingroup$
Cauchy-Schwarz inequality has sum of $a_k^2$ and sum of $b_k^2$ terms multiplied together. Can you guess that?
$endgroup$
– peterwhy
Sep 25 '13 at 1:16
$begingroup$
One way to begin on a problem like this is to take a small $n$ and see what's going on. For $n=2$ the inequality is $$(a+b)left(frac{1}{a} + frac{1}{b}right) geq 4$$. Can you show that?
$endgroup$
– Matthew Leingang
Jul 26 '16 at 17:03
1
$begingroup$
See also this answer math.stackexchange.com/a/194349/269624
$endgroup$
– Yuriy S
Jul 26 '16 at 17:06
1
$begingroup$
Just use the Cauchy-Schwarz Inequality with $x_i=sqrt{a_i}$ and $y_i=frac{1}{sqrt{a_i}}$.
$endgroup$
– Mark Viola
Jul 26 '16 at 17:18