看《数据结构与算法分析》有不懂的地方

Question

《数据结构与算法分析》马克艾伦维斯 C语言描述第二版 第24页
前提:若N=2的k次，则T(N)=N*(k+1)。那为什么T(N)=NlogN+N=O(NlogN)？

Answer 1

T(n)=2T(n/2)+n
    =2(2T(n/2*2)+n)+n
    =2(2(2T(n/2*2*2)+n)+n)+n
    =2^3T(n/2^3)+3n
    =...
    =2^kT(n/2^k)+kn            现在设 n=2^k
    =nT(1)+kn
    =n(T(1)+k)            T(1)是常数，可以忽略
    =kn
    =nlogn