0
$\begingroup$

I was docked a few points on a homework assignment for not simplifying this expression, but I don't see how to simplify it much further:

$$ H(X_n) = -\sum_{i=1}^{n} \frac{1}{1-\frac{1}{2^n}} \cdot 2^{-i} \cdot \log_2(\frac{1}{1-\frac{1}{2^n}}) \cdot 2^{-i} $$

I've tried a few things such as:

$$ -\frac{1}{1-\frac{1}{2^n}}\sum_{i=1}^{n} 2^{-i} \cdot \log_2(\frac{1}{1-\frac{1}{2^n}} \cdot 2^{-i}) $$ $$ -\frac{1}{1-\frac{1}{2^n}}\sum_{i=1}^{n} 2^{-i} \cdot (\log_2(1) - \log_2(1-\frac{1}{2^n}) + \log_22^{-i}) $$

$$ -\frac{1}{1-\frac{1}{2^n}}\sum_{i=1}^{n} 2^{-i} \cdot (- \log_2(1-\frac{1}{2^n}) -i) $$

This doesn't seem simpler, and I'm not sure what to do next.

$\endgroup$
1
  • $\begingroup$ $\sum_{i=1}^n2^{-i}=1-\frac {1}{2^n}.$ As for $\sum_{i=1}^ni2^{-i},$ let $f(x)=\sum_{i=1} ^nx^i.$ We have $xf'(x)=\sum_{i=1}^nix^i.$ And for $x\ne 1$ we have $f(x)=x(1-x^n)/(1-x).$ $\endgroup$ Jan 10, 2017 at 12:09

2 Answers 2

1
$\begingroup$

$$\eqalign{ H(X_n) &=-\frac{1}{1-\frac{1}{2^n}}\log_2\Bigl(\frac{1}{1-\frac{1}{2^n}}\Bigr) \sum_{i=1}^{n}2^{-i}2^{-i}\cr &=\frac{2^n}{2^n-1}\log_2\Bigl(1-\frac{1}{2^n}\Bigr)\sum_{i=1}^{n}4^{-i}\cr &=\frac{2^n}{2^n-1}\log_2\Bigl(\frac{2^n-1}{2^n}\Bigr)\frac14\frac{1-4^{-n}}{1-4^{-1}}\cr &=\frac{2^n}{2^n-1}\log_2\Bigl(\frac{2^n-1}{2^n}\Bigr)\frac13\frac{4^n-1}{4^n}\cr &=\frac13\frac{2^n+1}{2^n}\log_2\Bigl(\frac{2^n-1}{2^n}\Bigr) \cr}$$ The hard part is knowing when to stop. You could split up the fraction and the logarithm if you want, but IMHO this is probably the best answer.

$\endgroup$
1
$\begingroup$

Assume all your calculations are correct. $$ \log_2\bigg(1-\frac{1}{2^n}\biggr)=\log_2\frac{2^n-1}{2^n}=\log_2(2^n-1)-n $$ and can be taken out of the summation sign.

On the other hand, $$ \sum_{i=1}^n2^{-i} $$ and $$ \sum_{i=1}^ni2^{-i} $$ can be calculated further.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.