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?

T(n)=2T(n-1)+n -----(1) 
T(n-1)=2T(n-2)+n-1 ------(2)
T(n-2)=2T(n-3)+n-2 ------(3)
Substitute (3) in (2) and then (2) in (1)
T(n-1)=$2^2T$(n-3)+2(n-2)+(n-1)
T(n)= $2^3$T(N-3)+$2^2$(n-2)+2(n-1)+n
=> T(k)=$2^k$T(n-k) + $2^{k-1}$(n-(k-1))+........+$2^0$n
Now, since T(1)=1, let n-k=1 => k=n-1
T(n)=$2^{n-1}$T(1) + $2^{n-2}$(2) + $2^{n-3}$(3) + $2^{n-n}$(n) --------(4)
Multiply Equation (4) with 2
T(n)=$2^{n}$+$2^{n-1}$ + $2^{n-2}$ + $2^{n-3}$+...... + 2n ----------- (5)
Subtract Equation (5) with (4)
T(n)=$2^{n}$+$2^{n-1}$+$2^{n-2}$+$2^{n-3}$+........+2 -n
Using sum of GP terms, we get :
[ $2^{1}$($2^{n}$-1) - n ]/ (2-1)
= $2^{n+1}$ -2 -n
