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

GATE · 2004 · CS

T(1) = 1
T(n) = 2T(n - 1) + n, n ≥ 2 

1. A.

   2n + 1 - n - 2

2. B.

   2n - n

3. C.

   2n + 1 - 2n - 2

4. D.

   2n + n

Attempted by 101 students.