2

Let $N = 2^p$ for some $p \in \mathbb{N}$. Find the smallest upper bound for $\frac{N}{2}\log\left(\frac{N}{2}\right) + \frac{N}{4}\log\left(\frac{N}{4}\right) + \ldots + 1$

I guess I could first rewrite this to $\frac{2^p}{2}\log\left(\frac{2^p}{2}\right) + \frac{2^p}{4}\log\left(\frac{2^p}{4}\right) +\ldots+ 1$ and then to $2^{p-1}\log(2^{p-1}) + 2^{p-2}\log(2^{p-2}) +\ldots+1$ but I still don't know how I should proceed.

All help appreciated.

Edit: Now I though also writing it to the form $(p-1)2^{p-1} + (p-2)2^{p-2} + ... + 1 \Leftrightarrow \sum_{i=1}^{log N} (p-i)2^{p-i}$ but I still feel like ...

...  ;-(
(yes, the log is base 2, sorry, forgot to mention that)
postasaquest
  • 23

3 Answers3

3

You want

$\begin{align} \sum_{k=1}^p \frac{n}{2^k}\ln \frac{n}{2^k} &=\sum_{k=1}^p \frac{n}{2^k}(\ln n- \ln {2^k})\\ &=\sum_{k=1}^p \frac{n}{2^k}(\ln n- k\ln {2})\\ &=n \ln n\sum_{k=1}^p \frac{1}{2^k} -n\ln 2\sum_{k=1}^p \frac{k}{2^k} \\ \end{align} $

For not small $p$, $\sum_{k=1}^p \frac{1}{2^k} \approx 1$. Since $\sum_{k=1}^{\infty} k x^k = \frac{x}{(1-x)^2}$, $\sum_{k=1}^p \frac{k}{2^k} \approx \frac{1/2}{(1-1/2)^2} =2 $, so your sum $\approx n \ln n- 2 n \ln 2$.

You can get it more exactly by getting the exact form for $\sum_{k=1}^p k x^k$, but the difference is of order $\frac{p}{2^p}=\frac{\ln n}{n}$, so I will leave that to you.

marty cohen
  • 107,799
  • As I posted in my answer, the sum $\sum_{k=1}^pk2^k = 2 + 2^p(p-1)$. Yours is a very nice solution, by the way. It solves the problem for general $n$. – Daniel Robert-Nicoud Jun 12 '13 at 17:43
1

Fix $k = \log 2 = 1$. Then expression yields

$$\begin {eqnarray} S & = & \frac {N} {2} (\log N - k) + \frac {N} {4} (\log N - 2k) + \cdots + \frac {N} {2^{p - 1}} (\log N - (p - 1)k) + 1 \nonumber \\ & = & N \log N (\frac {1} {2} + \frac {1} {4} + \cdots + \frac {1} {2^{p - 1}}) - N (\frac {1} {2} + \frac {2} {4} + \cdots + \frac {p - 1} {2^{p - 1}}) + 1 \nonumber \\ & > & N \log N - 2 \log N - 2N + 1 \nonumber \\ & = & p 2^p - 2^p - 2p + 1. \end {eqnarray}$$

0

By properties of the logarithm:

$$\sum_{k = 1}^{p-1}2^k\log_2(2^k) = \sum_{k = 1}^{p-1}k2^k = 2+2^{p-1}(p-2)$$

where you can prove the last step with a simple induction.

Daniel Robert-Nicoud
  • 29,795