# 二、请编写python证明当 T(n) = 2T(n/2)+n, T(1) = 0 时， T(n) = nlog2(n), 假设 n 是 2 的指数倍

我们可以使用归纳法来证明这个结论。

首先，当 n=1 时，根据题目条件，T(1)=0，而 nlog2(n) = 1*log2(1) = 0，因此结论成立。

接着，假设当 n=k 时，T(k) = klog2(k) 成立，即：

T(k) = 2T(k/2) + k = 2*(k/2*log2(k/2)) + k = k*log2(k) - k + k = k*log2(k)

现在我们来证明当 n=2k 时，T(2k) = 2k*log2(2k)。

当 n=2k 时，有：

T(2k) = 2T(k) + 2k = 2k*log2(k) + 2k

因为 k 是 2 的指数倍，所以 log2(k) 是整数，因此我们可以将 2k*log2(k) 表示为 k*log2(k) + k*log2(2) = k*log2(k) + k。

于是，我们有：

T(2k) = 2k*log2(k) + 2k = k*log2(k) + k + k*log2(2) = k*log2(2k)

因此，当 n=2k 时，T(n) = nlog2(n) 成立。

综上所述，结论成立。