Could you please check if this substitution is right so far? The question:
Use resubstitution to solve the following recurrence equation:
$$T(n) = 2T(n-1) + n;\; n \ge2\text{ and }T(1) = 1.$$
So far I have this:
$$\begin{align}T(n) &= 2T(n-1) + n\\
&= 2(2T(n-2) + (n-1)) + n\\
&= 4T(n-2) + 3n -2\\
&= 2(4T(n-3) + 3(n-1) -2) + n\\
&= 2(4T(n-3) + 3n -3 -2) + n\\
&= 2(4T(n-3) + 3n -5) + n\\
&= 8T(n-3) + 6n - 10 + n\\
&= 8T(n-3) +7n -10\end{align}$$
I'm just wondering if so far, the way I'm approaching this is correct. Any help is appreciated, thank you.
 A: You are perhaps making it a little harder than necessary to take the next step. When you unwrap a recurrence in this way, it’s often a good idea not to combine the terms that don’t involve $T$:
$$\begin{align*}
T(n)&=2T(n-1)+n\\
&=2\Big(2T(n-2)+(n-1)\Big)+n\\
&=2^2T(n-2)+2(n-1)+n\\
&=2^2\Big(2T(n-3)+(n-2)\Big)+2(n-1)+n\\
&=2^3T(n-3)+2^2(n-2)+2(n-1)+n\;.
\end{align*}$$
When you leave the intermediate results in this form, it’s very easy to see that after $k$ steps you’ll have
$$\begin{align*}
T(n)&=2^kT(n-k)+2^{k-1}\big(n-(k-1)\big)+2^{k-2}\big(n-(k-2)\big)+\ldots+2^1(n-1)+2^0n\\
&=2^kT(n-k)+\sum_{i=0}^{k-1}2^i(n-i)\;.
\end{align*}$$
This makes it easy to see what the final step of the unwrapping will yield, and it also tells you that you’ll need to be able to work out
$$\sum_{i=0}^m2^i(n-i)=\sum_{i=0}^m2^in-\sum_{i=0}^m2^ii=n\sum_{i=0}^m2^i-\sum_{i=0}^mi2^i$$
for some value of $m$. One of those last two sums is easy, since it’s geometric; the other is a little trickier, but it’s been discussed many times on this site.
