Proof of inequality between sums Let $\{y_i\}_{i=1}^N, \{z_i\}_{i=1}^N$ be two sets of real numbers s.t. $y_i, z_i \ge 0$, $\sum_{i=1}^N y_i = 1$, $\sum_{i=1}^N z_i \le 1$.
I have been asked to show that 
$$ \sum_{i=1}^N y_i \log \left(\frac{y_i}{z_i}\right) \ge \sum_{i=1}^N (y_i - z_i)^2 $$
I thought I could go by induction:
in case $N=1$ the statement reduces to
$$\forall z \in [0,1] \qquad  -\log(z) \ge (1-z)^2 $$
which can be easily proved (for example by noticing that $-\log(z) - (1-z)^2$ goes to $+\infty$ as $z \to 0$, is $0$ for $z=1$ and the derivative is always negative).
For the inductive step I thought I could reason this way:
assuming the claim holds up to $N-1$, given the two sets $\{y_i\}_{i=1}^N, \{z_i\}_{i=1}^N$ we can obtain two sets with cardinality $N-1$ by just replacing the last two terms with their sum. This way we obtain two sets for which the claim holds, so the only thing to show is that
$$ a\,\log\left(\frac{a}{b}\right) - (a-b)^2 + c\, \log\left(\frac{c}{d}\right) -(c-d)^2 \ge (a+c)\,\log\left(\frac{a+c}{b+d}\right)-(a+c-b-d)^2 $$
i.e.
$$ a\,\log\left(\frac{a}{b}\right)+ c\, \log\left(\frac{c}{d}\right) \ge (a+c)\,\log\left(\frac{a+c}{b+d}\right)-2\,(a-b)(c-d) $$
where $a,c$ are the lasts two elements of $\{y_i\}$ (and respectively $b,d$ are the lasts two of $\{z_i\}$).
Here is where I got stuck, I don't really know how to prove this last inequality (in particular I don't know how to get rid of the last $-2(a-b)(c-d)$ term, which I cannot assume to be $\le0$).
Besides I'm not sure whether there is a simpler way to prove the statement.
 A: Actually, you CAN assume $(a-b)(c-d) \ge 0$, starting from $N \ge 3$. (With this assumption the last inequality is true by Jensen for the convex function $x\log x$.)
Lemma. If $N\ge 3$ then there exist $i,j \ (i\neq j)$ such that $(y_i - z_i)(y_j-z_j) \ge 0$.
Proof. Denote $x_i=y_i-z_i$. Obviously, among $N$ numbers $x_1,\ldots,x_n$ there must exist two numbers having the same sign. Done. 
Thus the complete proof will contain:


*

*Proof for $N=1,2$.

*Proof for $N\ge 3$: what you did above, but before that, apply the above lemma to assume that $(y_{n-1} - z_{n-1})(y_n-z_n) \ge 0$.

A: An alternative, straightforward proof of a slightly weaker statement, based on Pinsker's inequality.
Proposition. Let $\{y_i\}_{i=1}^N, \{z_i\}_{i=1}^N$ be two sets of real numbers s.t. $y_i, z_i \ge 0$, $\sum_{i=1}^N y_i = 1$, $\sum_{i=1}^N z_i \le 1$.
Then
$$ \sum_{i=1}^N y_i \log \left(\frac{y_i}{z_i}\right) \ge \frac{1}2{}\sum_{i=1}^N (y_i - z_i)^2 $$
Proof. We start by reducing the problem to a specific case.
Lemma 1. It is sufficient to prove the statement under the assumption $\sum_{i=1}^N y_i = \sum_{i=1}^N z_i = 1$.
Proof. If $\sum_{i=1}^N z_i < 1$, add an $(N+1)$-st element $y_{N+1}=0$, $z_{N+1}=1-\sum_{i=1}^N z_i > 0$. Assuming the statement holds for this case, since by convention/continuity $0\ln0=0$:
$$
\sum_{i=1}^{N} y_i \ln \frac{y_i}{z_i}
= \sum_{i=1}^{N+1} y_i \ln \frac{y_i}{z_i}
\geq \sum_{i=1}^{N+1} (y_i-z_i)^2 > \sum_{i=1}^{N} (y_i-z_i)^2
$$
establishing the sought result. $\blacksquare$
We therefore only consider this case. But now $y\stackrel{\rm def}{=}(y_1,\dots,y_N)$ and $z\stackrel{\rm def}{=}(z_1,\dots,z_N)$ define probability distributions over $[N]=\{1,\dots,N\}$, and the LHS is exactly the Kullback—Leibler divergence $D(y \| z) = \sum_{i=1}^N y_i \ln \frac{y_i}{z_i}$ (in nats) between $y$ and $z$. So the question boils down to proving
$$
D(y \| z) \geq \| y -z\|_2^2. \tag{1}
$$
We start with Pinsker's inequality
$$
D(y \| z) \geq 2\operatorname{d}_{\rm TV}(y,z)^2
= \frac{1}{2}\| y -z\|_1^2
\geq \frac{1}{2}\| y -z\|_2^2
$$
where the equality is the relation between total variation and $\ell_1$ distance, and the second inequality the mononicity of $\ell_p$ norms. This proves the proposition. $\blacksquare$
