Evaluating the Recurrence Relation $T(n) = 2T(n - 1) + n$

We are given a linear first-order non-homogeneous recurrence relation:

$\qquad T(n) = 2T(n - 1) + n$, for $n \ge 2$

with the base case $T(1) = 1$. We need to find a closed-form expression for $T(n)$.

Method of Iteration for Recurrence Relation

One common method to solve such recurrence relations is iteration. We repeatedly substitute the definition of $T(n-k)$ into the expression for $T(n)$.

• Starting with the original recurrence:

  $\qquad T(n) = 2T(n - 1) + n$

• Substitute $T(n-1)$ using $T(n-1) = 2T(n-2) + (n-1)$:

  $\qquad T(n) = 2[2T(n-2) + (n-1)] + n$

  $\qquad T(n) = 2^2 T(n-2) + 2(n-1) + n$

• Substitute $T(n-2)$ using $T(n-2) = 2T(n-3) + (n-2)$:

  $\qquad T(n) = 2^2[2T(n-3) + (n-2)] + 2(n-1) + n$

  $\qquad T(n) = 2^3 T(n-3) + 2^2(n-2) + 2(n-1) + n$

We can see a pattern emerging. After $k$ iterations, the expression for $T(n)$ will be:

$\qquad T(n) = 2^k T(n-k) + \sum_{i=0}^{k-1} 2^i (n-i)$

Reaching the Base Case T(1)

We continue iterating until we reach the base case $T(1)$. This occurs when $n-k = 1$, which means $k = n-1$. Substituting $k=n-1$ into the general form:

$\qquad T(n) = 2^{n-1} T(n-(n-1)) + \sum_{i=0}^{(n-1)-1} 2^i (n-i)$

$\qquad T(n) = 2^{n-1} T(1) + \sum_{i=0}^{n-2} 2^i (n-i)$

Using the given base case $T(1) = 1$:

$\qquad T(n) = 2^{n-1} \cdot 1 + \sum_{i=0}^{n-2} (n \cdot 2^i - i \cdot 2^i)$

$\qquad T(n) = 2^{n-1} + n \sum_{i=0}^{n-2} 2^i - \sum_{i=0}^{n-2} i \cdot 2^i$

Evaluating the Sums

We need to evaluate the two sums:

1. Geometric Sum: $\sum_{i=0}^{n-2} 2^i$
2. Arithmetic-Geometric Sum: $\sum_{i=0}^{n-2} i \cdot 2^i$

Evaluating the Geometric Sum

The first sum is a geometric series with first term $2^0=1$, ratio $2$, and $n-2 - 0 + 1 = n-1$ terms:

$\qquad \sum_{i=0}^{n-2} 2^i = \frac{2^{n-1} - 1}{2 - 1} = 2^{n-1} - 1$

Evaluating the Arithmetic-Geometric Sum

The second sum is $\sum_{i=0}^{n-2} i \cdot 2^i = 0 \cdot 2^0 + 1 \cdot 2^1 + 2 \cdot 2^2 + \dots + (n-2) \cdot 2^{n-2}$. The term for $i=0$ is zero, so this is equivalent to $\sum_{i=1}^{n-2} i \cdot 2^i$.

Let $S = \sum_{i=1}^{m} i x^i$. We can derive the formula for this sum. Consider the geometric series $\sum_{i=0}^{m} x^i = \frac{x^{m+1}-1}{x-1}$. Differentiating with respect to $x$ gives $\sum_{i=1}^{m} i x^{i-1} = \frac{(m+1)x^m(x-1) - (x^{m+1}-1)}{(x-1)^2}$. Multiplying by $x$ gives $\sum_{i=1}^{m} i x^i = x \frac{(m+1)x^m(x-1) - (x^{m+1}-1)}{(x-1)^2}$.

For our sum, $m = n-2$ and $x = 2$. So, $\sum_{i=1}^{n-2} i \cdot 2^i$ is:

$\qquad S_{AG} = \sum_{i=1}^{n-2} i \cdot 2^i = 2 \frac{(n-2+1)2^{n-2}(2-1) - (2^{n-2+1}-1)}{(2-1)^2}$

$\qquad S_{AG} = 2 \frac{(n-1)2^{n-2} \cdot 1 - (2^{n-1}-1)}{1^2}$

$\qquad S_{AG} = 2 [(n-1)2^{n-2} - 2^{n-1} + 1]$

$\qquad S_{AG} = (n-1)2^{n-1} - 2 \cdot 2^{n-1} + 2 \cdot 1$

$\qquad S_{AG} = (n-1)2^{n-1} - 2^n + 2$

Substituting Sums Back into T(n)

Now substitute the results of the sums back into the expression for $T(n)$:

$\qquad T(n) = 2^{n-1} + n (2^{n-1} - 1) - [(n-1)2^{n-1} - 2^n + 2]$

$\qquad T(n) = 2^{n-1} + n 2^{n-1} - n - (n-1)2^{n-1} + 2^n - 2$

$\qquad T(n) = 2^{n-1} + n 2^{n-1} - n - n 2^{n-1} + 2^{n-1} + 2^n - 2$

Combine terms with $2^{n-1}$: $(2^{n-1} + n 2^{n-1} - n 2^{n-1} + 2^{n-1}) = (1+n-n+1)2^{n-1} = 2 \cdot 2^{n-1} = 2^n$.

So, the expression becomes:

$\qquad T(n) = 2^n + 2^n - n - 2$

$\qquad T(n) = 2 \cdot 2^n - n - 2$

$\qquad T(n) = 2^{n+1} - n - 2$

Verification

Let's verify this closed form with the base case and a few small values:

• For $n=1$: $T(1) = 2^{1+1} - 1 - 2 = 2^2 - 3 = 4 - 3 = 1$. This matches the given $T(1)=1$.
• For $n=2$: Using the recurrence, $T(2) = 2T(1) + 2 = 2(1) + 2 = 4$. Using the formula, $T(2) = 2^{2+1} - 2 - 2 = 2^3 - 4 = 8 - 4 = 4$. This matches.
• For $n=3$: Using the recurrence, $T(3) = 2T(2) + 3 = 2(4) + 3 = 8 + 3 = 11$. Using the formula, $T(3) = 2^{3+1} - 3 - 2 = 2^4 - 5 = 16 - 5 = 11$. This matches.

The formula $T(n) = 2^{n+1} - n - 2$ correctly evaluates the recurrence relation.

Comparison with Options

Comparing our derived closed form $T(n) = 2^{n+1} - n - 2$ with the given options, we find it matches one of them.

The closed form $T(n) = 2^{n+1} - n - 2$ is the correct evaluation of the given recurrence relation.

Revision Table: Recurrence Relations

Additional Information: Solving Non-Homogeneous Recurrences

Linear non-homogeneous recurrence relations of the form $T(n) = a T(n-1) + f(n)$ can also be solved using the method of finding a homogeneous solution and a particular solution.

1. Homogeneous Solution ($T_h(n)$): Solve the associated homogeneous recurrence $T_h(n) = a T_h(n-1)$. The characteristic equation is $r - a = 0$, so $r=a$. The homogeneous solution is $T_h(n) = C \cdot a^n$ for some constant $C$. In our case, $a=2$, so $T_h(n) = C \cdot 2^n$.

2. Particular Solution ($T_p(n)$): Guess a form for $T_p(n)$ based on the non-homogeneous term $f(n)$. Since $f(n) = n$ (a linear polynomial in $n$), we guess a particular solution of the form $T_p(n) = An + B$. Substitute this into the original recurrence:

$\qquad An + B = 2(A(n-1) + B) + n$

$\qquad An + B = 2An - 2A + 2B + n$

$\qquad An + B = (2A + 1)n + (2B - 2A)$

Equating coefficients of $n$ and constant terms:

• Coefficients of $n$: $A = 2A + 1 \implies -A = 1 \implies A = -1$
• Constant terms: $B = 2B - 2A \implies -B = -2A$. Since $A=-1$, $-B = -2(-1) = 2 \implies B = -2$.

So the particular solution is $T_p(n) = -n - 2$.

3. General Solution: The total solution is the sum of the homogeneous and particular solutions: $T(n) = T_h(n) + T_p(n) = C \cdot 2^n - n - 2$.

4. Using Base Case to Find C: Use the base case $T(1) = 1$ to find $C$:

$\qquad T(1) = C \cdot 2^1 - 1 - 2 = 1$

$\qquad 2C - 3 = 1$

$\qquad 2C = 4$

$\qquad C = 2$

Substituting $C=2$ back into the general solution:

$\qquad T(n) = 2 \cdot 2^n - n - 2$

$\qquad T(n) = 2^{n+1} - n - 2$

This confirms the result obtained by the iteration method.