Solving recurrence relation $T(n) = 2T(n - 1) + \Theta(n)$ using the recursion tree method I am trying to solve this recursive relation using the recursion tree method: 
$T(n) = 2T(n - 1) + \Theta(n)$ with $T(0) = \Theta(1)$.
The answer is $T(n) = 2^n*{\rm constant}_2 + (2^n - 1)n + \Theta(1) = \Theta(n  2^n)$
However, for this question when I sum all the left over terms from the last level to the first, as we do in the recursion tree method, I get $n * \Theta (n)$.
I don't  get the $\Theta(n * 2^n)$ term anywhere. 
Please see my solution below to see how I tried to solve this question. I really want to know where I went wrong...

 A: Recall that $\Theta(n)$ denotes any sequence $(R(n))$ such that there exists some finite and positive $n_0$, $c$ and $C$, such that $cn\leqslant R(n)\leqslant Cn$ for every $n\geqslant n_0$. Hence the hypothesis is that, for every $n\geqslant n_0$,
$$
2T(n-1)+cn\leqslant T(n)\leqslant 2T(n-1)+Cn.
$$
Equivalently, $t(n)=2^{-n}T(n)$ is such that, for every $n\geqslant n_0$,
$$
t(n-1)+cn2^{-n}\leqslant t(n)\leqslant t(n-1)+Cn2^{-n}.
$$
Iterating this yields
$$
t(n_0)+cs(n)\leqslant t(n)\leqslant t(n_0)+Cs(n),\qquad s(n)=\sum_{k=n_0+1}^{n}k2^{-k}.
$$
In particular, for every $n\geqslant n_0+1$,
$$
t(n_0)+cs_*\leqslant t(n)\leqslant t(n_0)+Cs^*,\qquad s_*=(n_0+1)2^{-n_0},\quad s^*=\sum_{k=n_0+1}^{+\infty}k2^{-k}.
$$
Assume for a moment that $s^*$ is finite. Then $a2^n\le T(n)\leqslant A2^n$ for every $n\geqslant n_0+1$, with $a=t(n_0)+cs_*$ and $A=t(n_0)+Cs^*$, both positive and finite, hence $\color{red}{T(n)=\Theta(2^n)}$.
Finally, $s^*$ is finite if and only if $s_0$ is, where
$$
s_0=\sum_{k=0}^{+\infty}k2^{-k}.
$$
Recall that $s_0=\frac12\sigma'\left(\frac12\right)$ where, for every $|x|\lt1$, 
$$
\sigma(x)=\sum_{k=0}^{+\infty}x^k=(1-x)^{-1},
$$
hence $\sigma'(x)=(1-x)^{-2}$ and $s_0=2$ is finite.
A: $\Theta(n2^n)$ can’t be correct. Let’s take a look at what happens without the asymptotics, say with $T(n)=2T(n-1)+n$ and $T(0)=1$. Then
$$\begin{align*}
T(n)&=2T(n-1)+n\\
&=4T(n-2)+2(n-1)+n\\
&=8T(n-3)+4(n-2)+2(n-1)+n\\
&\,\vdots\\
&=2^kT(n-k)+\sum_{i=0}^{k-1}2^i(n-i)\\
&\,\vdots\\
&=2^nT(0)+\sum_{i=0}^{n-1}2^i(n-i)\\
&=2^n+n(2^n-1)-\sum_{i=0}^{n-1}i2^i\\
&=2^n+n(2^n-1)-\sum_{i=1}^{n-1}\sum_{j=1}^i2^i\\
&=2^n+n(2^n-1)-\sum_{j=1}^{n-1}\sum_{i=j}^{n-1}2^i\\
&=2^n+n(2^n-1)-\sum_{j=1}^{n-1}(2^n-2^j)\\
&=2^n+n(2^n-1)-n2^n+\sum_{j=1}^{n-1}2^j\\
&=2^n-n+2^n-2\\
&=2^{n+1}-n-2\;.
\end{align*}$$
This is $\Theta(2^n)$, but it’s not $\Theta(n2^n)$, because it’s not $\Omega(n2^n)$: $$\lim_{n\to\infty}\frac{2^{n+1}-n-2}{n2^n}=0\;.$$
A: OK, I've been very confused by this notation, but are you sure that the answer is $\Theta(n\cdot2^n)$?
Your tree analysis is correct: at the first step, you add $\Theta(n)$, at the next one, you add $2 \Theta(n-1)$, at the next one $4\Theta(n-2)$, etc. In other words, at the $i$-th step, you add $2^i \Theta(n-i)$. Because you need to add all the steps, the actual sum is then 
$$T(n) = \sum_{i=0}^n 2^i  \Theta(n-i)$$
Now, since $\Theta(n)$ means "a function doing $n$ steps of computation", you can rewrite $\Theta(n-i)$ as $\Theta(n)-\Theta(i)$. The sum becomes
$$
T(n) = \sum_{i=0}^n 2^i  \Theta(n) - 2^i\Theta(i) = \sum_{i=0}^n 2^i  \Theta(n) - \sum_{i=0}^n 2^i\Theta(i)
$$
If we pull $\Theta(n)$ out of the sum, we can use the fact that $\sum_{i=0}^n 2^i = 2^{n+1} - 1$. Moreover, we can use the fact that $\sum_{i=0}^n i\cdot 2^i = 2(n\cdot 2^n - 2^n+1)$. The sum then becomes: 
$$
T(n) = n*(2^{n+1} - 1) - 2(n\cdot 2^n - 2^n + 1) = -n + 2^{n+1} - 2
$$
So I would conclude that $T(n)= \Theta(2^{n})$. 
Actually, according to Wolfram Alpha, we have $t(n) = -n + 3\cdot2^n - 2$. 
So either I also made a mistake in the calculation (which is obviously possible), or the answer is indeed $\Theta(2^n)$, as you found yourself. 
