Consider the following recurrence relation: T(n) = 2T(n-1) + n2^n for n > 0, T(0) = 1. Which ONE of the following options is CORRECT?

GATE CSE 2025 Session 1 Q20: Solve T(n) = 2T(n−1) + n·2^n

Consider the following recurrence relation:

$T(n) = 2T(n-1) + n2^n \text{ for } n > 0, \quad T(0) = 1.$

Which ONE of the following options is CORRECT?

Try it: multiple choice: exactly one correct option

Wrong answer costs 1/3 mark in GATE.

Show answer and explanation

Answer: A (official GATE 2025 final answer key)

Concept used: Divide out the homogeneous growth $2^n$ to turn the recurrence into a simple sum.

First step: Let $S(n) = T(n)/2^n$ ; then $S(n) = S(n-1) + n$ , so $S(n) = 1 + \sum_{k=1}^{n} k$ .

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2025 Session 1 CS question paper and final answer key, organised by IIT Roorkee. Question paper · Answer key