How to analyze this recursion?

Question

How can I analyze this recursion for $k>0$? $$T(n)=n+T\left(\frac{n}{2}\right)+T\left(\frac{n}{4}\right)+T\left(\frac{n}{8}\right)+\cdots+T\left(\frac{n}{2^k}\right)$$

I want to prove that $T(n)=\theta(n\log(n))$.

Is it true that $T(n)=n+\frac{n}{2}+\cdots+\frac{n}{2}=n+\frac{n}{2}\log(n)$?

I got it by iterations method of these:

\begin{align}T(n)&=n+T\left(\frac{n}{2}\right)+T\left(\frac{n}{4}\right)+T\left(\frac{n}{8}\right)+\cdots+T\left(\frac{n}{2^k}\right)\\ T\left(\frac{n}{2}\right)&=\frac{n}{2}+T\left(\frac{n}{4}\right)+T\left(\frac{n}{8}\right)+T\left(\frac{n}{16}\right)+\cdots+T\left(\frac{n}{2^{k+1}}\right)\\ T\left(\frac{n}{4}\right)&=\frac{n}{4}+T\left(\frac{n}{8}\right)+T\left(\frac{n}{16}\right)+T\left(\frac{n}{32}\right)+\cdots+T\left(\frac{n}{2^{k+2}}\right)\\ T\left(\frac{n}{8}\right)&=\frac{n}{8}+T\left(\frac{n}{16}\right)+T\left(\frac{n}{32}\right)+\cdots+T\left(\frac{n}{2^{k+3}}\right)\\ &\vdots\end{align}

Answer 1

We have $$ T\left(\frac{n}{2}\right) = \frac{n}{2} + T\left(\frac{n}{4}\right) + \cdots + T\left(\frac{n}{2^{k+1}}\right) \tag{$1$} $$ and $$ T\left(n\right) = n + T\left(\frac{n}{2}\right) + \cdots + T\left(\frac{n}{2^{k}}\right) \tag{$2$} $$ By $(2) - (1)$, we have $$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{2} - T\left(\frac{n}{2^{k+1}}\right) \tag{$3$} $$ implying (if $T(n) \geq 0$ for all $n$) $$ T(n) \leq 2T\left(\frac{n}{2}\right) + \frac{n}{2} $$Thus by master theorem, $$ T(n) = \mathcal{O}(n \log n) $$

---

We can not conclude $T(n) = \Omega(n \log n)$ if $k$ is fixed. As a counterexample, when $k = 1$, we have $$ T(n) = T\left(\frac{n}{2}\right) + n $$ and in this case, $T(n) = \Theta(n)$.