= Solution
Let $V,V',U$ be mutually independent, with $V,V'$ identically distributed. <Entropy submodularity for three independent sums> gives
$$
H(V+V'+U)+H(U)\leq H(V+U)+H(V'+U).
$$
Independent addition cannot decrease discrete entropy, because $H(V+V'+U)\geq H(V+V'+U\mid U)=H(V+V')$. Hence
$$
H(V+V')+H(U)\leq H(U+V)+H(U+V').
$$
Take $U$ to have the distribution of $-X$ and take $V,V'$ to be independent copies of $X$, all mutually independent. Then $U+V$ and $U+V'$ both have the distribution of $X-Y$, whereas $V+V'$ has the distribution of $X+Y$ and $H(U)=H(X)$. Hence
$$
H(X+Y)+H(X)\leq2H(X-Y),
$$
or
$$
H(X+Y)-H(X)\leq2\{H(X-Y)-H(X)\}.
$$
The denominator is nonnegative because conditioning on $Y$ recovers $X$ from $X-Y$, so $H(X-Y)\geq H(X-Y\mid Y)=H(X)$.
Back to article page
