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

我们可以使用数学归纳法来证明这个递归式的解为 T(n) = nlog2(n)。

首先，当 n=1 时，T(1) = 0，成立。

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

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

现在我们来考虑 n=2k 时的情况，即 T(2k) = 2T(k) + 2k。

根据假设，T(k) = klog2(k)，所以 T(2k) = 2klog2(k) + 2k = 2k(log2(k) + 1) = 2klog2(2k)。

因此，由数学归纳法可知，对于所有 n=2的指数倍，T(n) = nlog2(n) 成立。