Demuestra que para cualquier entero positivo $n$ y $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}$

Question

Podría demostrarlo por inducción, pero necesito ver cómo podría haberlo descubierto por mí mismo (porque eso es lo que estará en el examen).

Answer 1

Pista. Uno puede observar que $$ \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} $$ luego sumando desde $k=0$ hasta $k=d$, los términos se telescópico, dando el resultado deseado.

Answer 2

PISTA:

$$\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$$

Ver Inducción Matemática (sumatoria): $\sum^n_{k=1} k2^k =(n-1)(2^{n+1})+2$

Answer 3

Esa suma de logaritmos sugiere elevar $2$ a la potencia del lado izquierdo para obtener un producto que no involucre logaritmos:

$$\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}}\;,$$

donde para obtener el denominador utilicé este resultado.

Ahora observe que si multiplica el numerador por $n$ y el denominador por $2^{-2}$, obtendrá el poder de $2^{d+1}$ de la fracción $\frac{n}{2^{d-1}}$, por lo que

$$\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}\;.$$

Finalmente, vuelva a tomar logaritmos en base $2$, y el lado derecho desaparecerá por completo.