<s>[INST] Solve the recurrence $T(n) = 2T(n-1) + n, T(1)=1, n\geq 2$ This question has been already solved here, I just want to figure out why I'm not being able to solve it using my method. Here's what I did -
$T(n)=2T(n-1)+n$
$T(n-1)=2T(n-2)+(n-1)$
$\therefore \,T(n)=2\{2T(n-2)+(n-1)\}+n$
$T(n)=4T(n-2)+3n-2$
$T(n-2)=2T(n-3)+(n-2)$
$\therefore T(n)=4\{2T(n-3)+(n-2)\}+3n-2$
$T(n)=8T(n-3)+7n-10$
$
\\.
\\.
\\.
\\T(n)=2^kT(n-k)+(2^k-1)n-c
\\\therefore T(n)=2^{n-1}T(1)+(2^{n-1}-1)n-c
\\T(n)=2^{n-1}+(2^{n-1}-1)n-c
$
This is where I'm stuck. I've seen other methods at the link above but I want to  keep it simple by using induction. How should I proceed?
The answer is supposed to be : $2^{n+1}-n-2$
 [/INST] look for a particular solution of the form $T(n) = an + b$ where $a,b$ need to be determined. we need $an + b = 2(an - a + b) + n$ equating the coefficient of $n$ gives you $a = -2$ and then $b = 2b -a$ so $b = a + -2$ and $T(n) = -n-2$ is a particular solutions. the solution to the homogeneous equation is $T(n) = C2^{n}$ and the general solution is $$T(n) = C2^n - n - 2 $$ fix the $C$ to satisfy $T(1) = 1$ 
$\bf edit: $
we will need $1*2 + 2*2^2 + 3*2^3 + \cdots + (n-2)*2^{n-2} = (n-3)2^{n-1}+2$
here is your method taking from where you sopped
$\begin{align}T(n) &= 2^{n-1}T(1) + (2^{n-1} - 1)n -\left(1*2 + 2*2^2 + 3*2^3 + \cdots+ (n-2)2^{n-2} \right)\\
&=2^{n-1} + (2^{n-1} - 1)n -\left( (n-3)2^{n-1}+2  \right)\\
&=2^{n+1}-n -2
\end{align}$
</s>