Para provar que a solução da recorrência \( T(n) = \begin{cases} 2, & \text{se } n = 2 \\ 2T(n/2) + n, & \text{se } n = 2^k, \text{ para } k > 1 \end{cases} \) é \( T(n) = n \log n \) quando \( n \) é uma potência de 2, podemos usar indução matemática. Base da indução: Para \( n = 2 \), temos \( T(2) = 2 \), que é verdadeiro, pois \( 2 = 2 \log 2 \). Hipótese de indução: Suponha que a afirmação seja verdadeira para \( n = 2^k \), ou seja, \( T(2^k) = 2^k \log 2^k \). Passo da indução: Para \( n = 2^{k+1} \), temos: \( T(2^{k+1}) = 2T(2^{k+1}/2) + 2^{k+1} \) \( T(2^{k+1}) = 2T(2^k) + 2^{k+1} \) (substituindo \( n = 2^{k+1} \) na recorrência) \( T(2^{k+1}) = 2(2^k \log 2^k) + 2^{k+1} \) (usando a hipótese de indução) \( T(2^{k+1}) = 2^{k+1} \log 2^k + 2^{k+1} \) \( T(2^{k+1}) = 2^{k+1} (k + 1) \) \( T(2^{k+1}) = 2^{k+1} \log 2^{k+1} \) Portanto, por indução matemática, a solução da recorrência \( T(n) = n \log n \) é válida quando \( n \) é uma potência de 2.