Outside of the Goose Legs


Can you get from the result that Aaron was explaining today to a more general one, $\sum_{i=1}^{n}{p_i \log{u_i}}\leq \log{\sum_{i=1}^{n}{p_i u_i}}$

$\textit{Proof:}$ Ari taught us that if we can't solve a problem, make a harder one. So I am going to prove the general case for any function $f$ that is convex on an interval (Assume for this problem that the function is convex everywhere, since that is true for logarithms). Thus, we want to show that if $f''\leq 0$, then $\sum_{i=1}^{n}{p_i f(u_i)}\leq f(\sum_{i=1}^{n}{p_i u_i})$. We proceed with our proof using induction.

$\textbf{Base Case:}$ The case where $n=2$ is the definition of convexity, so it holds.

$\textbf{Inductive Step:}$ Assume that our inequality holds for $n$, we want to show that it also holds for $n+1$. Begin by writing out the terms in the left hand side. $$f(p_1 x_1+p_2 x_2+\cdots+ p_n x_n+p_{n+1} x_{n+1})$$ Group the last terms together under by multiplying by $\frac{p_n+p_{n+1}}{p_n+p_{n+1}}$. $$f \left( p_1 x_1+p_2 x_2+\cdots +(p_n x_n+p_{n+1} x_{n+1}) \frac{p_n x_n+p_{n+1} x_{n+1}}{p_n+p_{n+1}} \right)$$ Since this expression has $n$ terms, we can use our inductive hypothesis to get that our expression is greater than or equal to $$p_1f(x_1)+p_2f(x_2)\cdots+(p_n+p_{n+1})f \left(\frac{p_n x_n+p_{n+1} x_{n+1}}{p_n+p_{n+1}} \right)$$ This is very close to what we want to prove, so it remains to show $$p_1f(x_1)+\cdots+(p_n+p_{n+1})f \left(\frac{p_n x_n+p_{n+1} x_{n+1}}{p_n+p_{n+1}} \right)\geq p_1f(x_1)+\cdots+p_nf(x_n)+p_{n+1}f(x_{n+1})$$ $$\implies (p_n+p_{n+1})f \left(\frac{p_n x_n+p_{n+1} x_{n+1}}{p_n+p_{n+1}} \right)\geq p_nf(x_n)+p_{n+1}f(x_{n+1})$$ Rewriting $f \left(\frac{p_n x_n+p_{n+1}x_{n+1}}{p_n+p_{n+1}} \right)$ as $f \left(\frac{p_{n}}{p_n+p_{n+1}}\cdot x_n+\frac{p_{n+1}}{p_n+p_{n+1}}\cdot x_{n+1} \right)$, we can apply our base case to find that $$f \left(\frac{p_{n}}{p_n+p_{n+1}}\cdot x_n+\frac{p_{n+1}}{p_n+p_{n+1}}\cdot x_{n+1} \right) \geq \frac{p_{n}}{p_n+p_{n+1}}f(x_n)+\frac{p_{n+1}}{p_n+p_{n+1}}f(x_{n+1})$$ since $\frac{p_{n}}{p_n+p_{n+1}}+\frac{p_{n+1}}{p_n+p_{n+1}}=1$. Substituting back into our inequality, we get $$(p_n+p_{n+1})f \left(\frac{p_n x_n+p_{n+1} x_{n+1}}{p_n+p_{n+1}} \right)\geq p_nx_n+p_{n+1}x_{n+1}$$

We now have:

\begin{align*} &f \left( p_1 x_1+p_2 x_2+\cdots +(p_n x_n+p_{n+1} x_{n+1}) \frac{p_n x_n+p_{n+1} x_{n+1}}{p_n+p_{n+1}} \right)\\ \geq &p_1f(x_1)+p_2f(x_2)\cdots+(p_n+p_{n+1})f \left(\frac{p_n x_n+p_{n+1} x_{n+1}}{p_n+p_{n+1}} \right)\\ \geq &p_1f(x_1)+\cdots+p_nf(x_n)+p_{n+1}f(x_{n+1}) \end{align*}

This completes our proof by induction. Now note that $\log{x}$ is convex everywhere since it's second derivative is $-\frac{1}{x^2}\leq 0, \ \forall x>0$. Then, since we satisfy the convexity condition of our new theorem, the result is a direct application where $f(x)=\log{x}$, and we are done.

Previous
Previous

Kelly Coin and Matrices

Next
Next

Vesneeten: Home to the Blue and Green Eyed Dragons