0

I am given that, $$ x \log_2(x) + (1-x)\log_2(1-x) \geq -1 $$ for $ 0 < x< 1$

I am supposed to show that, $$ \sum_{i=1}^{2^n}x_i \log_2 x_i \geq -n $$ where $$ \sum_{i=1}^{2^n} x_i = 1 $$ and $x_i > 0$, for all $i$.

So I guess it's a job for induction. The first step is already done. Assuming it's right for the $p$th step,

$$ \sum_{i=1}^{2^p}x_i \log_2 x_i \geq -p $$

$$ \sum_{i=1}^{2^p} x_i = 1 $$ and $x_i > 0$, for all $i$.

So now I have to go from this step to $p+1$st step. However, I cannot understand how to keep the condition of $ \sum_{i=1}^{2^p} x_i = 1 $ intact when I go to the $(p+1)$st step.

Is there anyway of doing this? Or am I going in the wrong direction?

Please help.

egreg
  • 238,574
PPGoodMan
  • 297

1 Answers1

0

Here's an idea for starting the induction step.

Assume your statement is true for $p$. Now suppose $\displaystyle \sum_{i=1}^{2^{p+1}}x_i=1$ with $x_i >0$. Then the subsequence $\displaystyle\sum_{i=1}^{2^p}x_i$ converges to some $a$. Since $x_i \geq 0$, we know $a>0$ and thus $\displaystyle 1 = \sum_{i=1}^{2^p}\frac{x_i}{a}$ with $\frac{x_i}{a}>0$. So from our induction assumption we get $\displaystyle \sum_{i=1}^{2^p}\frac{x_i}{a} \log_2(\frac{x_i}{a}) \geq -p$.

sfmiller940
  • 379