Help with recurrence $T(n) = T(n/2) + n$ I just need help seeing where I went wrong in this solution. 
$$T(n) = T\left(\frac{n}{2}\right) + n,~~~ T(1) = 0$$
By master theorem, this is $\theta(n)$.
However, when I try to solve it, it doesn't come out right. Where is my logic error?
$$T(n) = T\left(\frac{n}{2}\right) + n$$
$$T(n) = T\left(\frac{n}{4}\right) + n + n$$
$$T(n) = T\left(\frac{n}{8}\right) + n + n + n$$
$$T(n) = T\left(\frac{n}{16}\right) + n + n + n$$
Thus, the pattern appears to be:
$$T(n) = T\left(\frac{n}{2^k}\right) + kn,~~~ k>0$$
If we assume $n = 2^k$,
$$T(n)=T\left(\frac{n}{n}\right)+kn$$ 
$$T(n)=T\left(1\right)+kn$$ 
$$T(n)=0+kn$$ 
$$T(n)=kn$$ 
$k = \log_2 n$, so this can be rewritten as: 
$$T(n) = n \log_2(n)$$
However, this is incorrect. Where did I go wrong?
Thanks!
 A: Hint:
$$T(n) = T\left(\frac{n}{2}\right) + n$$
$$T(n) = T\left(\frac{n}{4}\right) + \frac{n}{2} + n$$
A: Actually, because it is a recurring sequence, you get:
$$T(n) = T\left(\frac{n}{2}\right) + n$$
$$T(\frac{n}{2}) = T\left(\frac{\frac{n}{2}}{2}\right) + \frac{n}{2}=T\left(\frac{n}{4}\right)+\frac{n}{2}$$
And so on:
$$T(n) = T\left(\frac{n}{2}\right) + n$$
$$T(n) = T\left(\frac{n}{4}\right)+\frac{n}{2} + n$$
$$T(n) = T\left(\frac{n}{8}\right)+\frac{n}{4}+\frac{n}{2} + n$$
As you noticed the pattern, we do the same here:
$$T(n) = T\left(\frac{n}{2^k}\right)+\sum_{j=0}^{k-1} \frac{n}{2^j},~~~k>0$$
As per your assumption $n=2^k$, we have:
$$T(n)=T\left(\frac{n}{n}\right)+\sum_{j=0}^{k-1} \frac{n}{2^j}$$
$$T(n)=T\left(1\right)+\sum_{j=0}^{k-1} \frac{n}{2^j}$$
$$T(n)=0+\sum_{j=0}^{k-1} \frac{n}{2^j}$$
$$T(n)=n*\sum_{j=0}^{k-1} \frac{2^k}{2^j}$$
As you mentioned, $k=\log_2 n$:
$$T(n)=n*\sum_{j=0}^{\log_2 n-1} \frac{2^{\log_2 n}}{2^j}$$
Simplify the logarithm:
$$T(n)=n*\sum_{j=0}^{\log_2 n-1} \frac{n}{2^j}$$
