# Jensen's inequality proof explanation

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.

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.

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

• 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. – Basem Fouda Sep 24 '16 at 12:12
• 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... – Peter Melech Sep 24 '16 at 12:16
• 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$ – Peter Melech Sep 24 '16 at 12:21
• 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. – Basem Fouda Sep 25 '16 at 14:58
• 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. – Basem Fouda Sep 25 '16 at 15:00