Solve recurrence T(n)=2T(n-1)+n for n greater than 1 and T(1)=1
Hint:
$$\begin{align*}
T(n) &amp;= 2T(n-1) + n \\
&amp;= 2^2 T(n-2) + (2n + n) - 2 \\
&amp;= 2^3 T(n-3) + (2^2n + 2n + n) - (2^2 \cdot 2 - 2) \\
&amp;= 2^4 T(n-4) + (2^3n + 2^2n + 2n + n) - (2^3 \cdot 3 + 2^2 \cdot 2 + 2^1 \cdot 1) \\
&amp;= \cdots
\end{align*}$$

If you are familiar with the required methods, you can also solve it using generating functions (and, e.g., techniques from here or chapter 7 of "Concrete Mathematics" by Graham, Knuth, et al.).