Demostración de una relación de recurrencia con inducción

Question

He tenido problemas con una tarea que recibí con el curso que estoy siguiendo. La tarea en cuestión:

Utilice la inducción para demostrar que cuando $n \geq 2$ es una potencia exacta de $2$ la solución de la recurrencia

$$T(n) = \begin{cases} 2 & \text{ if } n = 2,\\ 2T(n/2)+n & \text{ if } n =2^k, k > 1 \\ \end{cases} $$

es $T(n) = n\log(n)$

NOTA: los logaritmos de la tarea tienen base $2$ .

El caso base aquí es obvio, cuando $n = 2$ tenemos que $2 = 2\log(2)$ . Sin embargo, estoy atascado en el paso aquí y no estoy seguro de cómo resolver esto.

Answer 1

Dejemos que $T(n)=n\log{n}$ Aquí $n=2^k$ para algún k. Entonces supongo que tenemos que demostrar que la igualdad se mantiene para $k+1$ Es decir $2n=2^{k+1}$ . $T(2n)=2T(n)+2n=2n\log{n}+2n=2n(\log{n}+1)=2n\log{2n}$