Prove that for any positive integer $n$ and $d$, $\sum_{k=0}^d 2^k\log_2(\frac{n}{2^k})=2^{d+1}\log_2(\frac{n}{2^{d-1}})-2-\log_2{n}$ I could prove it by induction, but I need to see how I might have discovered it for myself (cause that's what's gonna be on exam).
 A: Hint. One may observe that
$$
\begin{align}
2^{k+1}\log_2\left(\frac{n}{2^{k+1}}\right)-2^k\log_2\left(\frac{n}{2^k}\right)&=2^k\left(\log_2\left(\frac{n^2}{2^{2k+2}}\right)-\log_2\left(\frac{n}{2^k}\right)\right)\\\\
&=2^k\log_2\left(\frac{n^2}{2^{2k+2}}\times\frac{2^k}{n}\right)\\\\
&=2^k\log_2\left(\frac{n}{2^{k+2}}\right)\\\\
&=2^k\log_2\left(\frac{n}{2^k}\right)-2^{k+1}
\end{align}
$$ then summing from $k=0$ to $k=d$, terms telescope, giving the desired result.
A: HINT:
$$\sum_{k=0}^d 2^k\log_2(\frac{n}{2^k})=\log_2n\sum_{k=0}^d 2^k\log_2(2^{-k})$$
$$=-\log_2n\sum_{k=0}^d k2^k$$
See Mathematical Induction (summation): $\sum^n_{k=1} k2^k =(n-1)(2^{n+1})+2$
A: That sum of logs suggests raising $2$ to the power of the lefthand side to get a product not involving logs:
$$\prod_{k=0}^d\left(\frac{n}{2^k}\right)^{2^k}=\frac{n^{\sum_{k=0}^d2^k}}{2^{\sum_{k=0}^dk2^k}}=\frac{n^{2^{d+1}-1}}{2^{(d-1)2^{d+1}+2}}\;,$$
where to get the denominator I used this result.
Now notice that if you multiply the numerator by $n$ and the denominator by $2^{-2}$, you have the $2^{d+1}$ power of the fraction $\frac{n}{2^{d-1}}$, so
$$\prod_{k=0}^d\left(\frac{n}{2^k}\right)^{2^k}=\left(\frac{n}{2^{d-1}}\right)^{2^{d+1}}\cdot\frac1{2^2n}\;.$$
Finally, take logs base $2$ again, and the righthand side drops right out.
