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?

Let's use the method of annihilators to turn this into a third-order, homogeneous recurrence, and then solve with a characteristic equation.  First, we write the recurrence so $n$ is the least index:
$$T(n) - 2T(n-1)= n \implies T(n+1)-2T(n) = n+1$$
Then, we rewrite the recurrence in terms of the shift operator $E$:
$$(E-2)T(n) = n+1$$
Applying the $(E-1)$ operator to both sides of the equation, we have:
$$(E-1)^2(E-2)T(n) = (E-1)^2(n+1)$$
Now, since $(E-1)^2(n+1) = 0$ (it annihilates that term), we have:
$$(E-1)^2(E-2)T(n) = 0$$
The characteristic equation is, then $(r-1)^2(r-2)=0$, so our roots are $r=1$ (with multiplicity $2$) and $r=2$.  So, the recurrence has the form:
\begin{align*}
T(n) &= c_1\cdot 2^n + c_2 \cdot n1^n + c_3 \cdot 1^n\\
&= c_1\cdot 2^n + nc_2 + c_3
\end{align*}
Using the recurrence relation, we compute $T(1) = 1, T(2) = 4, T(3) = 11$ and can now solve for $(c_1, c_2, c_3)$, which gives the solution $(2, -1, -2)$.
