Problem statement: Solve $T(n)$ for $T(n)=2T(n-1)+n$, $n > 1$, and $T(1)=1$.
My attempt: I tried back substituting but I am unable to find a general pattern: $$\begin{align*} T(n) &=2^2 T(n-2)+3n-2 \\ &=2^3 T(n-3)+7n-10 \\ &=2^4 T(n-4)+15n-34 \\ &=\cdots \end{align*}$$
Hint: $$\begin{align*} T(n) &= 2T(n-1) + n \\ &= 2^2 T(n-2) + (2n + n) - 2 \\ &= 2^3 T(n-3) + (2^2n + 2n + n) - (2^2 \cdot 2 - 2) \\ &= 2^4 T(n-4) + (2^3n + 2^2n + 2n + n) - (2^3 \cdot 3 + 2^2 \cdot 2 + 2^1 \cdot 1) \\ &= \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.).
A different general method to solve these recurrences is to frame them as a matrix multiplication :
$$ \left( \begin{matrix}T_{n+1}\\ n+1 \\ 1\end{matrix} \right) = \left( \begin{matrix}2T_{n}+n+1\\ n+1 \\ 1\end{matrix} \right) = \underbrace{\left( \begin{matrix}2&1&1 \\ 0&1&1 \\ 0&0&1\end{matrix} \right)}_M \left( \begin{matrix}T_{n}\\ n \\ 1\end{matrix} \right) $$
Now you have: $$ \left( \begin{matrix}T_{n}\\ n \\ 1\end{matrix} \right) = M^n \left( \begin{matrix}1\\ 1 \\ 1\end{matrix} \right) $$
You can get $M^n$ in $O(log(n))$ time through exponentiation.
Another option is to consider the related sequence $S(n) = T(n)/2^n$, which satisfies the recurrence $$ S(n) = S(n-1) + \frac{n}{2^n}, $$ whose solution is simply $$ S(n) = S(1) + \sum_{m=2}^n \frac{m}{2^m}. $$ The sum can be evaluated in many ways, for example (adding the $m=1$ term) $$ \sum_{m=1}^n \frac{m}{2^m} = \sum_{m=1}^n \sum_{k=1}^m \frac{1}{2^m} = \sum_{k=1}^n \sum_{m=k}^n \frac{1}{2^m} = \sum_{k=1}^n \left(\frac{1}{2^{k-1}} - \frac{1}{2^n} \right) = 2 - \frac{n+2}{2^n}. $$ This shows that $$ S(n) = 2 - \frac{n+2}{2^n}, \quad T(n) = 2^{n+1} - n - 2. $$ Indeed, one calculates that $T(1) = 2^2-1-2 = 1$, and $$ T(n) - 2T(n-1) = 2^{n+1} - n - 2 - 2(2^n - n - 1) = n. $$
