Upper bound for expression involving logarithms 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)
 A: 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.
A: 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}$$
A: 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.
