2
$\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.

$\endgroup$
3
$\begingroup$

The proof write-up you read isn't friendly to those new to induction, partly because it's easy to mistake the induction for circularity, partly because the base step is a little non-standard (we have to check two values of $n$, not just one). So let me spell out the argument a little more.

Theorem: for any $n\in\Bbb N$, a convex $f$ satisfies$$\sum_{i=1}^nt_i=1,\,t_i\ge0\implies f(\sum_{i=1}^n t_i x_i)\le\sum_{i=1}^nt_i f(x_i).$$

Base step of inductive proof: if $n=1$ then $t_1=1$, so the required result is $f(x_1)\le f(x_1)$, which is true; if $n=2$ the required result is$$t_1+t_2=1,\,t_i\ge0\implies f(t_1x_1+t_2x_2)\le t_1f(x_1)+t_2f(x_2),$$which is true by the convexity of $f$.

Inductive step of inductive proof: we prove if the result holds for $n=k\ge 2$ then it also holds for $n=k+1$. If $t_{n+1}=1$ other $t_i$ are $0$, so the required inequality is $f(x_{n+1})\le f(x_{n+1})$, which is true. If $t_{n+1}\ne1$,$$f\left(\sum_{i=1}^{k+1}t_ix_i\right)=f\left((1-t_{k+1})\sum_{i=1}^k\frac{t_i}{1-t_{k+1}}x_i+t_{k+1}x_{k+1}\right).$$By convexity, we have the upper bound $$(1-t_{k+1})f\left(\sum_{i=1}^k\frac{t_i}{1-t_{k+1}}x_i\right)+t_{k+1}f(x_{k+1}).$$By the inductive hypothesis (i.e. the $n=k$ case of the result), we get an upper bound on the first term, so$$f\left(\sum_{i=1}^{k+1}t_ix_i\right)\le(1-t_{k+1})\sum_{i=1}^k\frac{t_i}{1-t_{k+1}}f(x_i)+t_{k+1}f(x_{k+1})=\sum_{i=1}^{k+1}t_if(x_i).$$Our inductive step is now complete.

$\endgroup$
0
$\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$.

$\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.