How to tackle a recurrence that contains the sum of all previous elements? Say I have the following recurrence:
$$T(n) = n + T\left(\frac{n}{2}\right) + n + T\left(\frac{n}{4}\right) + n + T\left(\frac{n}{8}\right) + \cdots +n + T\left(\frac{n}{n}\right) $$
where $n = 2^k$, $k \in \mathbb{N} $ and $T(1) = 1$.
simplified to:
$$T(n) = n \log_2n + \sum_{i=1}^{\log_2n}T\left(\frac{n}{2^i}\right)  $$
The Master's theorem is not applicable; neither is the Akra-Bazzi method since $k = \log_2$ is not a constant. 
What strategy can I use to find a closed form solution? I have a feeling that the closed form is $T(n) = \sum_{i=0}^{\log_2n}\left[j\frac{n}{2^i}  \log_2 \left(\frac{n}{2^i} \right)\right] + 1 $ where $j = \max\left(1, 2^{i-1}\right)$ but would like a proof.
 A: Since we only need and evaluate $T(n)$ when $n$ is a power of $2$, say that $a(k)=T(2^k)$. The recursion becomes (I will use $n$ again from now on):
$$
a(n)=n2^n+\sum_{i=0}^{n-1}a(i)
$$
Define $s(n)=\sum_{i=0}^na(i)$. The above relation can be rewritten to
$$
s(n)-s(n-1)=n2^n+s(n-1)
$$
thus
$$
s(n)=n2^n+2s(n-1)
$$
This is is just a first degree linear recurrence relation that should be solvable.
Since we have $T(1)=1$, it follows that $a(0)=1$ and thus $s(0)=1$. The general solution for the recursion relation is
$$
s(n)=2^{n-1}(n(n+1)+C)
$$
for any constant $C$. (I found this using mathematica. The homogeneous part ($C2^{n-1}$) is obvious, but the inhomogeneous part is (probably) easiest found by writing out some small values. See @CarstenSchultz's comment below for a nice way to find it.) Solving this with $n=0$ gives
$$
1=\frac 12 C
$$
Thus, $C=2$ and we get
$$
s(n)=2^{n-1}(2+n+n^2)\\
a(n)=s(n)-s(n-1)=2^{n-2}(2+3n+n^2)\\
T(2^n)=s(n)-s(n-1)=2^{n-2}(2+3n+n^2)\\
$$
Note that $a(0)=T(1)=1\neq s(0)-s(-1)=\frac 12$. Since $s(0)=1$, we have $s(-1)=0$, which makes sense since it is an empty sum. The formula for $s(n)$ is thus only valid for nonnegative $n$.
A: As an additional comment on this, note that if we define $T(n)$ for all $n$ and not just powers of two with $T(0)=0$ and $T(1)=1$ like this
$$T(n) = \sum_{k=1}^{\lfloor \log_2 n \rfloor} T(\lfloor n/2^k \rfloor)
+ n \lfloor \log_2 n \rfloor,$$
and the binary representation of $n$ is given by
$$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k$$
then the exact formula for all $n$  where $n\ge 2$ is 
$$T(n) = 2^{\lfloor \log_2 n \rfloor - 1} + \sum_{j=0}^{\lfloor \log_2 n \rfloor} 
(\lfloor \log_2 n \rfloor -j ) 
[z^j] \frac{1-z}{1-2z} \sum_{k=j}^{\lfloor \log_2 n \rfloor}  d_k 2^{k-j}$$
because $$\frac{1}{1-z-z^2-z^3-\cdots} = \frac{1-z}{1-2z}.$$
This simplifies to
$$2^{\lfloor \log_2 n \rfloor - 1} + \lfloor \log_2 n \rfloor \times n +
\sum_{j=1}^{\lfloor \log_2 n \rfloor} 
(\lfloor \log_2 n \rfloor -j ) 
[z^j] \frac{1-z}{1-2z} \sum_{k=j}^{\lfloor \log_2 n \rfloor}  d_k 2^{k-j}$$
Now note that for $j\ge 1$
$$[z^j] \frac{1-z}{1-2z} = 2^{j-1}$$ so this in turn again simplifies, this time to
$$2^{\lfloor \log_2 n \rfloor - 1} + \lfloor \log_2 n \rfloor \times n +
\sum_{j=1}^{\lfloor \log_2 n \rfloor} 
(\lfloor \log_2 n \rfloor -j ) 
2^{j-1} \sum_{k=j}^{\lfloor \log_2 n \rfloor}  d_k 2^{k-j}$$
which is
$$2^{\lfloor \log_2 n \rfloor - 1} + \lfloor \log_2 n \rfloor \times n +
\frac{1}{2} \sum_{j=1}^{\lfloor \log_2 n \rfloor} 
(\lfloor \log_2 n \rfloor -j ) 
\sum_{k=j}^{\lfloor \log_2 n \rfloor}  d_k 2^k.$$
Now for an upper bound consider a string of one digits giving
$$T(n)\le 2^{\lfloor \log_2 n \rfloor - 1} + \lfloor \log_2 n \rfloor \times n +
\frac{1}{2} \sum_{j=1}^{\lfloor \log_2 n \rfloor} 
(\lfloor \log_2 n \rfloor -j ) (2^{\lfloor \log_2 n \rfloor+1}-2^j)
\\=  2^{\lfloor \log_2 n \rfloor - 1} + \lfloor \log_2 n \rfloor \times n +
\frac{1}{2} (\lfloor \log_2 n \rfloor +1)
\left(\lfloor \log_2 n \rfloor 2^{\lfloor \log_2 n \rfloor}
- 2^{\lfloor \log_2 n \rfloor+1} + 2\right).$$
For a lower bound consider a one digit followed by zeros giving
$$T(n)\ge 2^{\lfloor \log_2 n \rfloor - 1} + \lfloor \log_2 n \rfloor \times n +
\frac{1}{2} \sum_{j=1}^{\lfloor \log_2 n \rfloor} 
(\lfloor \log_2 n \rfloor -j ) 2^{\lfloor \log_2 n \rfloor}
\\ = 2^{\lfloor \log_2 n \rfloor - 1} + \lfloor \log_2 n \rfloor \times n +
\frac{1}{4} \lfloor \log_2 n \rfloor(\lfloor \log_2 n \rfloor - 1) 
2^{\lfloor \log_2 n \rfloor}.$$
The upper and lower bounds are attained and cannot be improved upon.
Selecting the dominant terms from the two bounds we finally get a complexity of
$$\Theta\left((\lfloor \log_2 n \rfloor)^2\times 2^{\lfloor \log_2 n \rfloor}\right)
= \Theta\left((\log_2 n)^2 2^{\log_2 n}\right)
= \Theta\left(n \times (\log_2 n)^2\right).$$
A similar calculation was done at this MSE link.
Addendum. The sequence of values of $T(2^j)$ using our definition is
$$3, 12, 40, 120, 336, 896, 2304, 5760, 14080, 33792,\ldots$$
which agrees (as it ought to) with the formula found by @Ragnar
$$T(2^j) = 2^{j-2}\times(2+3j+j^2).$$
(This is just a re-write of our lower bound, which to give credit was posted second.)
Remark as of Sat Feb  8 20:37:05 CET 2014. The upper limit of the outer sum can be replaced by $\lfloor \log_2 n\rfloor-1$ but the formulas are correct as stated.
A: I'd just start with $T(1)$ and look for a pattern:
$$T(2^1) = 1 \cdot 2^1 + 2^{1-1}T(1)$$
$$T(2^2) = 2\cdot 2^2 + 1\cdot 2^1 + (2^{2-1}) T(1)$$
$$T(2^3) = 3\cdot 2^3 + 2\cdot 2^2 + 2 \cdot 1 \cdot 2^1 + 2^{3-1} T(1)$$
$$T(2^4) = 4\cdot 2^4 + 3\cdot 2^3 + 2 \cdot 2 \cdot 2^2 + 4 \cdot 1 \cdot 2^1 + 2^{4-1} T(1)$$
so that if $T(1) = 1$,
$$T(2^n) = 2^{n-1} + \sum_{k=1}^n k \cdot 2^k + \sum_{k=1}^{n-2} (2^{n-k-1}-1)2^k.$$
