<s>[INST] Solve the recurrence $T(n) = 2T(n-1) + n$ Solve the recurrence  $T(n) = 2T(n-1) + n$
where $T(1) = 1$ and $n\ge 2$.
The final answer is $2^{n+1}-n-2$
Can anyone arrive at the solution?
 [/INST] By subtraction
$$
\begin{array}{rrcl}
& T(n)-2T(n-1) &=& n \\
& T(n-1) - 2T(n-2) &=& n-1 \\
\hline
& T(n)-3T(n-1)+2T(n-2) &=& 1
\end{array}$$
Again, by subtraction
$$
\begin{array}{rrcl}
& T(n)-3T(n-1)+2T(n-2) &=& 1 \\
& T(n-1)-3T(n-2)+ 2T(n-3) &=& 1 \\
\hline
& T(n)-4T(n-1)+5T(n-2)-2T(n-3) &=& 0
\end{array}$$
Characteristic equation of the recursion is
$$x^3-4x^2+5x-2 = 0$$
Roots of the equation are $x_1 = x_2 = 1$ and $x_3 = 2$
So, general solution of the recursion is $$T(n) = C_1\cdot 1^n + C_2\cdot n\cdot 1^n + C_3\cdot 2^n$$ or $$T(n) = C_1 + C_2\cdot n + C_3\cdot 2^n$$
now, from $T(1) = 1$ we get $T(2) = 4$ and $T(3) = 11$.
So, we get system 
$$
\begin{array}{ccccccc}
C_1  &+&C_2 &+& 2C_3 &=& 1 \\
C_1 &+&2C_2&+&4C_3 & =& 4 \\
C_1 & +& 3C_2 &+& 8C_3 &=& 11
\end{array}$$
From this system we get that $C_1 = -2$, $C_2 =-1$, and $C_3 = 2$, so particular solution of the recursion is $$T(n) =2\cdot2^n-n-2,$$ or $$T(n) = 2^{n+1}-n-2.$$
</s>