Доказательство рекуррентного соотношения с индукцией

Question

У меня были проблемы с заданием, которое я получил с курсом, которым я следую.Соответствующее задание:

Используйте индукцию, чтобы доказать, что когда n> = 2 - точная степень 2, решение повторения:

T(n) = {2 if n = 2, 
        2T(n/2)+n if n =2^k with k > 1 }
is T(n) = nlog(n)

ПРИМЕЧАНИЕ: логарифмы в назначенииесть база 2.

Базовый случай здесь очевиден, когда n = 2, мы имеем, что 2 = 2log (2) Однако я застрял на шаге здесь, и я не уверен, как решить эту проблему.

Answer 1

Шаг. Предположим, что утверждение верно для 2 ^ m для всех m <= k, и покажем его для 2 ^ {k + 1}. </p>

Тогда T (2 ^ {k + 1}) = 2T (2 ^ k) + 2 ^ {k + 1}.

По предположению индукции T (2 ^ k) = 2 ^ k * log (2 ^ k), т. Е. T (2 ^ k) = k * 2 ^ k (поскольку здесь логарифмы имеют основание 2).

Следовательно, T (2 ^ {k + 1}) = 2 * k * 2 ^ k + 2 ^ {k + 1} = 2 ^ {k + 1} * (k + 1), что можно записать как 2 ^ {k + 1} * log (2 ^ {k + 1}), завершая доказательство.