Jensen's inequality proof explanation
$begingroup$
I was reading a proof of Jensen's inequality on convex functions, and I need some help understanding it. The proof is as follows:
$$f(t_1x_1+...+t_nx_n) = f((1-t_n)(frac{t_1}{1-t_n}x_1+...+frac{t_{n-1}}{1-t_n}x_{n-1})+t_nx_n)$$
$$le (1-t_n) f(frac{t_1}{1-t_n}x_1+...+frac{t_{n-1}}{1-t_n}x_{n-1})+t_nf(x_n)),(convexitivity)$$
$$le (1-t_n) { frac{t_1}{1-t_n}f(x_1)+...+frac{t_{n-1}}{1-t_n}f(x_{n-1})}+t_nf(x_n),(induction)$$
$$=t_1f(x_1)+...+t_nf(x_n)$$.
The proof is fairly simple but can someone please explain the inductive step for me.Thanks.
inequality convex-analysis contest-math proof-explanation functional-inequalities
asked Sep 24 '16 at 11:37
Basem FoudaBasem Fouda
300111
$endgroup$
add a comment |
$begingroup$
I was reading a proof of Jensen's inequality on convex functions, and I need some help understanding it. The proof is as follows:
$$f(t_1x_1+...+t_nx_n) = f((1-t_n)(frac{t_1}{1-t_n}x_1+...+frac{t_{n-1}}{1-t_n}x_{n-1})+t_nx_n)$$
$$le (1-t_n) f(frac{t_1}{1-t_n}x_1+...+frac{t_{n-1}}{1-t_n}x_{n-1})+t_nf(x_n)),(convexitivity)$$
$$le (1-t_n) { frac{t_1}{1-t_n}f(x_1)+...+frac{t_{n-1}}{1-t_n}f(x_{n-1})}+t_nf(x_n),(induction)$$
$$=t_1f(x_1)+...+t_nf(x_n)$$.
The proof is fairly simple but can someone please explain the inductive step for me.Thanks.
inequality convex-analysis contest-math proof-explanation functional-inequalities
asked Sep 24 '16 at 11:37
Basem FoudaBasem Fouda
300111
$endgroup$
add a comment |
$begingroup$
I was reading a proof of Jensen's inequality on convex functions, and I need some help understanding it. The proof is as follows:
$$f(t_1x_1+...+t_nx_n) = f((1-t_n)(frac{t_1}{1-t_n}x_1+...+frac{t_{n-1}}{1-t_n}x_{n-1})+t_nx_n)$$
$$le (1-t_n) f(frac{t_1}{1-t_n}x_1+...+frac{t_{n-1}}{1-t_n}x_{n-1})+t_nf(x_n)),(convexitivity)$$
$$le (1-t_n) { frac{t_1}{1-t_n}f(x_1)+...+frac{t_{n-1}}{1-t_n}f(x_{n-1})}+t_nf(x_n),(induction)$$
$$=t_1f(x_1)+...+t_nf(x_n)$$.
The proof is fairly simple but can someone please explain the inductive step for me.Thanks.
inequality convex-analysis contest-math proof-explanation functional-inequalities
asked Sep 24 '16 at 11:37
Basem FoudaBasem Fouda
300111
$endgroup$
I was reading a proof of Jensen's inequality on convex functions, and I need some help understanding it. The proof is as follows:
$$f(t_1x_1+...+t_nx_n) = f((1-t_n)(frac{t_1}{1-t_n}x_1+...+frac{t_{n-1}}{1-t_n}x_{n-1})+t_nx_n)$$
$$le (1-t_n) f(frac{t_1}{1-t_n}x_1+...+frac{t_{n-1}}{1-t_n}x_{n-1})+t_nf(x_n)),(convexitivity)$$
$$le (1-t_n) { frac{t_1}{1-t_n}f(x_1)+...+frac{t_{n-1}}{1-t_n}f(x_{n-1})}+t_nf(x_n),(induction)$$
$$=t_1f(x_1)+...+t_nf(x_n)$$.
The proof is fairly simple but can someone please explain the inductive step for me.Thanks.
inequality convex-analysis contest-math proof-explanation functional-inequalities
inequality convex-analysis contest-math proof-explanation functional-inequalities
asked Sep 24 '16 at 11:37
Basem FoudaBasem Fouda
300111
asked Sep 24 '16 at 11:37
Basem FoudaBasem Fouda
300111
asked Sep 24 '16 at 11:37
Basem FoudaBasem Fouda
300111
asked Sep 24 '16 at 11:37
Basem FoudaBasem Fouda
300111
asked Sep 24 '16 at 11:37
Basem FoudaBasem Fouda
300111
300111
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The inductive assumption is that $f(lambda_1 x_1+....+lambda_{n-1}x_{n-1})leq lambda_1 f(x_1)+...+lambda_{n-1}f(x_{n-1})$ already holds if $sum_{j=1}^{n-1}lambda_j=1$ and since $sum_{j=1}^{n}t_j=1$ one has
$sum_{j=1}^{n-1}frac{t_j}{1-t_n}=frac{1-t_n}{1-t_n}=1$.
answered Sep 24 '16 at 11:55
Peter MelechPeter Melech
2,657813
$endgroup$
$begingroup$
But the assumption $f(lambda_1 x_1+....+lambda_{n-1}x_{n-1})leq lambda_1 f(x_1)+...+lambda_{n-1}f(x_{n-1})$ is jensen's inequality which is what we want to prove.
$endgroup$
– Basem Fouda
Sep 24 '16 at 12:12
$begingroup$
Not sure if I understand Your question, its the inductive hypothesis for $n-1$, for $n=1$ You have $t_1=1$ and $f(x_1)leq f(x_1)$ is trivial (equality holds), then the inductive step...
$endgroup$
– Peter Melech
Sep 24 '16 at 12:16
1
$begingroup$
Thats the way induction works, You assume what You want to prove to hold for e.g. $n-1$ and then proof that it holds for $n$. Of course You need an anchor $n=1$
$endgroup$
– Peter Melech
Sep 24 '16 at 12:21
$begingroup$
The reason it is had to discuss this problem is because $n$ is usually used in induction, however it happens to be the same variable used to describe the sequence $x_1,x_2,...,x_n$, so I would like to use the variable $m$ when talking about induction.
$endgroup$
– Basem Fouda
Sep 25 '16 at 14:58
$begingroup$
I think that induction in this case has to be done for $m+1$ rather than $m-1$. As the sequence goes $1,2,3,...,n$ and as our base case is $m=1$, $m+1$ is what works. However $m-1$, would work for a sequence of $1,0,-1, infinity$. Please correct me if I am wrong.
$endgroup$
– Basem Fouda
Sep 25 '16 at 15:00
|
show 2 more comments
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%2f1939399%2fjensens-inequality-proof-explanation%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The inductive assumption is that $f(lambda_1 x_1+....+lambda_{n-1}x_{n-1})leq lambda_1 f(x_1)+...+lambda_{n-1}f(x_{n-1})$ already holds if $sum_{j=1}^{n-1}lambda_j=1$ and since $sum_{j=1}^{n}t_j=1$ one has
$sum_{j=1}^{n-1}frac{t_j}{1-t_n}=frac{1-t_n}{1-t_n}=1$.
answered Sep 24 '16 at 11:55
Peter MelechPeter Melech
2,657813
$endgroup$
$begingroup$
But the assumption $f(lambda_1 x_1+....+lambda_{n-1}x_{n-1})leq lambda_1 f(x_1)+...+lambda_{n-1}f(x_{n-1})$ is jensen's inequality which is what we want to prove.
$endgroup$
– Basem Fouda
Sep 24 '16 at 12:12
$begingroup$
Not sure if I understand Your question, its the inductive hypothesis for $n-1$, for $n=1$ You have $t_1=1$ and $f(x_1)leq f(x_1)$ is trivial (equality holds), then the inductive step...
$endgroup$
– Peter Melech
Sep 24 '16 at 12:16
1
$begingroup$
Thats the way induction works, You assume what You want to prove to hold for e.g. $n-1$ and then proof that it holds for $n$. Of course You need an anchor $n=1$
$endgroup$
– Peter Melech
Sep 24 '16 at 12:21
$begingroup$
The reason it is had to discuss this problem is because $n$ is usually used in induction, however it happens to be the same variable used to describe the sequence $x_1,x_2,...,x_n$, so I would like to use the variable $m$ when talking about induction.
$endgroup$
– Basem Fouda
Sep 25 '16 at 14:58
$begingroup$
I think that induction in this case has to be done for $m+1$ rather than $m-1$. As the sequence goes $1,2,3,...,n$ and as our base case is $m=1$, $m+1$ is what works. However $m-1$, would work for a sequence of $1,0,-1, infinity$. Please correct me if I am wrong.
$endgroup$
– Basem Fouda
Sep 25 '16 at 15:00
|
show 2 more comments
$begingroup$
The inductive assumption is that $f(lambda_1 x_1+....+lambda_{n-1}x_{n-1})leq lambda_1 f(x_1)+...+lambda_{n-1}f(x_{n-1})$ already holds if $sum_{j=1}^{n-1}lambda_j=1$ and since $sum_{j=1}^{n}t_j=1$ one has
$sum_{j=1}^{n-1}frac{t_j}{1-t_n}=frac{1-t_n}{1-t_n}=1$.
answered Sep 24 '16 at 11:55
Peter MelechPeter Melech
2,657813
$endgroup$
$begingroup$
But the assumption $f(lambda_1 x_1+....+lambda_{n-1}x_{n-1})leq lambda_1 f(x_1)+...+lambda_{n-1}f(x_{n-1})$ is jensen's inequality which is what we want to prove.
$endgroup$
– Basem Fouda
Sep 24 '16 at 12:12
$begingroup$
Not sure if I understand Your question, its the inductive hypothesis for $n-1$, for $n=1$ You have $t_1=1$ and $f(x_1)leq f(x_1)$ is trivial (equality holds), then the inductive step...
$endgroup$
– Peter Melech
Sep 24 '16 at 12:16
1
$begingroup$
Thats the way induction works, You assume what You want to prove to hold for e.g. $n-1$ and then proof that it holds for $n$. Of course You need an anchor $n=1$
$endgroup$
– Peter Melech
Sep 24 '16 at 12:21
$begingroup$
The reason it is had to discuss this problem is because $n$ is usually used in induction, however it happens to be the same variable used to describe the sequence $x_1,x_2,...,x_n$, so I would like to use the variable $m$ when talking about induction.
$endgroup$
– Basem Fouda
Sep 25 '16 at 14:58
$begingroup$
I think that induction in this case has to be done for $m+1$ rather than $m-1$. As the sequence goes $1,2,3,...,n$ and as our base case is $m=1$, $m+1$ is what works. However $m-1$, would work for a sequence of $1,0,-1, infinity$. Please correct me if I am wrong.
$endgroup$
– Basem Fouda
Sep 25 '16 at 15:00
|
show 2 more comments
$begingroup$
The inductive assumption is that $f(lambda_1 x_1+....+lambda_{n-1}x_{n-1})leq lambda_1 f(x_1)+...+lambda_{n-1}f(x_{n-1})$ already holds if $sum_{j=1}^{n-1}lambda_j=1$ and since $sum_{j=1}^{n}t_j=1$ one has
$sum_{j=1}^{n-1}frac{t_j}{1-t_n}=frac{1-t_n}{1-t_n}=1$.
answered Sep 24 '16 at 11:55
Peter MelechPeter Melech
2,657813
$endgroup$
The inductive assumption is that $f(lambda_1 x_1+....+lambda_{n-1}x_{n-1})leq lambda_1 f(x_1)+...+lambda_{n-1}f(x_{n-1})$ already holds if $sum_{j=1}^{n-1}lambda_j=1$ and since $sum_{j=1}^{n}t_j=1$ one has
$sum_{j=1}^{n-1}frac{t_j}{1-t_n}=frac{1-t_n}{1-t_n}=1$.
answered Sep 24 '16 at 11:55
Peter MelechPeter Melech
2,657813
answered Sep 24 '16 at 11:55
Peter MelechPeter Melech
2,657813
answered Sep 24 '16 at 11:55
Peter MelechPeter Melech
2,657813
answered Sep 24 '16 at 11:55
Peter MelechPeter Melech
2,657813
2,657813
$begingroup$
But the assumption $f(lambda_1 x_1+....+lambda_{n-1}x_{n-1})leq lambda_1 f(x_1)+...+lambda_{n-1}f(x_{n-1})$ is jensen's inequality which is what we want to prove.
$endgroup$
– Basem Fouda
Sep 24 '16 at 12:12
$begingroup$
Not sure if I understand Your question, its the inductive hypothesis for $n-1$, for $n=1$ You have $t_1=1$ and $f(x_1)leq f(x_1)$ is trivial (equality holds), then the inductive step...
$endgroup$
– Peter Melech
Sep 24 '16 at 12:16
1
$begingroup$
Thats the way induction works, You assume what You want to prove to hold for e.g. $n-1$ and then proof that it holds for $n$. Of course You need an anchor $n=1$
$endgroup$
– Peter Melech
Sep 24 '16 at 12:21
$begingroup$
The reason it is had to discuss this problem is because $n$ is usually used in induction, however it happens to be the same variable used to describe the sequence $x_1,x_2,...,x_n$, so I would like to use the variable $m$ when talking about induction.
$endgroup$
– Basem Fouda
Sep 25 '16 at 14:58
$begingroup$
I think that induction in this case has to be done for $m+1$ rather than $m-1$. As the sequence goes $1,2,3,...,n$ and as our base case is $m=1$, $m+1$ is what works. However $m-1$, would work for a sequence of $1,0,-1, infinity$. Please correct me if I am wrong.
$endgroup$
– Basem Fouda
Sep 25 '16 at 15:00
|
show 2 more comments
$begingroup$
But the assumption $f(lambda_1 x_1+....+lambda_{n-1}x_{n-1})leq lambda_1 f(x_1)+...+lambda_{n-1}f(x_{n-1})$ is jensen's inequality which is what we want to prove.
$endgroup$
– Basem Fouda
Sep 24 '16 at 12:12
$begingroup$
Not sure if I understand Your question, its the inductive hypothesis for $n-1$, for $n=1$ You have $t_1=1$ and $f(x_1)leq f(x_1)$ is trivial (equality holds), then the inductive step...
$endgroup$
– Peter Melech
Sep 24 '16 at 12:16
1
$begingroup$
Thats the way induction works, You assume what You want to prove to hold for e.g. $n-1$ and then proof that it holds for $n$. Of course You need an anchor $n=1$
$endgroup$
– Peter Melech
Sep 24 '16 at 12:21
$begingroup$
The reason it is had to discuss this problem is because $n$ is usually used in induction, however it happens to be the same variable used to describe the sequence $x_1,x_2,...,x_n$, so I would like to use the variable $m$ when talking about induction.
$endgroup$
– Basem Fouda
Sep 25 '16 at 14:58
$begingroup$
I think that induction in this case has to be done for $m+1$ rather than $m-1$. As the sequence goes $1,2,3,...,n$ and as our base case is $m=1$, $m+1$ is what works. However $m-1$, would work for a sequence of $1,0,-1, infinity$. Please correct me if I am wrong.
$endgroup$
– Basem Fouda
Sep 25 '16 at 15:00
$begingroup$
But the assumption $f(lambda_1 x_1+....+lambda_{n-1}x_{n-1})leq lambda_1 f(x_1)+...+lambda_{n-1}f(x_{n-1})$ is jensen's inequality which is what we want to prove.
$endgroup$
– Basem Fouda
Sep 24 '16 at 12:12
$begingroup$
But the assumption $f(lambda_1 x_1+....+lambda_{n-1}x_{n-1})leq lambda_1 f(x_1)+...+lambda_{n-1}f(x_{n-1})$ is jensen's inequality which is what we want to prove.
$endgroup$
– Basem Fouda
Sep 24 '16 at 12:12
$begingroup$
Not sure if I understand Your question, its the inductive hypothesis for $n-1$, for $n=1$ You have $t_1=1$ and $f(x_1)leq f(x_1)$ is trivial (equality holds), then the inductive step...
$endgroup$
– Peter Melech
Sep 24 '16 at 12:16
$begingroup$
Not sure if I understand Your question, its the inductive hypothesis for $n-1$, for $n=1$ You have $t_1=1$ and $f(x_1)leq f(x_1)$ is trivial (equality holds), then the inductive step...
$endgroup$
– Peter Melech
Sep 24 '16 at 12:16
1
1
$begingroup$
Thats the way induction works, You assume what You want to prove to hold for e.g. $n-1$ and then proof that it holds for $n$. Of course You need an anchor $n=1$
$endgroup$
– Peter Melech
Sep 24 '16 at 12:21
$begingroup$
Thats the way induction works, You assume what You want to prove to hold for e.g. $n-1$ and then proof that it holds for $n$. Of course You need an anchor $n=1$
$endgroup$
– Peter Melech
Sep 24 '16 at 12:21
$begingroup$
The reason it is had to discuss this problem is because $n$ is usually used in induction, however it happens to be the same variable used to describe the sequence $x_1,x_2,...,x_n$, so I would like to use the variable $m$ when talking about induction.
$endgroup$
– Basem Fouda
Sep 25 '16 at 14:58
$begingroup$
The reason it is had to discuss this problem is because $n$ is usually used in induction, however it happens to be the same variable used to describe the sequence $x_1,x_2,...,x_n$, so I would like to use the variable $m$ when talking about induction.
$endgroup$
– Basem Fouda
Sep 25 '16 at 14:58
$begingroup$
I think that induction in this case has to be done for $m+1$ rather than $m-1$. As the sequence goes $1,2,3,...,n$ and as our base case is $m=1$, $m+1$ is what works. However $m-1$, would work for a sequence of $1,0,-1, infinity$. Please correct me if I am wrong.
$endgroup$
– Basem Fouda
Sep 25 '16 at 15:00
$begingroup$
I think that induction in this case has to be done for $m+1$ rather than $m-1$. As the sequence goes $1,2,3,...,n$ and as our base case is $m=1$, $m+1$ is what works. However $m-1$, would work for a sequence of $1,0,-1, infinity$. Please correct me if I am wrong.
$endgroup$
– Basem Fouda
Sep 25 '16 at 15:00
|
show 2 more comments
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%2f1939399%2fjensens-inequality-proof-explanation%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
