The recurrence equation T(1) = 1 T(n) = 2T(n - 1) + n, n ≥ 2 evaluates to

Solution outline: derive a closed form for T(n)=2T(n-1)+n with T(1)=1.

Key step: divide by 2^n and telescope.

• Let S(n)=T(n)/2^n. Then from T(n)=2T(n-1)+n we get S(n)-S(n-1)=n/2^n.

• Sum from k=1 to n: S(n)=S(1)+ sum_{k=2}^{n} k/2^k. Since S(1)=T(1)/2=1/2, this implies S(n)=sum_{k=1}^{n} k/2^k.

• Use the closed form for the finite sum: for x=1/2, sum_{k=1}^{n} k x^{k} = 2 - (n+1)/2^{n-1} + n/2^{n}.

• Therefore S(n)=2 - (n+1)/2^{n-1} + n/2^{n}, and multiplying by 2^n gives

• T(n)=2^n * S(n) = 2^{n+1} - 2(n+1) + n = 2^{n+1} - n - 2.

Verification (brief):

• Base case n=1: 2^{2} - 1 - 2 = 1, matches T(1)=1.

• Inductive check: assuming T(n-1)=2^{n} - (n-1) - 2, then 2T(n-1)+n = 2(2^{n} - n +1 -2) + n = 2^{n+1} - n - 2, so the formula is consistent.

Final answer: T(n) = 2^{n+1} - n - 2.